队列的原理及应用
一. 什么是队列?
- 队列: 只允许在一端进行插入数据操作, 在另一端进行数据删除操作的特殊线性表, 队列具有先进先出(FIFO)的特点
- 入队列: 在队尾进行插入数据
- 出队列: 在队头进行删除数据
二. 队列的使用
- 注: Java中, Queue是一个接口, 底层是通过链表实现的
- 队列中的常用操作
| 方法 | 功能 |
| boolean offer(E e) | 把 e 入到队列 |
| E poll() | 弹出队列中的元素 |
| E peek() | 获取队头元素 |
| int size() | 获取队列的长度 |
| boolean isEmpty() | 判断队列是否为空 |
import java.util.LinkedList;
import java.util.Queue;
// 队列的使用 FIFO
public class Demo {
public static void main(String[] args) {
// 申请队列
Queue<Integer> queue = new LinkedList<>();
// 入队
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
queue.offer(5);
System.out.println(queue);
// 出队
System.out.println(queue.poll());
System.out.println(queue.poll());
// 队列的有效元素个数
System.out.println(queue.size());
// 队列的队头元素
System.out.println(queue.peek());
// 判断队列是否为空
System.out.println(queue.isEmpty());
}
}- 双端队列
双端队列: 指允许队列的两端都可以进行入队和出队操作的队列, 说明元素可以从队头出队和入队, 元素也可也从队尾入队和出队。在实际工程中, 使用Deque接口比较多, 栈和队列均可以使用该接口
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
// 双端队列
public class DequeDemo {
public static void main(String[] args) {
// 双端队列的链式实现
Deque<Integer> deque = new LinkedList<>();
// 双端队列的线性实现
Deque<Integer> queue = new ArrayDeque<>();
}
}三. 队列的模拟实现
队列的实现分为顺序结构和链式结构, 两种均可实现队列
- 链式结构(使用链表来实现)
// 队列的模拟实现(链队)
public class MyQueue {
// 创建节点类
static class ListNode {
private int val;
private ListNode prev;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
}
// 队头
private ListNode head;
// 队尾
private ListNode tail;
// 有效元素个数
private int usedSize;
// 入队
public void offer(int val) {
// 创建新节点
ListNode node = new ListNode(val);
// 判空
if (head == null) {
head = tail = node;
} else {
// 头插法
node.next = head;
head.prev = node;
head = node;
}
// 队列中的元素个数 +1
usedSize++;
}
// 出队
public int poll() {
// 判断队列是否为空
if (head == null) {
return -1;
}
// 获取要出队的节点值
int oldVal = tail.val;
// 只有一个节点的情况
if (head == tail) {
// 把队头和队尾元素都置空
head = tail = null;
// 队列中的元素个数 -1
usedSize--;
return oldVal;
}
// 多个节点的情况
tail = tail.prev;
// 把要出队的节点置空
tail.next = null;
// 有效长度-1
usedSize--;
return oldVal;
}
// 获取队头元素
public int peek() {
// 判断队列是否为空
if (head == null) {
return -1;
}
return tail.val;
}
// 获取队列长度
public int size() {
return this.usedSize;
}
// 判断队列是否为空
public boolean isEmpty() {
// 队列中的元素个数为 0，则说明队列为空
return this.usedSize == 0;
}
// 打印
public String toString() {
ListNode cur = head;
// 用来拼接字符串
StringBuilder s = new StringBuilder();
while (cur != null) {
s.append(cur.val).append(" ");
cur = cur.next;
}
// 返回字符串
return s.toString();
}
}- 顺序结构(使用数组来实现)
1.使用usedSize来实现2.设置标记3. 留一个空间实现【常用】leetcode链接: 622. 设计循环队列 - 力扣（LeetCode）
// 循环队列实现
public class MyCircularQueue {
// 底层数组
private int[] elem;
// 队头下标
private int front;
// 队尾下标
private int rear;
// 初始化
public MyCircularQueue(int length) {
// 留一个空间来进行判断队列是否满了
this.elem = new int[length + 1];
}
// 入队
public boolean offer(int value) {
// 判满
if (isFull()) {
return false;
}
// 把元素放在队尾处
this.elem[rear] = value;
// 让rear后移一位
rear = (rear + 1) % this.elem.length;
return true;
}
// 判断队列是否满了
private boolean isFull() {
// 当队尾 +1 后和队头下标相同则说明队列满了【因为留出了一个空间来判断】
return ((rear + 1) % elem.length == front);
}
// 出队
public boolean poll() {
// 判空
if (isEmpty()) {
return false;
}
// 队头后移一位
front = (front + 1) % this.elem.length;
return true;
}
// 判空
private boolean isEmpty() {
// 队头和队尾指向同一个下标则说明队列为空
return this.front == this.rear;
}
// 获取队头元素
public int front() {
// 判空
if (isEmpty()) {
return -1;
}
return this.elem[front];
}
// 获取队尾元素
public int rear() {
// 判空
if (isEmpty()) return -1;
// rear在0的时候需要考虑特殊情况
if (rear == 0) {
return this.elem[elem.length - 1];
}
return this.elem[rear - 1];
// 另一种方法: 防止了rear在0的时候值的获取
// int index = (rear - 1 + elements.length) % elements.length;
}
// 获取数组长度
public int size() {
return (rear + elem.length - front) % elem.length;
}
}四. 常见算法题
1.用队列实现栈
- 题目描述: 225. 用队列实现栈 - 力扣（LeetCode）
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（ push、 top、 pop 和 empty）。实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
- 思路分析
两个队列模拟实现栈的操作；
1.push:
q1队列用于把元素入队; q2队列不为空时, 把元素弹出到q1中; 然后交换q1和q2, 完成元素的逆置
2.pop:
判断q2是否为空, 不为空则弹出q2的队头元素; 为空, 返回-1
3.top:
判断q2是否为空, 不为空则返回q2的队头元素; 为空, 返回-1
4.empty:
判断q2是否为空, 为空, 返回true; 不为空, 返回false
- 代码实现
class MyStack {
// 创建两个队列
private Queue<Integer> q1;
private Queue<Integer> q2;
// 初始化
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
// 入栈
public void push(int x) {
// q1 入队
q1.offer(x);
// q2 不为空, 则把 q2 中的值入到 q1 中
while (!q2.isEmpty()) {
q1.offer(q2.poll());
}
// 代码执行到此, q2 为空, q1 则是把队列中的数字逆置了
// 交换,让 q1 指向空, 让 q2 指向 q1
Queue<Integer> tmp = q1;
q1 = q2;
q2 = tmp;
}
// 出栈
public int pop() {
// 判空
if (empty()) {
return -1;
}
return q2.poll();
}
// 获取栈顶元素
public int top() {
if (empty()) {
return -1;
}
return q2.peek();
}
// 判断栈空
public boolean empty() {
return q2.isEmpty();
}
}
2.用栈使用队列
- 题目描述: 232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（ push、 pop、 peek、 empty）：实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
- 思路分析
两个栈进行模拟队列: s1, s2;
1.s1用来入元素, s2在需要出栈时对把s1的元素全部弹出到s2中, 然后弹出栈顶元素
2.出栈/获取栈顶元素需要注意: 当s2为空时, s1不为空时, 把s1中的元素全部弹出给s2, 进行元素逆置；s2不为空或s1为空不弹出, 因为s2中的元素已经逆置, 等待s2中的元素出队完即可再次逆置
- 代码详解
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 (empty()) {
return -1;
}
// 把 s1 中的元素逆置到 s2 中
reverse();
// 进行弹出
return s2.pop();
}
// 获取队头元素
public int peek() {
// 判空
if (empty()) {
return -1;
}
// 把 s1 中的元素逆置到 s2 中
reverse();
// 返回 s2 的队头元素
return s2.peek();
}
// 判空
public boolean empty() {
return s1.empty() && s2.empty();
}
// 逆置操作
private void reverse() {
// s2 为空, 则需要把 s1 中的元素逆置到 s2 中
while (s2.empty()) {
// s1 不为空, 进行弹出元素到 s2
while (!s1.empty()) {
s2.push(s1.pop());
}
}
}
}