java中关于队列的数组和链表实现

队列的介绍

队列是一种先进先出（FIFO）的线性的数据结构，队列的主要操作为入队和出队。

队头：队列的出口端，队尾：队列的入口端，通常在数组中表示为最后入队元素的下一个位置。

在用数组实现时，注意：若队头不断有元素出队，那么队列的可用空间就会变小，所以我们通常用循环队列来实现，此时队尾也可能出现在队头的前面。

相关学习视频教程推荐：java学习

队列的数组实现

队列的数组实现这里的队列一般都是循环队列！

特别注意：

（1）队列满时的判断条件为(队尾下标+1) % 数组长度 = 队头下标

（2）队尾指针指向的位置空出一位，因此队列最大容量比数组长度小1。

public class MyQueue {     private int[] array;     private int front;     private int rear;     public MyQueue(int capacity){         array = new int[capacity];     }       /*     入队时，只需判断队列是否已满，若队列已满，则抛出异常，其他情况（包括队列为空）都正常插入      */     public void enQueue(int data) throws Exception{         if((rear+1) % array.length  == front)             throw new Exception("队列已满，不能入队！");         array[rear] = data;         rear = (rear+1) % array.length;     }       /*     出队时，判断队列是否为空，若队列为空，抛出异常      */     public int deQueue() throws Exception{         if(front == rear)             throw new Exception("队列为空，不能出队！");         int temp = array[front];         front = (front+1) % array.length;         return temp;     }   //    public void output(){ //        for(int i = front; ((i+1) % array.length) <= rear; i++){ //一直在循环输出，严重错误！不能把取模判断语句写在条件里面！ //            i %= array.length; //            System.out.println(array[i]); //        } //    }       public void output(){         for(int i = front; i != rear; i = (i+1) % array.length){             System.out.println(array[i]);         }     }     public static void main(String[] args) throws Exception{         MyQueue myQueue = new MyQueue(5);//长度为5的队列只能插入4个元素         myQueue.enQueue(1);         myQueue.enQueue(3);         myQueue.enQueue(2);         myQueue.enQueue(4);         myQueue.deQueue();         myQueue.deQueue();         myQueue.enQueue(5);         myQueue.enQueue(6);         myQueue.output();     }   }

队列的链表实现

队列用链表实现时，用头指针指向队列的第一个节点，用尾指针指向队列的最后一个节点。

public class MyQueue_LinkList {     private static class Node{         int data;         Node next;         Node(int data){             this.data = data;         }     }       private Node front;     private Node rear;     private int size;//队列中实际元素的个数     private int maxsize;       public MyQueue_LinkList(int capacity){         maxsize = capacity;     }       public void enQueue(int data) throws Exception{         if(size >= maxsize)             throw new Exception("队列已满，无法入队");         Node insertedNode = new Node(data);         if(size == 0){             front = insertedNode;             rear = insertedNode;         }         else{             rear.next = insertedNode;             rear = insertedNode;         }         size++;     }       public int deQueue() throws Exception{         if(front == null)             throw new Exception("队列为空，无法出队！");         int temp;         if(front == rear)//队列中只有一个节点             rear = null;         temp = front.data;         front = front.next;         size--;         return temp;     }       public void output(){         Node temp = front;         for(int i = 0 ; i < size; i++){             System.out.println(temp.data);             temp = temp.next;         }     }       public static void main(String[] args) throws Exception{         MyQueue_LinkList myQueue_linkList = new MyQueue_LinkList(5);         myQueue_linkList.enQueue(1);         myQueue_linkList.enQueue(3);         myQueue_linkList.enQueue(2);         myQueue_linkList.deQueue();         myQueue_linkList.deQueue();         myQueue_linkList.enQueue(5);         myQueue_linkList.enQueue(7);         myQueue_linkList.output();       } }

队列的应用场景

（1）银行排队，先来先服务。

（2）多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。

（3）网络爬虫实现网站抓取，就是把待抓取的网站URL存入队列中，再按照存入队列的顺序来依次抓取和解析。

相关文章教程推荐：java入门教程

以上就是java中关于队列的数组和链表实现的详细内容，更多内容请关注技术你好其它相关文章！