关于队列，你需要知道这些

队列：先进先出 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First InFirst Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头。

队列也是一种特殊的线性表 也是只支持三个核心操作

入队列出队列取队首元素

队列的一些进化版本： 1.优先队列。 2.消息队列。给每个数据引入了“类型"的概念，这样就可以按指定类型来取数据 3.阻塞队列，和多线程密切相关。 （如果当前队列满了，再想插入元素，就需要等待）（阻塞） （如果当前队列为空，要想出队列元素，也需要等待）（阻塞） 4.无锁队列，和多线程密切相关，更高效

使用链表实现队列

package package11_1; class Node{ public int val; public Node next; public Node(int val) { this.val = val; } } public class MyQueue { //head 对应到队首元素 private Node head = null; //tail对应到队尾 private Node tail = null; private int size = 0; //1.入队列 public void offer(int x){ Node newNode = new Node(x); //插入到链表的尾部. if(head == null){ head = newNode; tail = newNode; size++; return; } tail.next = newNode; tail = tail.next; size++; return; } //2.出队列 public Integer poll(){ //空队列 if(head == null){ return null; } Integer ret = head.val; head = head.next; if(head == null){ //删除完后为空队列，这是，尾巴也要设置为空 tail = null; } return ret; } //3.取队首元素 public Integer peek(){ if(head == null){ return null; } return head.val; } public boolean isEmpty(){ return head == null; } public int size(){ return size; } public static void main(String[] args) { MyQueue myQueue = new MyQueue(); myQueue.offer(1); myQueue.offer(2); myQueue.offer(3); myQueue.offer(4); while (!myQueue.isEmpty()){ int curFront = myQueue.peek(); System.out.println(curFront); myQueue.poll(); } } }

数组来实现一个队列 为了让数组实现队列效率不能太低，我们可以使用循环队列的方式实现，通过改变头和尾的指向 关键：如果头和尾已经达到数组的最后一个元素，接下来再进行入队或者出队，就让这样的标记来到数组的开头。

package package11_1; public class MyQueue2 { private int[] date = new int[100]; private int head = 0;//队首元素的下标 private int tail = 0;//队尾元素的下标 //如果head == tail 则队列满了 因为这是个前闭后开区间 private int size = 0; //入队列 public boolean offer(int x){ if(size == date.length){ //满了 return false; } //把新元素放到tail的位置上 date[tail] = x; tail++; if(tail == date.length){ tail = 0; } size++; return true; } //出队列 public Integer poll(){ if(size == 0){ return null; } Integer ret = date[head]; head++; if(head == date.length){ head = 0; } size--; return ret; } public Integer peek(){ if(size == 0){ return null; } return date[head]; } public boolean isEmpty(){ return size == 0; } public int size(){ return size; } public static void main(String[] args) { MyQueue2 myQueue2 = new MyQueue2(); myQueue2.offer(1); myQueue2.offer(2); myQueue2.offer(3); myQueue2.offer(4); while (!myQueue2.isEmpty()){ int cur = myQueue2.peek(); System.out.println(cur); myQueue2.poll(); } } }

双端队列Deque 既可以从头部入也可以从尾部入 也可从头部出队列或者尾部出队列。