1. 棧的隊(duì)列的相互實(shí)現(xiàn)

思考：棧和隊(duì)列在實(shí)現(xiàn)上非常相似，能否用相互實(shí)現(xiàn)？

成都創(chuàng)新互聯(lián)是一家專業(yè)提供張家界企業(yè)網(wǎng)站建設(shè),專注與成都做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、HTML5建站、小程序制作等業(yè)務(wù)。10年已為張家界眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設(shè)計(jì)公司優(yōu)惠進(jìn)行中。

1.1. StackToQueue

用棧實(shí)現(xiàn)隊(duì)列等價(jià)于用“后進(jìn)先出”的特性實(shí)現(xiàn)“先進(jìn)先出”的特性.

實(shí)現(xiàn)思路：

• 準(zhǔn)備兩個(gè)棧用于實(shí)現(xiàn)隊(duì)列：stack_in和stack_out
• 入隊(duì)列：當(dāng)有新元素入隊(duì)時(shí)，將其壓入隊(duì)列stack_in
• 出隊(duì)列：當(dāng)需要出隊(duì)時(shí)：
  1.stack_out.size() == 0,將stack_in中的數(shù)據(jù)逐一彈出并壓人stack_out(數(shù)據(jù)移動(dòng))
  2.stack_out.size() > 0, 將stack_out的棧頂元素出棧(出棧操作)
  代碼實(shí)現(xiàn)：

template < typename T >
class StackToQueue : public Queue<T>
{
protected:
    mutable LinkStack<T> m_stack_in;
    mutable LinkStack<T> 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();
    }
};

評(píng)價(jià)：
雖然可以使用棧實(shí)現(xiàn)隊(duì)列，但是相比直接使用鏈表實(shí)現(xiàn)隊(duì)列，在出隊(duì)和獲取對(duì)頭元素的操作中，時(shí)間復(fù)雜度都變?yōu)榱薕(n)，可以說(shuō)并不高效。

1.2.QueueToStack

使用隊(duì)列實(shí)現(xiàn)棧，本質(zhì)上就是使用“先進(jìn)先出”的特性實(shí)現(xiàn)?！昂筮M(jìn)先出”的特性。

實(shí)現(xiàn)思路：

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

template < typename T >
class QueueToStack : public Stack<T>
{
protected:
    LinkQueue<T> m_queue_in;
    LinkQueue<T> m_queue_out;
    LinkQueue<T>* m_qIn;
    LinkQueue<T>* 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<T>* 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();
    }
};

總結(jié)評(píng)價(jià)：
雖然可以使用隊(duì)列實(shí)現(xiàn)棧，但是相比直接使用鏈表實(shí)現(xiàn)棧，入棧、出棧、獲取棧頂元素操作中，時(shí)間復(fù)雜度都變?yōu)榱薕(n)，可以說(shuō)并不高效。

分享題目：數(shù)據(jù)結(jié)構(gòu)(08)_隊(duì)列和棧的相互實(shí)現(xiàn)
地址分享：http://aaarwkj.com/article24/gpgdje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、營(yíng)銷型網(wǎng)站建設(shè)、微信小程序、做網(wǎng)站、全網(wǎng)營(yíng)銷推廣、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)