目录
一、概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头（Head/Front）
编辑
二、队列
2.1队列的概念
在Java中，Queue是个接口，底层是通过链表实现的。
编辑
编辑 注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现Queue接口。
编辑
2.1单链表模拟实现队列
编辑
编辑
public class MyQueue { static class ListNode{ private int value; private ListNode next; public ListNode(int val){ this.value=value; } } public ListNode head; public ListNode last; public int usedSize; public void offer(int val){ ListNode node=new ListNode(val); if(head==null){ head=node; last=node; } else{ last.next=node; last=last.next; } } public int poll(){ if(head==null){ return -1; } int val=-1; if(head.next==null){ val=head.value; head=null; last=null; return val; } val=head.value; head=head.next; usedSize--; return val; } public int peek(){ if(head==null){ return -1; } return head.value; } }
2.2双链表模拟实现队列
public class Queue { // 双向链表节点 public static class ListNode{ ListNode next; ListNode prev; int value; ListNode(int value){ this.value = value; } } ListNode first; // 队头 ListNode last; // 队尾 int size = 0; // 入队列---向双向链表位置插入新节点 public void offer(int e){ ListNode newNode = new ListNode(e); if(first == null){ first = newNode; // last = newNode; }else{ last.next = newNode; newNode.prev = last; // last = newNode; } last = newNode; size++; } // 出队列---将双向链表第一个节点删除掉 public int poll(){ // 1. 队列为空 // 2. 队列中只有一个元素----链表中只有一个节点---直接删除 // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除 int value = 0; if(first == null){ return -1; }else if(first == last){ last = null; first = null; }else{ value = first.value; first = first.next; first.prev.next = null; first.prev = null; } --size; return value; } // 获取队头元素---获取链表中第一个节点的值域 public int peek(){ if(first == null){ return -1; } return first.value; } public int size() { return size; } public boolean isEmpty(){ return first == null; } }
2.3队列的使用
public static void main(String[] args) { Queue<Integer> q = new LinkedList<>(); q.offer(1); q.offer(2); q.offer(3); q.offer(4); q.offer(5); // 从队尾入队列 System.out.println(q.size()); System.out.println(q.peek()); // 获取队头元素 q.poll(); System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回 if(q.isEmpty()){ System.out.println("队列空"); }else{ System.out.println(q.size()); } }
2.4循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。
编辑
编辑 力扣链接：环形队列
2.4.1设计环形队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
- MyCircularQueue(k): 构造器，设置队列长度为 k 。
- Front: 从队首获取元素。如果队列为空，返回 -1 。
- Rear: 获取队尾元素。如果队列为空，返回 -1 。
- enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
- deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
- isEmpty(): 检查循环队列是否为空。
- isFull(): 检查循环队列是否已满。
示例：
- MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
- circularQueue.enQueue(1); // 返回 true
- circularQueue.enQueue(2); // 返回 true
- circularQueue.enQueue(3); // 返回 true
- circularQueue.enQueue(4); // 返回 false，队列已满
- circularQueue.Rear(); // 返回 3
- circularQueue.isFull(); // 返回 true
- circularQueue.deQueue(); // 返回 true
- circularQueue.enQueue(4); // 返回 true
- circularQueue.Rear(); // 返回 4
提示：
- 所有的值都在 0 至 1000 的范围内；
- 操作数将在 1 至 1000 的范围内；
- 请不要使用内置的队列库。
class MyCircularQueue { private int[] elem; private int rear;//队尾 private int front;//对头 public MyCircularQueue(int k) { this.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; } }
三、双端队列
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
编辑
Deque是一个接口，使用时必须创建LinkedList的对象。
编辑 在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现 Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
四、面试题
4.1用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
编辑
public class MyStack { private int[] elem; private int usedSize; public MyStack() { this.elem = new int[5]; } //压栈 public void push(int val) { if(isFull()) { elem = Arrays.copyOf(elem,2*elem.length); } elem[usedSize] = val; usedSize++; } public boolean isFull() { return usedSize == elem.length; } //出栈 public int pop() { //1、判断栈不为空 if(empty()) { //抛出异常！！ throw new StackEmptyException("栈为空！"); } //2、开始删除 return elem[--usedSize]; } //获取栈顶元素 public int peek() { //1、判断栈不为空 if(empty()) { //抛出异常！！ throw new StackEmptyException("栈为空！"); } //2、开始删除 return elem[usedSize-1]; } public boolean empty() { return usedSize == 0; } }
4.2栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
编辑
import java.util.Stack; class MyQueue { private Stack<Integer> s1; private Stack<Integer> s2; public MyQueue() { s1 = new Stack<>(); s2 = new Stack<>(); } public void push(int x) { s1.push(x); } public int pop() { if(!s2.empty()) { return s2.pop(); }else { while(!s1.empty()) { int val = s1.pop(); s2.push(val); } return s2.pop(); } } public int peek() { if(!s2.empty()) { return s2.peek(); }else { while(!s1.empty()) { int val = s1.pop(); s2.push(val); } return s2.peek(); } } public boolean empty() { return s1.empty() && s2.empty(); } }
