Click here to Skip to main content
13,900,622 members
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

2.8K views
Posted 15 Mar 2019
Licenced MIT

Interview Question, Part 2

, 15 Mar 2019
Rate this:
Please Sign up or sign in to vote.
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!

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.

License

This article, along with any associated source code and files, is licensed under The MIT License

Share

About the Author

Martin Vorbrodt
Software Developer (Senior)
United States United States
No Biography provided

You may also be interested in...

Comments and Discussions

 
SuggestionO(1) implementation : like the Hanoi towers problem Pin
Stefan_Lang21-Mar-19 23:31
memberStefan_Lang21-Mar-19 23:31 
Questionno need to spill both ways Pin
Pete Lomax Member 1066450518-Mar-19 16:26
professionalPete Lomax Member 1066450518-Mar-19 16:26 
GeneralWalk Out Pin
qqmrichter17-Mar-19 22:06
memberqqmrichter17-Mar-19 22:06 
GeneralRe: Walk Out Pin
Stefan_Lang21-Mar-19 23:06
memberStefan_Lang21-Mar-19 23:06 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web05 | 2.8.190306.1 | Last Updated 15 Mar 2019
Article Copyright 2019 by Martin Vorbrodt
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid