Using Queues for a Stack and Stacks for a Queue

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.

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

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:

1. Push A , B , C

Enqueue A , B , C to Queue 1

╔═════════╤═════════════╤═══╤══════╗
║ Queue 1 │      A      │ B │  C   ║
╠═════════╪═════════════╪═══╪══════╣
║         │    Head     │   │ Tail ║
╟─────────┼─────────────┼───┼──────╢
║ Queue 2 │      -      │ - │  -   ║
╟─────────┼─────────────┼───┼──────╢
║         │ Head & Tail │   │      ║
╚═════════╧═════════════╧═══╧══════╝

1. 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 │             ║
╚═════════╧══════╧══════╧═════════════╝

1. 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:

1. Enqueue A , B , C

Push A , B , C to Stack 1

╔═════╤═════════╤═════╤═════════╗
║     │ Stack 1 │     │ Stack 2 ║
╠═════╪═════════╪═════╪═════════╣
║ Top │    C    │ Top │    -    ║
╟─────┼─────────┼─────┼─────────╢
║     │    B    │     │         ║
╟─────┼─────────┼─────┼─────────╢
║     │    A    │     │         ║
╚═════╧═════════╧═════╧═════════╝

1. 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    ║
╚═════╧═════════╧═════╧═════════╝

1. 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.

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.

• “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. Oct 18, 2012 at 23:46
• 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 !
– AJed
Oct 19, 2012 at 13:58
• Gilles put it best, but in short - you've only answered half of the question! Feb 23, 2015 at 10:45