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

#### 41 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.

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

2. Great Article Cloud Computing Projects

Networking Projects

Final Year Projects for CSE

JavaScript Training in Chennai

JavaScript Training in Chennai

The Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training

2. This comment has been removed by the author.

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

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.

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

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

7. Good Post! Thank you so much for sharing this pretty post, it was so good to read and useful to improve my knowledge as updated one, keep blogging.
ivanka trump hot pictures

8. good post thanks for sharing your post and i have seen some more web links for mulesoft and aws training .
https://svrtechnologies.com/mule-esb-training/
https://svrtechnologies.com/aws-course/

9. I like your post very much. It is very much useful for my research. I hope you to share more info about this. Keep posting mulesoft training

10. Thanks for sharing this information. I really Like Very Much.
mulesoft online training
best mulesoft online training
top mulesoft online training

11. I am reading your post from the beginning, it was so interesting to read & I feel thanks to you for posting such a good blog, keep updates regularly..mulesoft 4 training

12. Thank you for sharing such a great information.Its really nice and informative.hope more posts from you. I also want to share some information recently i have gone through and i had find the one of the best mulesoft training videos

13. Pretty article! I found some useful information in your blog, it was awesome to read, thanks for sharing this great content to my vision, keep sharing. mulesoft 4 training and mulesoft 4 training videos.

14. if you want to pop up your website then you need free business email accounts

15. I really enjoy reading of your article. I wanted to inform you that you have people like me who appreciate your work.

techwithgeeks
talesbuzz
whizzherald

16. Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
mulesoft online training
best mulesoft online training
top mulesoft online training

17. I am reading your post from the beginning, it was so interesting to read & I feel thanks to you for posting such a good blog, keep updates regularly.I want to share about Mulesoft training in hyderabad .

18. I am reading your post from the beginning, it was so interesting to read & I feel thanks to you for posting such a good blog, keep updates regularly.I want to share about Mulesoft training .

19. http://www.prspackersandmovers.com/

20. Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
workday online training

21. https://www.atranspackers.in/index.html

22. Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
workday online training
workday hcm online training

23. Its very informative blog and useful article thank you for sharing with us , keep posting learn
microstrategy courses | microstrategy training

24. Great article! It is really helpful for my research. Do post and share more such wonderful content and keep updating.
Informatica Cloud Training
SAP Hybris Training
AWS‌ ‌Data‌ ‌Engineering‌ Training

25. Power BI is a collection of various tools and services, applications that collaborate to produce interactive visuals and business intelligence capabilities of data. It helps end-users very much. Learn Power BI in real-time with ITGuru.
power bi online training | power bi online course

26. Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website mulesoft online training
best mulesoft online training
top mulesoft online training

27. Thanks again for the article post.Really thank you! Fantastic
MuleSoft online course
MuleSoft onlinetraining from india