数据结构(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<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(); } }; 

评价：
虽然可以使用栈实现队列，但是相比直接使用链表实现队列，在出队和获取对头元素的操作中，时间复杂度都变为了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<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(); } }; 

总结评价：
虽然可以使用队列实现栈，但是相比直接使用链表实现栈，入栈、出栈、获取栈顶元素操作中，时间复杂度都变为了O(n)，可以说并不高效。