Saturday, October 29, 2011

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.    

8 comments:

  1. When you have to implement 1 stack using 2 queues we can do as follows:

    Class Xstack{
    private:
    std::queue Q1;
    std::queue Q2;
    bool flag;

    public:
    Xstack(){ flag=false;};
    void pop(int n);
    int push(void);
    };


    void XStack::push(int n)
    {
    (flag==false)?Q1.push_back(n):Q2.push_back(n);
    }

    int XStack::pop()
    {
    std::queue *q1, *q2;
    if(flag==false)
    {
    q1=&Q1;
    q2=&Q2;
    }
    else
    {
    q1=&Q2;
    q2=&Q1;
    }
    while(q1->size()!=1)
    {
    q2->push_back(q1->front());
    q1->pop_front();
    }
    int x= q1->front();
    q1->pop_front();
    flag^=1;
    }

    The author is not responsible for the above snippet of code and it is given in accordance to Open source licenses. You may use it as you want as long as you you understand that there is no guarantee with this.

    ReplyDelete
    Replies
    1. Hi Harry,

      I learnt so much in such little time about No. 17 - Queue Implemented with Two Stacks. Even a toddler could become smart reading of your amazing articles.

      Thank you for creating an Amazon Web Services (AWS) account. We are in the process of activating your account so that you can begin using AWS AWS Training . For most customers, activation only takes a couple of minutes (but can sometimes take a few hours if additional account verification is required). We will notify you by email once verification is complete and your account is activated."

      AMI denotes Amazon Machine Image. It is definitely a picture of the source file system. Useful hardware, servers have bios that denote the master boot record from the first slab on a disk. A disk image, although can sit actually on a disk, Linux can boot from an absolute location on the EBS storage network.

      Appreciate your effort for making such useful blogs and helping the community.

      Thanks,
      Kevin

      Delete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Please check the below videos to understand this problem. Part 2 and Part 3 covers C++ and Java solution to the above problem.

    Part 1 - https://www.youtube.com/watch?v=_PIRZqC0pS0
    Part 2 - https://www.youtube.com/watch?v=D2Z2iGQW7cM
    Part 3 - https://www.youtube.com/watch?v=DeChmB6JSZw

    ReplyDelete
  4. Hello There,

    Such vivid info on the No. 17 - Queue Implemented with Two Stacks ! Flabbergasted! Thank you for making the read a smooth sail!

    I have just received an email that says, "We're writing to provide you with an electronic invoice for your use of AWS services for the billing period April 1 - April 30, 2018. Additional information regarding your bill, individual service charge details, and your account history are available on the Billing & Cost Management Page."

    Thanks a lot. This was a perfect step-by-step guide. Don’t think it could have been done better.

    Thank you,
    Preethi.

    ReplyDelete
  5. Hello There,


    I’ve often thought about this No. 17 - Queue Implemented with Two Stacks. Nice to have it laid out so clearly. Great eye opener.


    I was trying to register a new domain name on route 53 and I initially had payment issues. Finally, the payment went through and I was debited by my bank but Amazon sent me a message that payment failed even after the payment is successful.

    THANK YOU!! This saved my butt today, I’m immensely grateful.

    Shukran,
    Radhey

    ReplyDelete
  6. Bonjour,


    I genuinely do look forward for the time where you post some new write ups. Your blog make me feel so educated! Continue soaring and writing please.


    At the moment i cant complete my account because AWS is only providing me Credit Card that are not used that much in my country (The Netherlands, Europe) and the debit card solutions that AWS is providing ain't working as well because my debit is not recognized so probably it's only for the US. AWS Training USA




    But nice Article Mate! Great Information! Keep up the good work!


    Kind Regards,
    Irene Hynes

    ReplyDelete