Interview Questions

Algorithm Concept

The complexity of this approach relies on the fact that queue is a LIFO structure (Last-In, First-Out), where stack is a FIFO (First-In, First-Out) structure.
In queue push adds element at the end of the queue, where pop takes element from front of the queue.
In stack push adds element at the front of the stack and pop takes element again from from of the stack.

In order to solve this problem you will need to use two stacks.

Because you are using stack there will be always some performance problem you need to take into consideration. You can either optimize this algorithm for push or pop.

Solution

// Queue implementaion using Stack
// Optimized for push operation.
// Note: This queue is not thread-safe.
class Queue
{
public:
    void push(int elem)
    {
        m_stack.push(elem);
    }

    int pop()
    {
        if (m_stack.empty()) throw exception();

        Stack helperStack;

        // find last element
        while (!m_stack.empty())
        {
            helperStack.push(m_stack.pop());
        }

        int elem = helperStack.pop();

        // restore stack
        while (!helperStack.empty())
        {
            m_stack.push(helperStack.pop());
        }

        return elem;
    }

    bool empty()
    {
        return m_stack.empty();
    }

private:
    Stack m_stack; // by default empty
};

Here is a slight variation of the solution above, but here we optimize our data structure for series of push, or series of pop operations.

// Queue implementaion using Stack
// Optimized for series of pushes and series of pop operations.
class Queue
{
public:
    void push(int elem)
    {
        // prepare Queue for push
        if (!m_stackForPop.empty())
            reverse(m_stackForPop, m_stackForPush);

        m_stack.push(elem);
    }

    int pop()
    {
        // prepare Queue for push
        if (!m_stackForPush.empty())
            reverse(m_stackForPush, m_stackForPop);

        if (m_stackForPop.empty())
            throw exception();

        return m_stackForPop.pop();
    }

    bool empty()
    {
        return m_stackForPop.empty() && m_stackForPush.empty();
    }

private:
    void reverse(Stack &source, Stack &dest)
    {
        while (!source.empty())
        {
            dest.push(source.pop());
        }
    }

    Stack m_stackForPop;
    Stack m_stackForPush;
};

Implement Queue using Stack

Algorithm Concept

Solution