No. 17 - Queue Implemented with Two Stacks

Problem: Implement a queue with two stacks. The class for queues is declared in C++ as below. Please implement two functions: appendTail to append an element into tail of a queue, and deleteHead to delete an element from head of a queue.

template <typename T> class CQueue

{

public:

    CQueue(void);

    ~CQueue(void);

   

void appendTail(const T& node);

    T deleteHead();                 

private:

    stack<T> stack1;

    stack<T> stack2;

};

Analysis: According to declaration above, a queue contains two stacks stack1 and stack2. Therefore, it is required to implement a queue which follows the rule “First In First Out” with two stacks which follow the rule of “First In Last Out”.

We analyze the process to add and delete some elements via some examples. Firstly en element a is inserted. Let us push it into stack1. There is an element {a} in stack1and stack2 is empty. We continue to add two more elements b and c (push them into stack1 too). There are three elements {a, b, c} in stack1 now, where c is on its top, and stack2 is still empty (as shown in Figure 1-a).

We then have a try to delete an element from a queue. According to the rule “First in First out”, the first element to be deleted is a since it is added before b and c. The element a is stored in to stack1, and it is not on the top of stack. Therefore, we cannot pop it directly. We can notice that stack2 has not been used, so it is the time for us to utilize it. If we pop elements from stack1 and push them into stack2 one by one, the order of elements in stack2 is reverse to the order in stack1. After three popping and pushing operations, stack1 becomes empty and there are three elements {c, b, a} in stack2. The element a can be popped out now since it is on the top of stack2. Now there are two elements left {c, b} in stack2 and b is on its top (as shown in Figure 1-b).

How about to continue deleting more elements from the tail of queue? The element b is inserted into queue before c, so it should be deleted when there are two elements b and c left in queue. It can be popped out since it is on the top of stack2. After the popping operation, stack1 remains empty and there is only an element c in stack2 (as shown in Figure 1-c).

It is time to summarize the steps to delete an element from a queue: The top of stack2 can be popped out since it is the first element inserted into queue when stack2 is not empty. When stack2 is empty, we pop all elements from stack1 and push them into stack2 one by one. The first element in a queue is pushed into the bottom of stack1. It can be popped out directly after popping and pushing operations since it is on the top of stack2.

Let us insert another element d. How about to push it into stack1 (as shown in Figure1-d)? When we continue to delete the top of stack2, which is element c, can be popped because it is not empty (as shown in Figure 1-d). The element c is indeed inserted into queue before the element d, so it is a reasonable operation to delete c before d. The final status of the queue is shown as Figure 1-e.

Figure 1: The process to simulate a queue with two stacks.

We can write code after we get clear ideas about the process to insert and delete elements. Some sample code is shown below:

template<typename T> void CQueue<T>::appendTail(const T& element)

{

    stack1.push(element);

}

template<typename T> T CQueue<T>::deleteHead()

{

    if(stack2.size()<= 0)

    {

        while(stack1.size()>0)

        {

            T& data = stack1.top();

            stack1.pop();

            stack2.push(data);

        }

    }

    if(stack2.size() == 0)

        throw new exception("queue is empty");

    T head = stack2.top();

    stack2.pop();

    return head;

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.