1. 棧的隊列的相互實現

思考：棧和隊列在實現上非常相似，能否用相互實現？

1.1. StackToQueue

用棧實現隊列等價于用“后進先出”的特性實現“先進先出”的特性.

實現思路：

• 準備兩個棧用于實現隊列：stack_in和stack_out
• 入隊列：當有新元素入隊時，將其壓入隊列stack_in
• 出隊列：當需要出隊時：
  1.stack_out.size() == 0,將stack_in中的數據逐一彈出并壓人stack_out(數據移動)
  2.stack_out.size() > 0, 將stack_out的棧頂元素出棧(出棧操作)
  代碼實現：

template < typename T >
class StackToQueue : public Queue
{
protected:
    mutable LinkStack m_stack_in;
    mutable LinkStack m_stack_out;

    void move() const   //O(n)
    {
        if(m_stack_out.size() == 0)
        {
           while(m_stack_in.size() > 0)
            {
                m_stack_out.push(m_stack_in.top());
                m_stack_in.pop();
            }
        }
    }
public:
    void enqueue(const T& e) //O(1)
    {
        m_stack_in.push(e);
    }

    void dequeue()  //O(n)
    {
        move();

        if(m_stack_out.size() > 0)
        {
            m_stack_out.pop();
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "no element in current StackToQueue...");
        }
    }

    T front() const //O(n)
    {
        move();

        if(m_stack_out.size() > 0)
        {
            return m_stack_out.top();
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "no element in current StackToQueue...");
        }
    }

    void clear()    // O(n)
    {
        m_stack_in.clear();
        m_stack_out.clear();
    }

    int length() const  //O(n)
    {
        return m_stack_in.size() + m_stack_out.size();
    }
};

評價：
雖然可以使用棧實現隊列，但是相比直接使用鏈表實現隊列，在出隊和獲取對頭元素的操作中，時間復雜度都變為了O(n)，可以說并不高效。

1.2.QueueToStack

使用隊列實現棧，本質上就是使用“先進先出”的特性實現棧“后進先出”的特性。

實現思路：

• 準備兩個隊列用于實現棧：queue_1[in]和queue_2[out]
• 入棧：當有新元素入棧時，將其加入隊列[in]
• 出棧：
  1. 將隊列[in]中的前n-1個元素出隊，并進入隊列[out]中；
  2. 將隊列[in]中的最后一個元素出隊列(出棧操作)
  3. 交換兩個隊列的角色；
     代碼實現：

template < typename T >
class QueueToStack : public Stack
{
protected:
    LinkQueue m_queue_in;
    LinkQueue m_queue_out;
    LinkQueue* m_qIn;
    LinkQueue* m_qOut;

    void move() const   //O(n)
    {
       while(m_qIn->length()-1 > 0)
        {
            m_qOut->enqueue(m_qIn->front());
            m_qIn->dequeue();
        }
    }

    void swap()     //O(1)
    {
        LinkQueue* temp = NULL;

        temp = m_qIn;
        m_qIn = m_qOut;
        m_qOut = temp;
    }
public:
    QueueToStack()  //O(1)
    {
        m_qIn  = &m_queue_in;
        m_qOut = &m_queue_out;
    }

    void push(const T& e)   //O(n)
    {
        m_qIn->enqueue(e);
    }

    void pop()      //O(n)
    {
        if(m_qIn->length() > 0)
        {
            move();
            m_qIn->dequeue();
            swap();
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "no element in current QueueToStack...");
        }
    }

    T top() const       //O(n)
    {
        if(m_qIn->length() > 0)
        {
            move();
            return m_qIn->front();
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "no element in current QueueToStack...");
        }
    }

    void clear()        //O(n)
    {
        m_qIn->clear();
        m_qOut->clear();
    }

    int size() const    //O(1)
    {
        return m_qIn->length() + m_qOut->length();
    }
};

總結評價：
雖然可以使用隊列實現棧，但是相比直接使用鏈表實現棧，入棧、出棧、獲取棧頂元素操作中，時間復雜度都變為了O(n)，可以說并不高效。

另外有需要云服務器可以了解下創新互聯scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。