Question

Suppose you have a stack ADT (i.e., an Abstract Data Type that includes operations to maintain a stack. Design a flowchart or suitable logical diagram to show you could implement a queue’s enqueue and dequeue operations using two stacks, stack 1 and stack 2.

​

Answer 1

One approach would be to move all items from stack1 to stack2 (effectively reversing the items), then pop the top item from stack2 and then put them back.

Assume you use stack1 for enqueueing. So enqueue(x) = stack1.push(x).

Dequeueing would be:

- For all items in stack1: pop them from stack1 and push them in stack 2.

- Pop one item from stack2, which will be your dequeue result

- For all items in stack2: pop them from stack2 and push them in stack 1.

Hope it makes sense. I'm sure you can draw a diagram.