13,900,598 members
Technical Blog
alternative version

Stats

2.8K views
Posted 15 Mar 2019
Licenced MIT

Interview Question, Part 2

, 15 Mar 2019
Given only a stack, how to implement a queue

Another interview question I was asked in the past:

Given only a stack, implement a queue.

I remember thinking at first that it cannot be done! My mind for some reason imagined that I am limited to only one stack. I told the interviewer that I don’t think it can be done with one stack. His response was: I didn’t say anything about having only one stack. That’s when it hit me: if I use two stacks, one for pushing, one for popping, and move the elements between them, it can be done!

When pushing, items go on stack 1. So the bottom of stack 1 is the front of the queue. So how do we get to the bottom element? We pop all the items from stack 1 and push them onto stack 2. This effectively reverses the order of elements and the top of stack 2 becomes the front of the queue. We can then pop off the queue by popping off of stack 2. We do this reversal of elements on every push and pop of the queue. Yea it’s inefficient, but it works.  Honestly, I don’t know why you would ever want to implement a queue this way, but nevertheless it was a great interview question!

```#include <iostream>
#include <stack>
using namespace std;

mutex cout_lock;
#define trace(x) { scoped_lock<mutex> lock(cout_lock); cout << x << endl; }

template<typename T>
class queue
{
public:
void push(const T& item)
{
spill(m_pop, m_push);
m_push.push(item);
}

void pop(T& item)
{
spill(m_push, m_pop);
item = m_pop.top();
m_pop.pop();
}

bool empty() const noexcept
{
return m_push.empty() && m_pop.empty();
}

private:
void spill(stack<T>& from, stack<T>& to)
{
while(!from.empty())
{
to.push(from.top());
from.pop();
}
}

stack<T> m_push;
stack<T> m_pop;
};

int main(int argc, char** argv)
{
queue<int> q;

q.push(1);
q.push(2);
q.push(3);

while(!q.empty())
{
int item;
q.pop(item);
trace(item);
}

return 1;
}```

1
2
3

Program output.

Share

 Software Developer (Senior) United States
No Biography provided

You may also be interested in...

 First Prev Next
 O(1) implementation : like the Hanoi towers problem Stefan_Lang21-Mar-19 23:31 Stefan_Lang 21-Mar-19 23:31
 no need to spill both ways Pete Lomax Member 1066450518-Mar-19 16:26 Pete Lomax Member 10664505 18-Mar-19 16:26
 Walk Out qqmrichter17-Mar-19 22:06 qqmrichter 17-Mar-19 22:06
 Re: Walk Out Stefan_Lang21-Mar-19 23:06 Stefan_Lang 21-Mar-19 23:06
 Last Visit: 23-Mar-19 21:07     Last Update: 23-Mar-19 21:07 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.