是否可以在不使用 2 个堆栈的情况下在 C 中创建一个 FIFO“堆栈”？
谢谢！
（对不起那些回答前一个问题的人。我在想 LIFO，意思是 FIFO。）
Tyler
问问题
14650 次
7 回答
4
这很容易。只需实现一个双向链表，保存指向列表中最后一项的指针。
要添加到队列中，请在开头创建一个新节点，将其链接到前一个开头。（正常列表插入）
要从队列中删除，请取消指向最后一项的指针，将指针更改为前一项指针，然后返回最后一项......（这就是双向链表的原因。另一个选项是单链表list 并迭代整个列表以获取指向最后两个元素的指针）。
于 2009-01-30T22:20:31.407 回答
2
听起来您正在尝试创建一个队列，在其中插入一端并从另一端拉出。
一种方法是使用链表。您可以存储指向头部和尾部的指针。当你插入时，将新记录附加到尾部，当你从队列中弹出一些东西时，你抓住头指针指向的节点。（反之亦然，没关系）
于 2009-01-30T22:20:45.103 回答
2
这不只是一个标准的链表，除了你只定义函数来拉出头元素并将东西推到尾元素上吗？您甚至可以在带有尾指针的单链表中执行此操作，而不是在完全双向链表中。
于 2009-01-30T22:21:06.397 回答
1
为此使用 2 个堆栈是一个有趣的解决方案，而且是一个缓慢的解决方案。当您可以使用普通队列时，为什么要提到堆栈？这是你想要的先进先出，对吧？您可以使用数组来创建队列，并对其长度进行取模以使其成为圆形。
于 2009-01-30T22:20:39.143 回答
1
您还可以使用循环数组实现队列。
于 2009-01-30T22:39:07.623 回答
1
尽管已经提出了正确的解决方案，但我只想纠正 FIFO 并不是真正的堆栈。
这个问题经常出现在算法课上，他们要求你使用堆栈构建一个，并证明插入和移除的摊销成本是 O(1)。
可以使用双向链表、带有开始和结束指针的数组/向量、循环数组等来构建 FIFO。
于 2009-01-31T01:04:56.753 回答
0
我认为 OP 想知道如果他所拥有的只是堆栈，无论出于何种神秘原因，如何处理它。诀窍是记住将东西压入堆栈然后将其弹出会颠倒项目的顺序，因此您可以使用两个堆栈来反转它两次。
传入的项目被推到 stack1 上，并且当 stack2 为空时全部弹出到 stack2 上。所以第一个项目被推入stack1，立即弹出并推入stack2，准备输出。后续项在 stack1 上堆叠，直到 stack2 弹出，此时最后一项在 stack2 上，然后是倒数第二项，依此类推，直到 stack1 再次为空。现在所有项目都重新堆叠在 stack2 上，最新的在底部，最旧的在顶部。新的推送继续在 stack1 上建立，等待 stack2 再次变空，stack2 只是按照原始顺序生成项目，直到它为空，此时我们重复 unstack-restack 过程。
我不会评论效率等；只是“你可以那样做”。我在一次采访中被问到这个问题，我的直接回答是“什么样的白痴会这样做？只需实现一个实际的队列并完成它” - 我认为这不是他们正在寻找的答案。
于 2009-01-30T23:09:15.473 回答