Interview Question, Part 2

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!

The Answer

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