- 博主简介：努力学习的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;//!注意，这里需要+1
this.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();
}
}
💐若有疑问的地方，欢迎随时在评论区or私信找瑶瑶子交流讨论🌺
-
Java岛冒险记【从小白到大佬之路】
-
LeetCode每日一题–进击大厂
-
Go语言核心编程
文章来源：https://www.toymoban.com/news/detail-681798.html -
算法文章来源地址https://www.toymoban.com/news/detail-681798.html
到了这里，关于【数据结构】队列篇| 超清晰图解和详解：循环队列模拟、用栈实现队列、用队列实现栈的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
