Search code examples
data-structureslinked-listqueuestack

What is the point of "Two Stack based Queues"?


I've seen queues implemented (in books and computer science classes) using 2 stacks (inbound and outbound). In this kind of data structure, when we pop data from the queue (dequeue), we first push everything from the impound stack to the outbound stack and then pop the data from the outbound stack.

So if we have n elements in the queue and we want to remove the first element, we must first do n push operations. This makes the time complexity of the dequeue operation O(n).

Where are these kinds of queues used? Why would you implement it like this instead of just using a single singly linked list (time complexity of O(1) for insert and remove)?


Solution

  • when we pop data from the queue (dequeue), we first push everything from the impound stack to the outbound stack and then pop the data from the outbound stack.

    That is incorrect. Fun thing, a question was asked recently on stackoverflow by someone who was confused by this as well. We only push stuff from the inbound stack to the outbound stack if the outbound stack is empty. If you push too soon, then the order of elements will be mixed up.

    So the dequeue operation has complexity O(n) in the worst case, and in environments where amortised analysis makes sense, it has amortised complexity O(1). In simpler words: you'll be moving n elements every n dequeue operations, so each dequeue operation takes only one move on average, even though from time to time a dequeue operation will be much slower.

    But you're right that this is still a drawback of this implementation, and in fact I think this two-stack implementation is much rarer in practice than other implementations. However, note that stacks are not necessarily implemented as linked-lists. In many contexts they are implemented using dynamic arrays.

    In a context where stacks are implemented as linked lists, then you are completely right: it doesn't make much sense to implement a queue as two stacks rather than as a simple linked list.