1.概念

队列 : 只允许在一段进行插入数据操操作 , 在另一端进行删除数据操作的特殊线性表 ; 队列是先进先出

入队列 : 进行插入操作的一端称为队尾

出队列 : 进行删除操作的一端称为对头

2.队列的使用

在Java中 , Queue 是一个接口 , 底层通过链表实现的

方法	行为	说明
`add(E e)`	添加元素到队尾（若队列已满，抛出 `IllegalStateException`）	推荐使用 `offer()`
`offer(E e)`	添加元素到队尾（队列满时返回 `false`）	更安全的插入方式
`remove()`	移除并返回队头元素（队列空时抛出`NoSuchElementException`）	推荐使用 `poll()`
`poll()`	移除并返回队头元素（队列空时返回 `null`）	安全的移除方式
`element()`	查看队头元素（不删除，队列空时抛出异常）	推荐使用 `peek()`
`peek()`	查看队头元素（不删除，队列空时返回 `null`）	安全的查看方式

public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();queue.offer(11);//添加元素到队尾queue.offer(12);queue.offer(13);queue.offer(14);queue.offer(15);System.out.println(queue);//打印队列  [11, 12, 13, 14, 15]int a1 = queue.poll();//移除头元素,并返回System.out.println(a1);//11System.out.println(queue);//[12, 13, 14, 15]int a2 = queue.peek();//获取队头元素System.out.println(a2);//12
}

3.队列的模拟实现

①实现队列

public class MyQueue {public static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val){this.val = val;}}public int usedSize = 0;public ListNode head = null;public ListNode last = null;public boolean isEmpty(){//检查是否为空return usedSize == 0;//如果是空的 , usedSize为0 返回true}public void offer(int val){//入队列,采用的是尾插法ListNode node = new ListNode(val);if(isEmpty()){head = last =  node;//把node节点赋值给head和lastusedSize++;}else {last.next = node;node.prev = last;last = node;usedSize++;}}public int poll(){//相应的出队列应该采用,头删法if(isEmpty()) {return -1;}int vall = head.val;head = head.next;if(head != null){head.prev = null;}usedSize--;return vall;}public int size(){//返回大小return usedSize;}}

②测试

public static void main(String[] args) {MyQueue myQueue = new MyQueue();myQueue.offer(11);//添加元素到队尾myQueue.offer(12);myQueue.offer(13);myQueue.offer(14);myQueue.offer(15);System.out.println(myQueue.poll());
}

4.循环队列

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间
但是使用循环队列，我们能使用这些空间去存储新的值

方法名	描述	参数	返回值	特殊说明
MyCircularQueue(k)	构造器，初始化队列，设置队列容量为 k	int k（队列容量）	无	内部实际使用 k+1 的空间来区分空满状态
Front()	获取队首元素	无	int（队首元素值）	队列为空时返回 - 1
Rear()	获取队尾元素	无	int（队尾元素值）	队列为空时返回 - 1
enQueue(value)	向队列插入元素	int value（待插入元素）	boolean（插入成功返回 true，队列满则返回 false）	插入后队尾指针循环后移
deQueue()	从队列删除队首元素	无	boolean（删除成功返回 true，队列为空则返回 false）	删除后队首指针循环后移
isEmpty()	检查队列是否为空	无	boolean（为空返回 true，否则返回 false）	当 front == rear 时队列空
isFull()	检查队列是否已满	无	boolean（已满返回 true，否则返回 false）	当 (rear+1) % 容量 == front 时队列满

class MyCircularQueue {public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {elem = new int[k+1];}//入队列 public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear = (rear+1)%elem.length;return true;}//出队列 public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1)%elem.length;return true;}//得到队头元素 public int Front() {if(isEmpty()) {return -1;}return elem[front];}public int Rear() {if(isEmpty()) {return -1;}int index = (rear == 0) ? elem.length-1 : rear-1;return elem[index];}public boolean isEmpty() {return rear == front;}public boolean isFull() {return (rear+1)%elem.length == front;}}

5.双端队列(Deque)

双端队列是指允许两端都可以进行入队和出队操作的队列

Deque是一个接口, 使用时必须创建LinkedList对象

Deque的接口比较多 , 栈和队列均可以实现该接口

public static void main(String[] args) {Deque<Integer> stack = new LinkedList<>();//双端队列的链式实现Deque<Integer> queue = new ArrayDeque<>();//双端队列的线性实现
}

6.用队列实现栈

模拟的入栈操作 : 将元素放到不为空的队列中
模拟的出栈操作 : 把不为空的队列中的size-1个元素放到另一个队列中 ; 最后剩下的就是模拟栈中的顶层元素

import java.util.LinkedList;
import java.util.Queue;class MyStackUseQueue {public Queue<Integer> qu1;public Queue<Integer> qu2;public MyStackUseQueue() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if(!qu1.isEmpty()) {qu1.offer(x);}else if(!qu2.isEmpty()) {qu2.offer(x);}else {qu1.offer(x);}}public int pop() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int size = qu1.size();for(int i = 0;i < size-1;i++) {qu2.offer( qu1.poll());}return qu1.poll();}else  {int size = qu2.size();for(int i = 0;i < size-1;i++) {qu1.offer( qu2.poll());}return qu2.poll();}}public int top() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int size = qu1.size();int val = 0;for(int i = 0;i < size;i++) {val = qu1.poll();qu2.offer(val);}return val;}else  {int size = qu2.size();int val = 0;for(int i = 0;i < size;i++) {val = qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

7.用栈实现队列

模拟入队操作 : 放到第一个栈中
模拟出队操作 : 判断第二个栈是否为空 ?

如果为空 : 需要把第一个栈中的所有元素都放到第二个栈里 , 取出第二个栈中的顶层元素

如果不为空 : 直接取出第二个栈中的顶层元素

import java.util.ArrayDeque;class MyQueueUseStack {public ArrayDeque<Integer> stack1;public ArrayDeque<Integer> stack2;public MyQueueUseStack() {stack1 = new  ArrayDeque<>();stack2 = new  ArrayDeque<>();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()) {return -1;}if(stack2.isEmpty()) {//第一个栈里面所有的元素 放到第二个栈当中 while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()) {return -1;}if(stack2.isEmpty()) {//第一个栈里面所有的元素 放到第二个栈当中 while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}