Given a sequence of enqueue and dequeue operations, return a result of their execution without using a queue data structure.
Operations are given in the form of a linked list:
● A non-negative integer means “enqueue me”.
● -1 means
○ If the queue is not empty, dequeue the current head and append it to the result.
○ If the queue is empty, append -1 to the result.
Result is a linked list.
Use two stacks as an auxiliary data structure. Using a queue isn’t allowed.
Input: 1, -1, 2, -1, -1, 3, -1
Output: 1, 2, -1, 3
Here is how we would execute the operations and build the result list:
Input: 0, 1, 2, -1, 3
The only dequeue operation results in the first enqueued element, 0, to be appended to the result list.
Input Parameters: Function has one argument: operations (singly linked list of integers of length N).
Output: Function must return a singly linked list of integers.
● There will be at least one dequeue (-1) operation.
Any time we process an operation that puts a number to the queue, we need to store it somewhere. We are only allowed to use stacks to store numbers, so let’s be pushing all enqueued numbers into stack1.
Any time an operation tells us to retrieve a number from the queue, that number would be at the bottom of stack1 then. To access it we’d need to pop all the numbers from there. Luckily we are allowed to use another stack. So we can temporarily push all the numbers into stack2 and access the desired number from the bottom of stack1. After that we can push all the remaining numbers back from stack2 to stack1. They will end up being in the same order as they were there before the dequeue operation, and that works for us.
brute_force_solution.cpp uses this algorithm. What about its complexity?
O(N^2) for processing all N operations. Every dequeue operation requires moving around all the numbers so far enqueued, that makes the dequeue operation O(N).
Auxiliary Space Used:
O(N) since we never store more than N numbers.
O(N). Input, output and temporary data structures are all O(N) so O(N) + O(N) + O(N) = O(N).
Let’s imagine that we started with the brute force solution described above and came to this situation:
stack1 = [1, 2, 3], stack2 = , next operation: -1
To dequeue, we move all numbers from stack1 to stack2:
stack1 = , stack2 = [3, 2], add append number 1 to the result.
Now we can notice that stack2 has all the remaining numbers in the order that’s perfect for us. For example, if the next operation is -1, we can simply pop and return number 2 from stack2 - a constant time operation.
We can dequeue elements this way if we leave them in stack2, but what about enqueueing new ones? It turns out that we can push them in stack1, and they can remain there until stack2 is empty. Once stack2 is empty and another dequeue operation comes, we can do what was described two paragraphs ago: pop all numbers from stack1 and push them into stack2.
optimal_solution.cpp uses this algorithm.
Enqueue operation takes constant time, clearly. Let us examine dequeue operation.
Most dequeue operations will just need to pop one number from stack2, that’s constant time. Some dequeue operations however will need to move some numbers from stack1 to stack2.
Amortized time complexity of the dequeue operation is constant and intuitively we can observe that we never move any given number more than once between stack1 and stack2 (that’s constant time per number).
Overall time complexity of the algorithm would be O(N) since we process N operations, taking constant time per operation (amortized).
Auxiliary Space Used:
O(N) as we never store more than N numbers in our stacks.