Timeline for What's the point of implementing a Stack using two queues?
Current License: CC BY-SA 3.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:40 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Jun 19, 2015 at 4:51 | history | unprotected | gnat | ||
| Jun 17, 2015 at 20:55 | comment | added | user541686 | (...cont'd) If you think about the uses of priority queues, it is generally true (i.e., there exists a statistical trend) that those enqueued later are still dequeued later than those enqueued earlier. For example, breadth-first-search is an approximation to Dijkstra's algorithm in many cases, even though in particular instances it might not be a great approximation. A stack is never any kind of approximation to a queue. It has precisely the opposite behavior in every situation, so calling it a queue is completely nonsensical. | |
| Jun 17, 2015 at 20:50 | comment | added | user541686 | The whole point of a queue is that your enqueue time should have some vague sort of inverse correspondence with your dequeue time. In other words, with any kind of queue, given no additional information, then your best guess is that those enqueued later will be dequeued later. Sure, it might not be 100% accurate, but "queue" still (statistically) describes the overall trend. But with a stack, which exactly behaves in the opposite fashion, this is strictly the worst possible guess--at that point, it bears exactly zero resemblance to a queue. (That's 0%! Not even 1%!) | |
| Jun 17, 2015 at 20:43 | comment | added | Carcigenicate | @Mehrdad That's not a correct way of thinking about it. A Priority queue is a queue and it's not FIFO (as in you bathroom example). If I implemented a stack using a priority queue where the element's order was based on insertion time, would that not be a queue? | |
| Jun 17, 2015 at 20:10 | history | protected | gnat | ||
| Jun 17, 2015 at 20:10 | comment | added | user541686 | @yoniLavi: I don't disagree that it's popular nomenclature, but that doesn't imply it makes any sense. A calling a stack a "LIFO queue" makes as much sense as calling ethernet "wired Wi-Fi". | |
| Jun 17, 2015 at 20:00 | comment | added | yoniLavi | @Mehrdad, referring to a stack as a type of queue is not nonsensical, it uses the general definition given in Queueing Theory as any method used by a system with limited resources to prioritize access to those resources to elements waiting in line. | |
| Jun 17, 2015 at 13:17 | answer | added | The Spooniest | timeline score: 1 | |
| Jun 17, 2015 at 12:13 | comment | added | Ian | Anyone that can write this code and answer a few questions on their code clearly understands queue and stacks, hence a very good task to help students build the understanding. | |
| Jun 17, 2015 at 7:25 | comment | added | user541686 | "A stack is a (LIFO) queue"... uhm, a queue is a waiting line. Like the line for using a public restroom. Do the lines you wait in ever behave in a LIFO fashion? Stop using the term "LIFO queue", it's nonsensical. | |
| Jun 17, 2015 at 3:22 | comment | added | slebetman | @MichaelT: Or you can also find yourself running on a stack based CPU | |
| Jun 17, 2015 at 2:04 | comment | added | user40980 | Building off what Eric said, you can sometimes find yourself in a stack based language (such as dc or a push down automaton with two stacks (equivalent to a turing machine because, well, you can do more)) where you may find yourself with multiple stacks, but no queue. | |
| Jun 17, 2015 at 0:21 | comment | added | Eric Lippert | The more usual problem is to implement a queue using two stacks. You might find Chris Okasaki's book on purely functional data structures interesting. | |
| Jun 16, 2015 at 22:32 | answer | added | Rob | timeline score: 6 | |
| Jun 16, 2015 at 21:53 | vote | accept | Carcigenicate | ||
| Jun 16, 2015 at 21:48 | history | edited | Carcigenicate | CC BY-SA 3.0 |
edited body
|
| Jun 16, 2015 at 21:47 | answer | added | Thraidh | timeline score: 3 | |
| Jun 16, 2015 at 21:14 | history | tweeted | twitter.com/#!/StackProgrammer/status/610918388437749761 | ||
| Jun 16, 2015 at 20:26 | comment | added | Carcigenicate |
Yes, I realized that I'm using "illegal operations" for the question. I literally reversed every push/pop (front for back) so I'm only using legal methods, and it operates the same. I don't know if I should update the code since it's mostly besides the question.
|
|
| Jun 16, 2015 at 20:25 | history | edited | user40980 | CC BY-SA 3.0 |
Spell out small numbers. queues doesn't need an grocer's apostrophe (see https://en.wikipedia.org/wiki/Apostrophe#Superfluous_apostrophes_.28.22greengrocers.E2.80.99_apostrophes.22.29 ).
|
| Jun 16, 2015 at 20:20 | answer | added | amon | timeline score: 21 | |
| Jun 16, 2015 at 20:19 | answer | added | Destruktor | timeline score: 3 | |
| Jun 16, 2015 at 20:13 | answer | added | user22815 | timeline score: 46 | |
| Jun 16, 2015 at 20:12 | comment | added | user40980 | A queue is typically referring to a FIFO structure while the stack is a LIFO structure. The interface for LinkedList in Java is that of a deque (double ended queue) which allows both FIFO and LIFO access. Try changing programming to the Queue interface rather than the LinkedList implementation. | |
| Jun 16, 2015 at 20:05 | history | asked | Carcigenicate | CC BY-SA 3.0 |