如果使用数组实现,我可以看到使用两个堆栈的优点,因为使用数组比堆栈更容易实现堆栈。 但是,如果使用链表,优势是什么? 将栈弹出到队列中的行为增加了链接列表和数组实现的开销。为什么使用两个堆栈来创建一个队列?
回答
这是实现在函数式编程语言队列单纯的功能性的常用方法(不可变的,但在共享结构)列表(例如Clojure中,哈斯克尔,二郎...):
- 用一双名单代表第一个列表中的元素处于FIFO顺序并且第二个列表中的LIFO顺序的队列
- 通过预先考虑到第二个列表排队到队列
- 通过取出队列中的第一个元素列表
- 如果第一个列表为空:反转第二列表,并与它代替第一列表中,并用一个空列表
更换第二列表
(所有的操作除了任何可能的返回值返回新的队列对象)关键是将一个元素添加到(从)一个纯函数列表的前面是O(1),而反向操作是O(n)在所有出列处被分摊,所以它接近于O( 1),从而为您提供一个具有不可变数据结构的队列实现。
第二步,我相信最后一个单词应该是'list'而不是'queue',使它像'通过预先考虑第二个列表入队到队列中。] – 2014-05-27 09:41:43
谢谢@LihangLi,修正了! – liwp 2014-05-27 09:50:12
这是一个很好的学习经验,但不是一个实际的。
您可以使用两个不可变的堆栈来创建一个不可变的队列。
但是,如果你只是想要一个可变队列,使用两个栈是一个很好的方式,使它比使用链表更慢和更复杂。
此方法可用于使用两个原子单链表基于堆栈构建lock-free队列,如由Win32提供的:Interlocked Singly Linked Lists。 该算法可能如liwp's answer中所述,尽管重新打包步骤(第4项)可以进行一些优化。
无锁数据结构和算法是一个非常令人兴奋的(对我们一些人)编程领域,但它们必须非常小心地使用。在一般情况下,基于锁的算法效率更高。
在一个多写入器的单个阅读器的情况下,很容易以高效的无锁方式处理“入队”操作,同样对于出列(无需锁定写入者,并假设一个读取器)如果一个人通过收件箱中的“全部弹出”操作(基本上是一个'Interlocked.Exchange')开始出列,如果可能有多个读者,最好让他们使用锁定在彼此之间进行仲裁(他们的锁定会'不会影响作家) – supercat 2012-09-25 22:09:01
这是我来这里寻找的解释,有一个好的先生。 – 2017-05-01 14:30:51
- 1. 从两个堆栈创建队列
- 2. 在两个堆栈队列中创建一个toString
- 3. 使用两个堆栈的队列
- 4. 使用堆栈两个队列
- 5. 你会用什么来实现两个堆栈队列?基于数组的栈或链表栈?怎么样两个队列堆栈?
- 6. 堆栈和队列,为什么?
- 7. 创建一个通用堆栈阵列
- 8. 如何实现两个堆栈队列
- 9. Java:用一个队列实现堆栈,有什么问题?
- 10. 我该如何为一个队列或堆栈使用两个C结构?
- 11. 使用2个队列实现堆栈
- 12. 尝试使用堆栈创建队列。为什么我得到一个无效的int转换错误?
- 13. 什么创建堆栈?
- 14. 为什么我们在Java中使用堆栈和队列?
- 15. 使用C中的两个堆栈实现队列
- 16. 使用两个堆栈实现队列奇怪的错误
- 17. 使用队列堆栈
- 18. C++堆栈/堆栈。为什么只有一个新操作员?
- 19. 将一个值从一个队列移动到一个堆栈
- 20. 连接两个堆栈(在另一个上面一个堆栈)
- 21. 使用只有一个堆栈实现优先级队列
- 22. StackedAndGroupedColumn系列值为这两个堆栈
- 23. 为什么队列和堆栈被声明为指针?
- 24. 队列+堆栈C++
- 25. iOS4创建两个UIActionSheets,3.1.3创建一个?为什么?
- 26. 使用两个变体创建堆栈值
- 27. 创建一个行堆栈算法
- 28. 创建一个Deck类扩展堆栈
- 29. 创建一个新的堆栈操作
- 30. Qt:创建一个图像的堆栈
谁使用两个堆栈来创建队列?我不太了解情况(对不起( – helios 2010-01-12 15:42:22