Implementing a queue using two stacks

Implement the enqueue, dequeue and peek functionalities of a queue using two stacks.

A queue is a FIFO (first-in, first-out) data structure and a stack is a LIFO (last-in, first-out) data structure. Consider two stacks stack_A and stack_B. A queue can be implemented by using stack_A for the enqueue() operation and stack_B for the dequeue() and peek() operations. Consider the following example: (the top of the stack is highlighted)

enqueue(10): Push 10 onto the stack_A

stack_A	stack_B
10

enqueue(20): Push 20 onto the stack_A

stack_A	stack_B
20
10

enqueue(30): Push 30 onto the stack_A

stack_A	stack_B
30
20
10

Peek(): The element which was inserted first has to be returned without popping it. In order to do this, first transfer all the elements from stack_A to stack_B if stack_B is empty. Return the topmost element from the stack_B. If the stack_B is not empty, just return the topmost element.

In this example, first pop the elements from stack_A and push them onto stack_B. Return the topmost element from stack_B, which is 10.

stack_A	stack_B
	10
	20
	30

enqueue(40): Push 40 onto the stack_A

stack_A	stack_B
	10
	20
40	30

Peek(): As stack_B is not empty, just return the topmost element from stack_B. In this case, it is 10.

dequeue(): The same logic as for the peek() operation holds true here. The difference here is the topmost element from the stack_B has to be popped out instead of returning it.

stack_A	stack_B
	20
40	30

Following is the C++ code:

#include <algorithm>

#include <stack>

class QueueStack {

  stack<int> stack_A;

  stack<int> stack_B;

public:

  void enqueue(int item);

  void dequeue();

  int peek();

};

void QueueStack::enqueue(int item) {

  stack_A.push(item);

}

void QueueStack::dequeue() {

  if(stack_B.empty()) {

    if(stack_A.empty()) {

      cout << "The queue is empty" << endl;

      return;

    } else {

      while(!stack_A.empty()) {

        stack_B.push(stack_A.top());

        stack_A.pop();

      }

      cout << "Removing " << stack_B.top() << " from the queue" << endl;

      stack_B.pop();

    }

  } else {

      cout << "Removing " << stack_B.top() << " from the queue" << endl;

      stack_B.pop();

  }

}

int QueueStack::peek() {

  if(stack_B.empty()) {

    if(stack_A.empty()) {

      cout << "The queue is empty" << endl;

      return -1;

    } else {

      while(!stack_A.empty()) {

        stack_B.push(stack_A.top());

        stack_A.pop();

      }

      cout << "The topmost element is " << stack_B.top() << endl;

      return stack_B.top();

    }

  } else {

      cout << "The topmost element is " << stack_B.top() << endl;

      return stack_B.top();

  }

}

In our case, the enqueue() worked only on stack_A and dequeue() worked on both stack_A and stack_B. A modified implementation could be to update stack_A and stack_B after each enqueue() and work on stack_B for dequeue().

A sequence of n combined enqueues and dequeues take O(n) time.