In this article we'll discuss how to implement queue and sort by stack. All these methods need to use two stacks.

§1 Queue

  Here we have a stack st1, and we'll use a temporary stack st2 to reverse st1. So, we can give method one:

1. in queue: directly in st1.
2. out queue: reverse st1 to st2, next pop the top, then reverse st2 to st1.

  This is the common method to achieve, to reduce the operation steps, we can have method two:

1. in queue: directly in st1.
2. out queue: if st2 not empty, pop from st2; else if st2 empty, reverse st1 to st2, then pop from st2.

Here is C++ example code:

// use stack to implement queue.
template<typename elemType>
class stque {
private:
    std::stack<elemType> m_st1;
    std::stack<elemType> m_st2;

public:
    stque() { /* do nothing */ }

    void reverse()
    {
        while (!m_st1.empty())
        {
            m_st2.push(m_st1.top());
            m_st1.pop();
        }
    }

    void push(elemType ele)
    {
        m_st1.push(ele);
    }

    elemType pop()
    {
        // if st2 empty, reverse st1 to st2 first, then pop.
        if (m_st2.empty())
        {
            this->reverse();
        }

        // if st2 not empty, directly pop.
        elemType retval = m_st2.top();
        m_st2.pop();
        return retval;
    }
};

§2 Sort

  Sort have the same idea with queue, here is my method. we have st1 which is to be sorted and sorted stack st2 i.e. the output. We use lt < as order principle.

that is, each time an element a is popped from the stack s, and the size of the top element b on the stack between it and s2 is judged, if a is less than or equal to b, then it is pushed to s2, otherwise, s2 is popped and merged Stack to s until the top element of s2 happens to be smaller than a, put a on the stack s2, repeat the above steps until s is empty.

Here is an example code:

// use stack to implement sort.
template<typename elemType>
class stsort {
public:
    // sort principle: <, for st2: small nums on top, big nums in bottom
    std::stack<elemType> sort(std::stack<elemType> st1)
    {
        std::stack<elemType> st2;

        st2.push(st1.top());
        st1.pop();

        while (!st1.empty())
        {
            elemType st1Top = st1.top();
            st1.pop();

        loop:
            elemType st2Top = st2.top();
            st2.pop();
            if (st1Top < st2Top)
            {
                st2.push(st2Top);
                st2.push(st1Top);
            }
            else
            {
                st1.push(st2Top);
                if (st2.empty())
                {
                    st2.push(st1Top);
                    continue;
                }
                goto loop;
            }
        }
        return st2;
    }
};