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)，可以说并不高效。

转载于:https://blog.51cto.com/11134889/2131771

你可能感兴趣的文章