队列
队列
你一定要努力成为你想要成为的人啊！！
队列的底层是双向链表！
学习不能停！
二、队列（Queue）
1. 概念
- 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
- 入队列：进行插入操作的一端称为队尾（Tail/Rear）
- 出队列：进行删除操作的一端称为队头（Head/Front）
2. 队列的使用
- 在Java中，Queue是个接口，底层是通过链表实现的。 （ 队列底层是双向链表）
- 相关基本框架：
- 方法：
- 注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
如：Queue q = new LinkedList<>();
3. 队列的模拟实现
- 相关：
1） 使用单链表：
头插法入队：O(1) 出队：O(n)-尾结点
尾插法入队：O(n) 出队：O(1)-头结点
2）使用单链表去实现：要实现出入队都是O(1)-加上一个tail引用标志尾结点
- 思路：
1.定义一个结点静态内部类
2.队列头尾结点定义
3.入队：void offer：判空 +操作
4.出队：poll：删除头结点–只有一个结点 + 判空 + 返回oldVal
5.peek：不删除只是查看当前头元素：判空+其他
6.size：
// 一般情况下队列入队用offer 而不是add
- 代码：
- MyQueue.java
// 使用单链表模拟实现队列功能 --复杂度O(1)
// 先进先出
public class MyQueue {
// 使用内部类--结点类-单链表
static class Node {
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
// 定义头尾结点
public Node head;
public Node tail;
// 开始模拟功能实现
// 有效元素个数
public static int usedSize;
// 入队 offer
public void offer(int val) {
Node node = new Node(val);
// 首先进行判空
if(this.head==null) {
this.head = node;
this.tail = node;
} else {
// 存在则直接操作
this.tail.next = node;
this.tail = this.tail.next;
}
usedSize++;
}
// 出队 poll:删除头结点！
public int poll() {
// 首先进行判空：
if(this.head==null) {
throw new EmptyQueueException("sorry 队列为空！");
}
// 保存旧的元素
int oldVal = this.head.val;
// 再进行是否只有一个元素判断
if(this.head.next==null) {
this.head = null;
this.tail = null;
} else {
// 多个元素
this.head = this.head.next;
}
usedSize--;
return oldVal;
}
// 查看当前头元素（不删除）peek
public int peek() {
// 首先进行判空
if(this.head==null) {
throw new EmptyQueueException("sorry 队列为空！");
}
return this.head.val;
}
// 求有效长度（元素个数）
public int size() {
return usedSize;
}
// 检测队列是否为空
public boolean isEmpty() {
return size()==0;
}
// 没有此方法
/*// 测试打印，实际方法并没有
public void print() {
Node cur = this.head;
while(cur!=null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}*/
}
- EmptyQueueException.java
public class EmptyQueueException extends RuntimeException{
public EmptyQueueException() {
}
public EmptyQueueException(String message) {
super(message);
}
}
- Test.java
public class Test {
public static void main(String[] args) {
MyQueue myQueue = new MyQueue();
System.out.println("进行入队操作：");
myQueue.offer(2);
myQueue.offer(8);
myQueue.offer(1998);
/*System.out.println("测试打印（实际没有该方法：");
myQueue.print();*/
System.out.println("有效长度为：");
System.out.println(myQueue.size());
System.out.println("进行队头的元素查看：");
System.out.println(myQueue.peek());
System.out.println("有效长度为：");
System.out.println(myQueue.size());
System.out.println("拿到并删除对头元素：（出队操作）");
System.out.println(myQueue.poll());
System.out.println("有效长度为：");
System.out.println(myQueue.size());
System.out.println("进行判空操作：");
System.out.println(myQueue.isEmpty());
}
}
4. 循环队列
- 如果使用**顺序存储（底层数组）**来实现队列，因为有空间大小，所以如果在前面的元素出栈后就会浪费掉前面的空间而要一直往后开辟空间，所以此时想一个方法：使得rear能够到达队头（也就是进行循环使用）；弹出一个元素，front就走到下一个位置
- （当front == rear时就是满了，但是有一个问题：当队列为空时也是front == rear —所以如何进行队列空与队列满的区分呢？
- 最后的解决方法：计数；另一种方法：浪费一个空间，也就是存储元素之前看一下rear的下一步是否为front，是就不进行元素存储
- 浪费空间方法的思路：
- 定义一个数组 + usedSize + 对头、队尾下标
（定义属性）- 构造方法初始化数组k
- 入队：千万不能rear++：因为进行循环时k++根本不可能到0 – 解决办法：加一模长度
首先要判满：写一个方法
（如果扩容，就要更新front和rear！！）- 判空
- 出队：判空+front的变化同样使用加一模
- 获取队头元素（不删除）：判空+获取
- 获取队尾元素（不删除）：应该有两种方法返回下标–三目表达式判断rear==0？ or rear+len-1模len
- 注意一个问题：如果使用浪费空间去做，就会比预期少放一个元素，解决办法就是初始化时放一个空间
最好的方法就是使用uesdSize （==0空，==len满）
- 代码实现：
1） 通过size属性进行记录：
public class MyCircularQueue {
// 定义数组 + usedSize
public int[] array;
public int usedSize;
// 定义队头、队尾的下标---注意这里所定义的只是下标而已！！！
public int front;
public int rear;
public MyCircularQueue(int k) {
// 进行数组初始化：数组前加一个this比较好！
//array = new int[k];
this.array = new int[k];
}
// 入队：判空+操作No!! == 其实是进行判满
public boolean enQueue(int value) {
/*if(isEmpty()) {
// 为空
this.front = value;
this.rear = value;
array[usedSize++] = value; // 先用后加
return true;
}else {
this.rear = value;
array[usedSize] = value;
usedSize = (usedSize+1) % array.length;
return true;
}
// 默认就是false*/
if(isFull()) {
// 如果要进行判满 就要变换队头和队尾
return false;
}
// 这里不对！！
/*this.array[front] = value;
this.array[rear] = value;*/
// 此处对队头不用赋值，因为此时rear==front，随便赋值一个就代表另一个也会被改变！！！
this.array[rear] = value;
// 赋值之后rear下标要有变化，但是不是直接++！！
// 注意：入队过程中：当入队完成后是rear往后挪动了一个下标位置！！！
this.rear = (this.rear+1)%array.length;
this.usedSize++;
return true;
}
// 进行出队（删除队头）
public boolean deQueue() {
//判空 + 操作
if(isEmpty()) {
// 空就返回-1
return false;
}
//这一步是错误的，因为这个操作其实只是给现在的队头重新赋值了而已，但是实际目的是：front下标走到下一个！！不管当前元素
//this.array[front] = array[(this.front+1) % array.length];
this.front = (this.front+1) % array.length; // 同样注意这里！
this.usedSize--;
return true;
}
// 拿到队头不删除
public int Front() {
// 注意判空！！
if(isEmpty()) {
return -1; // OJ上返回-1 其他可以抛异常！！
}
return this.array[front];
}
// 拿到队尾
public int Rear() {
// 注意判空！！
if(isEmpty()) {
return -1; // OJ上返回-1 其他可以抛异常！！
}
// 这里依旧是错误的
//return this.array[rear];
// 理由即修改如下：
// 注意：入队过程中：当入队完成后是rear往后挪动了一个下标位置！！！
// 所以拿到队尾是要让index在实际rear之前一位
int index = (rear==0)?(array.length-1):(rear-1);
return this.array[index];
// 或者是
// return this.array[(this.rear + array.length-1] % array.length)];
}
// 进行判空
public boolean isEmpty() {
return (0 == this.usedSize);
}
// 进行判满
public boolean isFull() {
return (array.length == this.usedSize);
}
// 进行大小查找
public int getSize() {
return this.usedSize;
}
// 模拟一个打印操作：实际上没有这个方法
public void print() {
for (int i=this.front; i<this.rear; i++) { //注意循环条件！！！不是从0开始！！！
System.out.print(this.array[i] + " ");
}
System.out.println();
}
}
2） 浪费空间的方法：
public class MyCircularQueue {
public int[] array;
public int front;
public int rear;
public MyCircularQueue(int k) {
array = new int[k+1]; // 为了满足实际需要的大小，k+1
}
// 入队
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
this.array[rear] = value;
this.rear = (this.rear+1)%array.length;
return true;
}
// 出队：删除队头
public boolean deQueue() {
if(isEmpty()) {
return false;
}
this.front = (this.front+1)%array.length;
return true;
}
// 获取队头
public int Front() {
if(isEmpty()) {
return -1;
}
return this.array[front];
}
public int Rear() {
if(isEmpty()) {
return -1;
}
// 一直都不会放满 但是所存储元素是够的一定
//int index = (rear==0)?(array.length-1):(rear-1);
//return this.array[index];
return this.array[(this.rear + array.length-1)% array.length];
}
public boolean isEmpty() {
return (this.front == this.rear);
}
public boolean isFull() {
return ((this.rear+1) % array.length ==this.front); // 浪费一个空间的做法
}
}
3） 使用标记（flag进行出入栈以及默认（还没开始操作）情况下的标记）
// 格外注意判空+判满的时候！！
public class MyCircularQueue {
public int[] array;
public int front;
public int rear;
public boolean flag; // 进行rear==front 的标记！！:意思就是说：入队成功就是true 出队成功就是false
// 则：入队成功+rear==front就是满了 出队+rear==front或者是默认的（也就是还没开始放）就是空的！！
public MyCircularQueue(int k) {
array = new int[k];
}
public boolean enQueue(int value) {
// 放元素
if(isFull()) {
return false;
}
this.array[rear] = value;
this.rear = (this.rear+1) % array.length;
// 成功入队：
flag = true;
return true;
}
public boolean deQueue() {
if(isEmpty()) {
return false;
}
this.front = (this.front+1) % array.length;
flag = false;
return true;
}
public int Front() {
if(isEmpty()) {
return -1;
}
return this.array[front];
}
public int Rear() {
if(isEmpty()) {
return -1;
}
return this.array[(this.rear+array.length-1)%array.length];
}
// 注意判空、判满的条件！！
public boolean isEmpty() {
// 空是：入队/没有操作(false)+相等！！
if((this.front==this.rear) && (!flag)) {
return true;
}
return false;
}
public boolean isFull() {
// 满是：入队+相等！！
if((this.front==this.rear)&&flag) {
return true;
}
return false;
}
}
三、双端队列（Deque）
- 双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
- Deque是一个接口，使用时必须创建LinkedList的对象。
即如：Deque deque = new LinkedList<>(); - Deque：双端队列：哪一边进都ok（但是必然是一端进栈另一端出栈）
四、面试题
1. 用队列实现栈
- 思路：
一个队列（先进先出）是不能实现栈（先进后出）的：所以使用两个队列来实现：入栈时入到不为空的队列中，然后出栈时，将所要元素之前的所有元素都出到另一个栈中（即：出已有元素size-1 个）
1）声明定义两个队列 + 构造方法进行初始化（new初始化的是两个队列！！注意new的对象！）+ usedSize
2）入栈push：if判断是否为空
3）出栈pop：判空 + qu1（队列1）默认选择 + for循环进行元素弹出（注意一点：size会变化，所以要使用一个临时变量
来记录size最初始的值！！）
4）查看栈顶元素top：类似出栈，只是循环是所有元素，然后要记录每次元素（即：需要一个变量空间记录每次拿到的元素），再把最后的元素进行return
5）判空：两种方式：一是usedSize，二是两个队列都是空&&
循环队列（此处使用LinkedList来初始化对象）一般不用考虑栈满情况，所以不进行判满操作）
（注意点：OJ写题时不要进行异常抛出，而是返回-1）
时刻注意usedSize要进行变化！！
- 代码：
class MyStack {
// 声明定义两个队列
Queue<Integer> queue1;
Queue<Integer> queue2;
// 定义usedSize
public int usedSize;
// 初始化栈! 错误！！！
// 初始化的是 两个队列！！
public MyStack() {
// MyStack myStack = new MyStack();
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
// 注意new的对象！！！
}
// 入栈：判空+入到不为空的队列里
public void push(int x) {
// 注意队列出栈使用的方法！！
// 注意：但是此时代码有问题：size是会变化的！！！
// 创建临时变量，但是创建在每个所需要的内部就行
// 判空-- 队列判空+注意入到非空中，若是都空则入到默认1中！！
if (!queue1.isEmpty()) {
queue1.offer(x);
} else if (!queue2.isEmpty()) {
queue2.offer(x);
} else {
// 都为空 则默认选择queue1
queue1.offer(x);
}
usedSize++;
}
// 出栈：则将队列中的（元素-1）个移到另一个队列中
// 哪个队列不为空就出哪个
public int pop() {
// 判空
if(empty()) {
return -1; // OJ一般不能抛出异常
}
// 来到这儿就说明不为空！
if(!queue1.isEmpty()) {
// 不空就弹出size-1个元素
//for (int i = 0; i < queue1.size()-1; i++) {
// 所以创建临时变量
int curSize = queue1.size();
for (int i = 0; i < curSize-1; i++) {
queue2.offer(queue1.poll()); // 弹出并删除
}
usedSize--;
return queue1.poll();
} else {
// 不空就弹出size-1个元素
//for (int i = 0; i < queue2.size()-1; i++) {
int curSize = queue2.size(); // 注意细节！
for (int i = 0; i < curSize-1; i++) {
queue1.offer(queue2.poll()); // 弹出并删除
}
usedSize--;
return queue2.poll();
}
}
// 获取栈顶元素：不删除--需要一个中间过渡的变量空间
public int top() {
// 其实主要方法类似于删除栈顶元素pop
// 设置一个过渡的变量
int ret = -1;
// 判空
if(empty()) {
return -1; // OJ一般不能抛出异常
}
// 来到这儿就说明不为空！
if(!queue1.isEmpty()) {
// 不空就直接将size个元素放到另一个队列中
// 所以创建临时变量
int curSize = queue1.size();
for (int i = 0; i < curSize; i++) {
ret = queue1.poll(); // 弹出并删除
queue2.offer(ret);
}
return ret;
} else {
int curSize = queue2.size();
for (int i = 0; i < curSize; i++) {
ret = queue2.poll(); // 弹出并删除
queue1.offer(ret);
}
return ret;
}
}
// 判空：判断栈中是否为空
public boolean empty() {
return (usedSize==0);
}
// 判空：判断栈中是否为空方法2
public boolean empty2() {
return (queue1.isEmpty()&&queue2.isEmpty());
}
}
2. 用栈实现队列
- 思路：
用一个栈实现队列：NO！ 同样的方法：两个栈实现一个队列
第一个栈是专门进元素的，第二个栈是专出元素的！当第二个栈（即出的）为空时就将第一个栈的元素都出
到第二个栈中
1）声明两个栈
2）入队push：直接压入
3）出队pop：判空+判断第二个栈是否为空
4）peek：都放过来I+peek（注意不是pop）
5）判空：两个都为空
- 代码：
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() {
//缺少一个完整判空：空则返回-1
if(empty()) {
return -1;
}
// 判出的栈空
if(stack2.empty()) {
// 如果使用size（） 同样要注意的是：size会变化，所以应该使用临时变量！
int curSize = stack1.size();
//for (int i = 0; i < stack1.size(); i++) {
for (int i = 0; i < curSize; i++) {
stack2.push(stack1.pop());
}
/*
// 直接用while循环
while (!stack1.empty()) {
stack2.push(stack1.pop());
}*/
}
return stack2.pop();
}
// 拿到顶但不删除
public int peek() {
if(empty()) {
return -1;
}
//来到这儿需要再判断2是否为空，空才要进行1倒过来到2
if(stack2.empty()) {
// 直接用while循环
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
// 判空：直接判断两个栈是否为空就行
public boolean empty() {
return (stack1.empty() && stack2.empty());
}
}
3. 实现一个最小栈
- 思路：
今日头条考过一次
在常数时间内找到最小值，也就是说时间复杂度O(1)
思路：如果是使用一个栈去实现的，时间复杂度必然不满足，所以再有一个栈minStack专门用来保存最小值：这里的意思其实就是在普通栈中存放完元素之后的最小值（新压入的元素与最小栈中的栈顶元素比较，小于就压入最小栈；出栈时，除了出普通栈的最小元素外，还要和最小栈的栈顶元素比较，如果相等则同样需要出最小栈的栈顶元素，这样才能保证最小元素就是在最小栈的栈顶。
- 注意最小栈中存的元素其实是：在普通栈中存完当前元素之后，与最小栈的栈顶元素比较，若小就压入最小栈
弹出最小元素：当我们需要出栈的时候，除了出普通栈的元素外，还要和最小栈的栈顶元素比较，如果相等则最小栈栈顶元素也出，以保证每次获取的最小值都在最下栈栈顶！（如果普通栈所出的元素与最小栈不相等，则继续出普通栈元素，即：说明此时并不是最小值）- 入栈注意：入栈时不仅要使得元素进入普通栈，还要让普通栈的元素<=最小栈栈顶元素的进入最小栈
- 代码：
class MinStack {
// 两个栈声明
Stack<Integer> stack; // 普通栈
Stack<Integer> minStack; //最小栈
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
// 入栈：需要判断最小栈是否为空&&val与最小栈栈顶元素大小
public void push(int val) {
// 一定进入普通栈
stack.push(val);
// 判断最小栈是否为空
if(minStack.empty()) {
// 注意这里如果最小栈为空则直接装入元素！
minStack.push(val);
} else {
int peekMin = minStack.peek(); // 获取最小栈栈顶元素（即：最小值）
if(val <= peekMin) {
minStack.push(val);
}
}
}
// 出栈：删除普通栈的栈顶:如果普通栈与最小栈栈顶元素相等，
// 则最小栈栈顶元素也要出，不等就不用出，保证寻找最小值的正确性
// 普通栈要判空：如果普通栈都为空，那么最小栈也一定为空
public void pop() {
// 普通栈判空
// 只要普通栈不为空 最小栈一定不为空：因为二者最后都是一样的元素
if(!stack.empty()) {
// 普通栈一定出元素
int popVal = stack.pop();
//与最小栈栈顶元素进行比较
int peekMin = minStack.peek();
if(popVal == peekMin) {
minStack.pop();
}
}
}
// 获取普通栈栈顶元素：直接弹出但不删除！:所以与最小栈无关
// 判空
public int top() {
if(stack.empty()) {
return -1;
}
// 来到这儿就是不空
return stack.peek();
}
// 获取最小值（常数时间）--也就是最小栈栈顶元素
// 但是注意：是获取但是不删除，所以用peek！
public int getMin() {
if(minStack.empty()) {
return -1;
}
// return minStack.pop();
return minStack.peek();
}
public static void main(String[] args) {
System.out.println("测试：");
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
System.out.println(minStack.getMin());
minStack.pop();
System.out.println(minStack.top());
System.out.println(minStack.getMin());
}
}
THINK
- 区分队列和栈：队列先进先出，栈先进后出
- 区分队列和栈的初始化方式：队列LinkedList，栈直接Stack
- 队列面试题
- 双端队列
本文含有隐藏内容，请 开通VIP 后查看