当前位置：首页 > news >正文

【数据结构】队列篇| 超清晰图解和详解：循环队列模拟、用栈实现队列、用队列实现栈

news 2025/6/26 23:41:00

在这里插入图片描述

博主简介：努力学习的22级计算机科学与技术本科生一枚🌸
博主主页： @是瑶瑶子啦
每日一言🌼: 每一个不曾起舞的日子，都是对生命的辜负。——尼采

一、模拟实现循环队列

🔗622. 设计循环队列
在这里插入图片描述

👧🏻思路：
🍊数据结构：使用数组为数据结构，且采用牺牲一个空间的方法来包装判空和判满的不同。
- 判空：Q.rear == Q.front
- 判满：Q.rear.next == Q.front/(rear+1)%size == front(满的时候可以看上图，此时rear指向的空间浪费掉了）

⭐这里就要注意，因为是浪费一个空间来判满的，所以比如我们需要一个容量为k的循环队列，那么实际的物理容量应该设计为k+1个！！！（这题在下面代码有体现，否则只能存k-1个）！

🍊头尾指针含义（重点）
- font:指向队头元素
- rear:下一个待插入元素的位置
🦆
🙇🏻‍♀️代码：

class MyCircularQueue {int[] myCircularQueue;int front = 0;int rear = 0;int size = 0;//构造函数，创建一个循环队列public MyCircularQueue(int k) {this.size = k+1;//!注意，这里需要+1this.myCircularQueue = new int[size];}//入队操作public boolean enQueue(int value) {if (isFull()){return false;}myCircularQueue[rear] = value;rear = (rear+1)%size;return true;}//出队操作public boolean deQueue() {if(isEmpty()){return false;}front = (front + 1)%size;return true;}//读取队头元素（注意判空）public int Front() {if(isEmpty()){return -1;}return myCircularQueue[front];}//读取队尾元素（注意判空）public int Rear() {if(isEmpty()){return -1;}return myCircularQueue[(rear - 1 + size) % size ];}//判空public boolean isEmpty() {if(front == rear){return true;}return false;}//判满public boolean isFull() {if((rear+1)%size == front){return true;}return false;}
}/*** Your MyCircularQueue object will be instantiated and called as such:* MyCircularQueue obj = new MyCircularQueue(k);* boolean param_1 = obj.enQueue(value);* boolean param_2 = obj.deQueue();* int param_3 = obj.Front();* int param_4 = obj.Rear();* boolean param_5 = obj.isEmpty();* boolean param_6 = obj.isFull();*/

二、用栈实现队列⭐

🔗232. 用栈实现队列
在这里插入图片描述

👧🏻思路：
- 若只有一个栈stack1，是不可能实现队列的，它可以实现在“队尾”入队，但不能实现拿到队头元素
- 于是我们需要一个辅助的中转栈stack2，把stack1的元素依次放入，再通过stack2.peek，间接取得队头元素
  
  此时两个栈一起便实现了队列。（注意，当stack2为空时，及时把stack1的元素挪过去！）
🙇🏻‍♀️代码：

class MyQueue {Stack<Integer> stack1;Stack<Integer> stack2 ;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}/** 添加元素到队尾 */public void push(int x) {stack1.push(x);}/** 将stack1的元素挪到stack2 */public void stack1ToStack2(){while(!stack1.empty()){stack2.push(stack1.pop());}}/** 删除队头的元素并返回 */public int pop() {if(stack2.empty()){stack1ToStack2();}return stack2.pop();}/** 返回队头元素 */public int peek() {if(stack2.empty()){stack1ToStack2();}return stack2.peek();}/** 判断队列是否为空 */public boolean empty() {return stack1.empty() && stack2.empty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

三、225. 用队列实现栈

🔗225. 用队列实现栈

在这里插入图片描述

👧🏻思路：
- 一个队列实现栈的问题在于：可以像栈一样正常入栈，但是队列的话只能拿到栈底元素，无法拿到栈顶（队尾）元素。
- 为了解决这个问题，关键是，如何在正常入栈操作的基础上，让新添加元素（即栈顶元素处于队头位置，这才可以始得每次出队列（出栈）拿到的是最新添加的栈顶元素。
方法1：单个队列实现
即每次加入新元素后，把新元素前面的元素顺次弹出，排到该元素后面，即可让新元素成为队头元素，即栈顶元素。这样就保证队头元素为栈顶元素。
🙇🏻‍♀️代码：

class MyStack {Queue<Integer> queue;public MyStack() {queue = new LinkedList<>();}public void push(int x) {//先直接添加queue.offer(x);//将新元素（栈顶元素）前的所有元素顺次移到栈顶元素之后for (int i = 0; i < queue.size() - 1; i++){queue.offer(queue.poll());}}public int pop() {return queue.poll();}public int top() {return queue.peek();}public boolean empty() {return queue.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

方法2：双队列实现
本质和单队列是一样的，实现栈的队列是queue1,只不过在添加新元素之前，把新元素放在空的辅助队列queue2中——使之处于队头（栈顶），然后将queue1中的元素顺次移入，此时再把queue1和queue2互换即可（脱裤子放屁的感觉，和方法一基本上是一样的）

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<Integer>();queue2 = new LinkedList<Integer>();}public void push(int x) {queue2.offer(x);while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}public int pop() {return queue1.poll();}public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}