数据结构(08)_队列和栈的相互实现-创新互联

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许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

名称栏目：数据结构(08)_队列和栈的相互实现-创新互联
分享URL：http://cdxtjz.cn/article/dsdeei.html