详解栈和队列相互实现

栈和队列作为两种典型的线性表和特殊的数据结构，有着非常鲜明甚至可以说是相互对立的特点；栈先进后出（后进先出），队列先进先出（后进后出）。因此，在相同的输入情况下，两者产生的输出却截然相反。也正是因为这种截然相对的输出，使得他们彼此之间有了更多的联系，比如栈和队列相互实现。简而言之，就是我们可以用栈模拟出队列的输出，同样也可以用队列模拟出栈的输出。

一、栈实现队列

先说通俗易懂的也是大家最容易想到的实现方式：用两个栈实现一个队列。

1.两个栈S1，S2，S1负责数据的压入(Enqueue),S2负责数据的弹出(Dequeue);

2.初始状态两个栈都为空；

3.压入数据时，压入S1;

4.弹出数据时候，如果S2为空，则将S1中所有数据项弹出然后压入S2(倒序进入S2),然后弹出S2的栈顶元素；如果S2不为空，则直接弹出S2栈顶元素；如果S2为空且S1为空，则队列为空。例如对a,b,c实现push操作，然后实现pop操作：

#ifndef QUEUE_H

#define QUEUE_H

#include <iostream>

#include <stack>

template<typename T>

class Queue {

private:

 std::stack<T> s1;

 std::stack<T> s2;

 T back_elem;

public:

 void push(T elem);

 void pop();

 T front();

 T back();

 int size() const;

 bool empty() const;

};

template<typename T>

void Queue<T>::push(T elem) {

 s1.push(elem);

 back_elem = elem;

}

template<typename T>

void Queue<T>::pop() {

 if(!s2.empty()) {

  s2.pop();

 }

 else if(!s1.empty()) {

  while(!s1.empty()) {

   s2.push(s1.top());

   s1.pop();

  }

  s2.pop();

 }

 else {

  std::cout << "error pop(), empty queue!" << std::endl;

 }

}

template<typename T>

T Queue<T>::front(){

 if(!s2.empty()) {

  return s2.top();

 }

 else if(!s1.empty()) {

  while(!s1.empty()) {

   s2.push(s1.top());

   s1.pop();

  }

  return s2.top();

 }

 else {

  std::cout << "error front(), empty queue!" << std::endl;

 }

}

template<typename T>

T Queue<T>::back(){

 if(!empty())

  return back_elem;

 else {

  std::cout << "error back(), empty queue!" << std::endl;

  return 0;

 }

}

template<typename T>

int Queue<T>::size() const {

 return s1.size() + s2.size();

}

template<typename T>

bool Queue<T>::empty() const {

 return s1.empty() && s2.empty();

}

#endif                               

二、用队列实现栈

有了上面的经验，我们可以再想想怎样用两个队列实现栈呢？其实，思路或者说是原理，都是一样，就是利用两个容器，实现数据的翻转。

1.使用两个队列 q1, q2, 还有两个bool变量 q1_used， q2_used，分别表示q1是否在使用，q2是否在使用，两者只有一个在使用，另一个不在使用。初始状态为 q1_used = true;  q2_used = false;即此时q1在使用，q2闲置。

2.实现栈的push操作，首先判断q1_used，q2_used，然后找出正在使用队列，将其添加到队列中。例如q1_used == true;  则将元素添加到队列q1；  反之q2_used == true，则将元素添加到队列q2中。

3.实现栈的pop操作，首先判断q1_used ，q2_used，找出正在使用的队列，然后将在使用的队列元素取出来，放到闲置的队列中，删除队列最后一个元素。然后修改q1_used, q2_used。

例如初始状态为q1_used = true，a,b,c入栈，则将其插入队列q1中，然后执行出栈操作pop，则将a,b从q1中出队列，然后进入q2，将c进行pop操作。

4.执行top操作，判断q1_used q2_used，然后找出正在使用的队列，利用该队列函数back()，返回栈头元素值。

5.至于size()和empty()操作，就对正在使用的队列，执行size（）和empty（）函数，返回值。

具体实现代码如下：

#ifndef STACK_H

#define STACK_H

#include <queue>

#include <iostream>

template <typename T>

class Stack {

private:

 std::queue<T> q1;

 std::queue<T> q2;

 bool q1_used, q2_used;

public:

 Stack();

 void push(T elem);

 void pop();

 T top() const;

 bool empty() const;

 int size() const;

};

template <typename T>

Stack<T>::Stack() {

 q1_used = true;

 q2_used = false;

}

template <typename T>

void Stack<T>::push(T elem) {

 if(q1_used == true) {

  q1.push(elem);

 }

 if(q2_used == true) {

  q2.push(elem);

 }

}

template <typename T>

void Stack<T>::pop() {

 if(!q1.empty() && q1_used == true) {

  while(q1.size() != 1) {

   q2.push(q1.front());

   q1.pop();

  }

  q1.pop();

  q2_used = true;

  q1_used = false;

  return;

 }

 if(!q2.empty() && q2_used == true) {

  while(q2.size() != 1) {

   q1.push(q2.front());

   q2.pop();

  }

  q2.pop();

  q2_used = false;

  q1_used = true;

  return;

 }

 std::cout << "error! Stack::pop()" << std::endl;

}

template <typename T>

T Stack<T>::top() const {

 if(!q1.empty() && q1_used == true) {

  return q1.back();

 }

 else if(!q2.empty() && q2_used == true) {

  return q2.back();

 }

 std::cout << "error! Stack::top()" << std::endl;

 return 0;

}

template <typename T>

bool Stack<T>::empty() const {

 return q1.empty() && q1_used == true || q2.empty() && q2_used == true;

}

template <typename T>

int Stack<T>::size() const {

 if(!q1.empty() && q1_used == true) {

  return q1.size();

 }

 if(!q2.empty() && q2_used == true) {

  return q2.size();

 }

 return 0;

}

#endif

归根结底，栈和队列相互实现正是依赖于栈和队列的互相对立的特点。这也许就是数据结构的神奇之处，能够把各种不同的数据结构紧密的联系起来。我们可以在本站的数据结构和算法教程中找到更多类似的例子。