Implement a queue using stacks.
This uses two stacks to represent a queue, one for the enqueueing operation and another for the dequeuing operation.
All elements are transferred from one stack to another any time the queue operation switches. In other words, if the current operation is enqueue and the previous operation was dequeue, then all elements must first be transferred to the enqueue stack before the current element can be added. Likewise, if the current operation is dequeue and the previous operation was enqueue, then all elements must first be transferred to the dequeue stack before removing the current element.
struct Queue<T> {
var nqStack = Stack<T>()
var dqStack = Stack<T>()
func enqueue<T>(item: T) {
while (let i = dqStack.pop()) {
nqStack.push(item: i)
}
nqStack.push(item: item)
}
func dequeue<T>() -> T? {
while (let i = nqStack.pop()) {
dqStack.push(item: i)
}
return dqStack.pop()
}
}
The runtime is most efficient when either:
- all elements are enqueued first, then all elements are dequeued
- each element is enqueued and dequeued before another element is introduced
In both cases, each element is
- enqueued, requiring 1 push
- transferred, requiring 1 pop and 1 push
- dequeued, requiring 1 pop
This data structure takes 4n = O(n) push/pop operations, for a collection of n elements.
The runtime is very inefficient when n/2 elements are enqueued first, then operations alternate between dequeue and enqueue for the remaining n/2 elements. In terms of pushing/popping operations, it has:
enqueues = n / 2 pushes
dequeue followed by enqueue =
n / 2 ((n / 2 pops + n / 2 pushes + 1 pop) + ((n – 1) / 2 pops + (n – 1) / 2 pushes + 1 pushes))
dequeues = n / 2 pops
= n/2 + n/2((n/2 + n/2 + 1) + (n - 1)/2 + (n - 1)/2 + 1) + n/2 = 2n/2 + n/2(2n/2 + 1) + 2(n - 1)/2 + 1) = n + n/2((n + 1) + (n - 1) + 1) = n + n/2(2n + 1) = n + (2n^2 + n)/2 = n + n^2 + n/2 = n^2 + 3n/2 = O(n^2)