一、什么是队列

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

双端队列：可以在对头或者队尾进行插入或者删除操作。

普通队列和双端队列

从上面知道双向列表可以当普通队列使用，也可以当双端队列使用，也可以当栈使用。

二、队列常用的方法

2.1、Queue

注意add函数和offer函数

public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();queue.add(1);//添加元素queue.add(2);//添加元素queue.add(3);//添加元素queue.offer(4);//添加元素queue.offer(5);//添加元素queue.offer(6);//添加元素System.out.println(queue.peek());//获取对头元素，但是不删除System.out.println(queue.element());//获取对头元素，但是不删除System.out.println(queue.poll());//获取对头元素，并且删除对头元素System.out.println(queue.remove());//获取对头元素，并且删除对头元素}

2.2、Deque

public static void main(String[] args) {Deque<Integer> deque = new LinkedList<>();deque.add(1);//默认在队尾添加元素deque.addFirst(2);//在对头添加元素deque.addLast(3);//在队尾添加元素deque.offer(4);//在队尾添加元素deque.offerLast(5);//在队尾添加元素deque.offerFirst(6);//在队头添加元素System.out.println(deque);System.out.println(deque.peek());//获取元素，但是不删除System.out.println(deque.peekFirst());//获取队头元素，但是不删除System.out.println(deque.peekLast());//获取队尾元素，但是不删除System.out.println(deque.poll());//获取队头元素，并且删除System.out.println(deque.pollFirst());//获取队头元素，并且删除System.out.println(deque);}

三、单链表模拟实现队列

单链表可以实现队列，那双向链表也可以实现队列
使用单链表第三种方式实现队列
offer（）- 在队列里面添加元素

/*** 在队列里面添加元素，实际上就是尾插法* @param val*/public void offer(int val){//要插入节点，那就要先创造一个节点Node node = new Node(val);//这时候就要分两种情况：1、如果是第一次插入 2、不是第一次插入if(head == null){//head == null说明是第一次插入head = node;last = node;}else {last.next = node;last = last.next;}}

poll（） - 出队列

/*** 出队列，并且删除元素* @return*/public int poll(){//出队列就是删除头结点，但是如果链表里面没有节点那就不能删除if(isEmpty()){throw new RuntimeException("队列为空！");}int oldVal = head.val;head = head.next;return oldVal;}/*** 判断队列是否为空，如果队列为空那就返回true，否则返回FALSE* @return*/public boolean isEmpty(){return this.head == null;}

使用的单链表实现简单的队列

//使用单链表实现队列，首先就要定义节点
class Node{//值域public int val;//指针域public Node next;public Node(int val){this.val = val ;}
}
public class MyQueue {//单链表实现队列，那就要加上一个尾指针public Node head;//头结点public Node last;//尾巴节点/*** 在队列里面添加元素，实际上就是尾插法* @param val*/public void offer(int val){//要插入节点，那就要先创造一个节点Node node = new Node(val);//这时候就要分两种情况：1、如果是第一次插入 2、不是第一次插入if(head == null){//head == null说明是第一次插入head = node;last = node;}else {last.next = node;last = last.next;}}/*** 出队列，并且删除元素* @return*/public int poll(){//出队列就是删除头结点，但是如果链表里面没有节点那就不能删除if(isEmpty()){throw new RuntimeException("队列为空！");}int oldVal = head.val;head = head.next;return oldVal;}/*** 判断队列是否为空，如果队列为空那就返回true，否则返回FALSE* @return*/public boolean isEmpty(){return this.head == null;}/*** 获取对头的元素* @return*/public int peek(){//出队列就是删除头结点，但是如果链表里面没有节点那就不能删除if(isEmpty()){throw new RuntimeException("队列为空！");}return head.val;}
}

四、循环队列

我们说了可以利用链表实现队列，那能不能利用数组实现队列？？？

上图转载于：https://blog.csdn.net/DarkAndGrey/article/details/122511544

队列面试题

设计循环队列

public class MyCircularQueue {//我们知道循环队列是有数组实现的，所以要创建一个数组，并且还有表示对头和队尾的下标public int[] elem;public int front;//对头的下标public int rear;//队尾的下标/*** 构造方法，初始化数组的大小* @param k*/public MyCircularQueue(int k) {this.elem = new int[k+1];}/*** 入队列* @param value* @return*/public boolean enQueue(int value) {//在入队列的时候先判断队列是否满，满了不能入if(isFull()){return false;}elem[rear] = value;rear = (rear+1) % elem.length;return true;}/*** 出队列* @return*/public boolean deQueue() {if(isEmpty()){return false;}front = (front+1) % elem.length;return true;}/*** 返回对头下标的元素* @return*/public int Front() {if(isEmpty()){return -1;}return elem[front];}/*** 获取队尾元素* @return*/public int Rear() {if(isEmpty()){return -1;}int index = 0;if(rear == 0){index = elem.length - 1;}else{index = rear - 1;}return elem[index];}public boolean isEmpty() {//front的下一个是rear，那就说明空了return front == rear;}/*** 判断队列是否满* @return*/public boolean isFull() {//rear的下一个如果是front，那这个队列就满了if((rear+1) % elem.length == front){return true;}return false;}
}

用队列实现栈

class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}/*** 添加元素，将要添加的元素放入不为空的栈里面* @param x*/public void push(int x) {if(!qu1.isEmpty()){//如果qu1不为空，那就插入元素qu1.offer(x);}else if(!qu2.isEmpty()){//如果qu2不为空，那就插入元素qu2.offer(x);}else{//第一次插入的时候，两个都为空的时候，那就指定队列插入元素qu1.offer(x);}}/*** 弹出元素* @return*/public int pop() {if (empty()){return -1;}if(!qu1.isEmpty()){int size = qu1.size();for (int i = 0; i < size - 1; i++) {int val = qu1.poll();qu2.offer(val);}return qu1.poll();}if(!qu2.isEmpty()){int size = qu2.size();for (int i = 0; i < size - 1; i++) {int val = qu2.poll();qu1.offer(val);}return qu2.poll();}return -1;}public int top() {if (empty()){return -1;}if(!qu1.isEmpty()){int val = 0;//要记录这个size ，不然当出一个元素的时候这个函数都会变化，得到的值也会变化int size = qu1.size();for (int i = 0; i < size; i++) {val = qu1.poll();qu2.offer(val);}return val;}if(!qu2.isEmpty()){int val = 0;int size = qu2.size();for (int i = 0; i < size; i++) {val = qu2.poll();qu1.offer(val);}return val;}return -1;}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

用栈实现队列

class MyQueue {Stack<Integer> stack1;Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {// 防止 别人一开始 就调用 peek，所以 peek 也需要 写 stack1 导入 stack2 的程序if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {// 如果模拟的队列 将全部数据出队，那么 stack1 和 stack2 都为空return stack1.isEmpty() && stack2.isEmpty();}
}