使用队列伪代码实现堆栈 [英] Implementing stack using a queue pseudocode

问题描述

我对以下伪代码感到困惑

I am confused on the following pseudocode

■ 使用单个队列实现堆栈.具体写使用 enqueue 对堆栈进行推送和弹出操作的伪代码和队列的出队操作.考虑给定队列类给你.我们将使用单个队列 q.考虑队列的前端是栈顶

■ Implement a stack using a single queue. Specifically, write pseudocode for push and pop operations on a stack using enqueue and dequeue operations of queue. Consider the queue class is given to you. We will use a single queue q. Consider the front of the queue is the top of the stack

推(x)

s   =   q.size()
q.enqueue(x)
for(int i = 0;  i < s;  i++)
q.enqueue(q.dequeue())

pop()
if  q.isEmpty()
"Exception"
return  q.dequeue()

我意识到堆栈的底部是队列的后面.所以当我们入队时，它必须排在栈底.因此，我们必须从堆栈中移除所有内容并将该项目推入，然后将所有内容放回原处.我不明白 "for(int i = 0; i < s; i++)q.enqueue(q.dequeue())" 我认为这符合我所说的，但有人可以引导我完成它吗?谢谢！

I realize that the bottom of the stack is the back of the queue. So when we enqueue, it has to go at the bottom of the stack. So we must remove everything from the stack and push that item in, then put everything back. I do not understand the "for(int i = 0; i < s; i++) q.enqueue(q.dequeue())" I assume this does what i am talking about but can someone walk me through it? Thank you!

推荐答案

假设您已经添加了 3 个值:

Let's say you have already added 3 values:

6  7  8

如果是队列，只能在左边添加，只能在右边取.

With a queue, you can only add on the left, and only take on the right.

有了栈，你想在右边加，在右边取，即目标是在右边加上下一个值(9)，像这样:

With a stack, you want to add on the right, and take on the right, i.e. the goal is to add the next value (9) on the right, like this:

6  7  8  9

但是，对于队列，您只能在左侧添加:

But, with a queue, you can only add on the left:

9  6  7  8

所以您想要做的是使用有效的队列操作从右到左循环预先存在的值(6 7 8)，一次一个:

So what you want to do, is cycle the preexisting values (6 7 8) from the right to the left, one at a time, using valid queue actions:

┌─> 8  9  6  7 ─┐
└───────────────┘

┌─> 7  8  9  6 ─┐
└───────────────┘

┌─> 6  7  8  9 ─┐
└───────────────┘

因此，要对 预先存在的 值执行此操作，在添加新值之前 取队列的大小，然后添加新值，然后移动最后一个值根据需要预先设置多次，即 size 次.

So, to do that for the preexisting values, you take the size of the queue before adding the new value, then add the new value, and move last value up front as many times as needed, i.e. size times.

这篇关于使用队列伪代码实现堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！