I was asked a question on how to use a pair of Queues to create a Stack and how to use a pair of Stacks to create a Queue. Any thoughts on how I would do this? Right now I don't even know where to start.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ One direction is easy, the other is highly nontrivial (if you want it to be fast): cstheory.stackexchange.com/questions/2562/one-stack-two-queues $\endgroup$– Alex ten BrinkOct 20, 2012 at 18:36
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
To answer the question in the comment above-
Two queues to implement a stack(Assume Queue A is filled with elements in LIFO order and Queue B is empty):
PUSH: Empty Queue A into Queue B. LIFO order will be persisted in Queue B. Now insert the new element into Queue A. Now empty Queue B into Queue A.
POP: Dequeue from Queue A
$\begingroup$
$\endgroup$
how to use a pair of Queues to create a Stack
Two regular (FIFO) Queues will be sufficient to implement a regular (LIFO) stack.
I'll show you the process with an example below:
The operation that should be done on our newly constructed Stack using two queues are:
Push A , B , C
Pop C
Push D
Lets start:
- Push A , B , C
Enqueue A , B , C to Queue 1
╔═════════╤═════════════╤═══╤══════╗
║ Queue 1 │ A │ B │ C ║
╠═════════╪═════════════╪═══╪══════╣
║ │ Head │ │ Tail ║
╟─────────┼─────────────┼───┼──────╢
║ Queue 2 │ - │ - │ - ║
╟─────────┼─────────────┼───┼──────╢
║ │ Head & Tail │ │ ║
╚═════════╧═════════════╧═══╧══════╝
- Pop C
Dequeue all element for Queue 1 expect tail element
Enqueue those elements (Dequeued from Queue 1) to Queue 2
Dequeue Tail from Queue 1
╔═════════╤══════╤══════╤═════════════╗
║ Queue 1 │ - │ - │ C ║
╠═════════╪══════╪══════╪═════════════╣
║ │ │ │ Head & Tail ║
╟─────────┼──────┼──────┼─────────────╢
║ Queue 2 │ A │ B │ ║
╟─────────┼──────┼──────┼─────────────╢
║ │ Head │ Tail │ ║
╚═════════╧══════╧══════╧═════════════╝
- Push D
Enqueue element to Queue 2
╔═════════╤═════════════╤═══╤══════╗
║ Queue 1 │ - │ - │ - ║
╠═════════╪═════════════╪═══╪══════╣
║ │ Head & Tail │ │ ║
╟─────────┼─────────────┼───┼──────╢
║ Queue 2 │ A │ B │ D ║
╟─────────┼─────────────┼───┼──────╢
║ │ Head │ │ Tail ║
╚═════════╧═════════════╧═══╧══════╝
PUSH :
Case 1 - empty stack
Enqueue into any Queue (1 or 2)
Case 2 - non empty stack
Enqueue into non empty Queue
POP :
Dequeue all element except tail of the non empty Queue (say Queue 1)
Enqueue all those element to the other empty Queue (say Queue 2)
Dequeue from Queue 1
how to use a pair of Stacks to create a Queue
Two regular (LIFO) stacks will be sufficient to implement a regular (LIFO) Queue.
Exmaple:
The operation that should be done on our newly constructed Queue using two stacks are:
Enqueue A , B , C
Dequeue C
Enqueue D
Lets start:
- Enqueue A , B , C
Push A , B , C to Stack 1
╔═════╤═════════╤═════╤═════════╗
║ │ Stack 1 │ │ Stack 2 ║
╠═════╪═════════╪═════╪═════════╣
║ Top │ C │ Top │ - ║
╟─────┼─────────┼─────┼─────────╢
║ │ B │ │ ║
╟─────┼─────────┼─────┼─────────╢
║ │ A │ │ ║
╚═════╧═════════╧═════╧═════════╝
- Dequeue C
Pop all elements from Stack 1
Push all these elements (popped from stack 1) to Stack 2
Pop from Stack 2
╔═════╤═════════╤═════╤═════════╗
║ │ Stack 1 │ │ Stack 2 ║
╠═════╪═════════╪═════╪═════════╣
║ Top │ - │ Top │ A ║
╟─────┼─────────┼─────┼─────────╢
║ │ │ │ B ║
╟─────┼─────────┼─────┼─────────╢
║ │ │ │ C ║
╚═════╧═════════╧═════╧═════════╝
- Enqueue D
Push D into Stack 2
╔═════╤═════════╤═════╤═════════╗
║ │ Stack 1 │ │ Stack 2 ║
╠═════╪═════════╪═════╪═════════╣
║ Top │ - │ Top │ D ║
╟─────┼─────────┼─────┼─────────╢
║ │ │ │ B ║
╟─────┼─────────┼─────┼─────────╢
║ │ │ │ C ║
╚═════╧═════════╧═════╧═════════╝
Enqueue:
Case 1 : Empty queue
Push into any stack (1 or 2)
Case 2 : Non empty queue
Push into non empty stack
Dequeue:
Pop all the elements from the non empty stack
Push all those elements (popped from non empty stack) to the empty stack
Pop top of non empty stack.
$\begingroup$
$\endgroup$
3
Two stacks to implements a queue -- always fill the stack A in stack B: the last element in stack A is popped (now you got FIFO) -- return elements from stack B to stack A.
Same idea is applied to queues.
-
2$\begingroup$ “Same idea is applied to queues.” How so? If you add elements to queue A, you get them back in the same order. If you then put them into queue B, you still get them in the same order. This is like negative × negative = positive, whereas positive × positive ≠ negative. $\endgroup$ Oct 18, 2012 at 23:46
-
$\begingroup$ Whoever gave me minus should revise his/her decision. I gave the solution already. To get the last element in a queue, you move all elements to queue B except the last ! the last is popped. "isn't that the same idea applied to queues ?!" - I don't care about votes ! but hey ! it s clear there ! $\endgroup$– AJedOct 19, 2012 at 13:58
-
$\begingroup$ Gilles put it best, but in short - you've only answered half of the question! $\endgroup$ Feb 23, 2015 at 10:45