Implement Queue and Sort via Stack

  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;
    }
};