Timeline for What's the point of implementing a Stack using two queues?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17, 2015 at 14:23 | comment | added | Voo | "horrible time complexity" and "vastly inferior" is not exactly right. Amortized complexity is still O(1) for push and pop. There's a fun question in TAOCP (vol1?) about that (basically you have to show that the number of times an element can switch from one stack to the other is constant). Worst case performance for one operation is different, but then I rarely hear anybody talking about O(N) performance for push in ArrayLists - not the usually interesting number. | |
| Jun 17, 2015 at 8:34 | history | rollback | amon |
Rollback to Revision 1
|
|
| Jun 17, 2015 at 8:34 | comment | added | amon |
@JohnKugelman Thanks for your edit, but I really meant “horrible time complexity”. For a linked-list-based stack push, peek and pop operations are in O(1). The same for a resizeable array-based stack, except that push is in O(1) amortized, with O(n) worst case. Compared with that, a queue-based stack is vastly inferior with O(n) push, O(1) pop and peek, or alternatively O(1) push, O(n) pop and peek.
|
|
| S Jun 17, 2015 at 1:29 | history | suggested | John Kugelman | CC BY-SA 3.0 |
The time complexity is the same, since O(2n) = O(n). Changed "horrible time complexity" to "inefficient".
|
| Jun 16, 2015 at 21:58 | review | Suggested edits | |||
| S Jun 17, 2015 at 1:29 | |||||
| Jun 16, 2015 at 20:20 | history | answered | amon | CC BY-SA 3.0 |