使用两个队列实现堆栈
使用两个队列实现堆栈
提问于 2009-03-27 02:07:34
早些时候也提出了类似的问题。there，但这里的问题与之相反，使用两个队列作为堆栈。问题是..。
给定两个队列及其标准操作(enqueue，dequeue，isempty，size)，用它的标准操作实现一个堆栈(pop，push，isempty，size)。
应该有两个解决方案的版本。
- 版本A：在推送项目时，堆栈应该是有效的；以及
- 版本B：当弹出一个项目时，堆栈应该是有效的。
与任何特定的语言实现相比，我对算法更感兴趣。但是，我欢迎用我熟悉的语言表达的解决方案(java,c#,python,vb,javascript,php)。
回答 25
Stack Overflow用户
回答已采纳
发布于 2009-03-27 02:17:52
版本A(高效推送)：
- 推送：
在queue1中入队
- 流行：
当queue1的大小大于1时，将从queue1出列的项目输送到queue2
出列并返回queue1的最后一项，然后切换queue1和queue2的名称
版本B(高效pop)：
- 推送：
在queue2中入队
将queue1的所有项都放入queue2中，然后切换queue1和queue2的名称
- 流行：
从queue1排队
Stack Overflow用户
发布于 2009-03-27 02:20:05
最简单(也可能是唯一的)方法是将新元素推入空队列，然后将另一个元素从队列中取出，并将其排入先前的空队列中。通过这种方式，最新的总是排在队列的前面。这将是版本B，对于版本A，您只需通过将除最后一个以外的元素出列到第二个队列中来逆转该过程。
步骤0：
"Stack"
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+步骤1：
"Stack"
+---+---+---+---+---+
| 1 | | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| 1 | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+步骤2：
"Stack"
+---+---+---+---+---+
| 2 | 1 | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| | | | | | | 2 | 1 | | | |
+---+---+---+---+---+ +---+---+---+---+---+步骤3：
"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| 3 | 2 | 1 | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+Stack Overflow用户
发布于 2011-09-06 12:19:06
我们可以用一个队列做到这一点：
推送：
- 将新元素入队。
- 如果
n是队列中元素的数量，然后删除并插入元素n-1时间。
流行：
- 出队。
push 1
front
+----+----+----+----+----+----+
| 1 | | | | | | insert 1
+----+----+----+----+----+----+
push2
front
+----+----+----+----+----+----+
| 1 | 2 | | | | | insert 2
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | 2 | 1 | | | | remove and insert 1
+----+----+----+----+----+----+
insert 3
front
+----+----+----+----+----+----+
| | 2 | 1 | 3 | | | insert 3
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | | 1 | 3 | 2 | | remove and insert 2
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | | | 3 | 2 | 1 | remove and insert 1
+----+----+----+----+----+----+示例实现：
int stack_pop (queue_data *q)
{
return queue_remove (q);
}
void stack_push (queue_data *q, int val)
{
int old_count = queue_get_element_count (q), i;
queue_insert (q, val);
for (i=0; i页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/688276
复制相关文章
相似问题