棧和隊列作為兩種典型的線性表和特殊的數據結構，有著非常鮮明甚至可以說是相互對立的特點；棧先進后出（后進先出），隊列先進先出（后進后出）。因此，在相同的輸入情況下，兩者產生的輸出卻截然相反。也正是因為這種截然相對的輸出，使得他們彼此之間有了更多的聯系，比如棧和隊列相互實現。簡而言之，就是我們可以用棧模擬出隊列的輸出，同樣也可以用隊列模擬出棧的輸出。

一、棧實現隊列

先說通俗易懂的也是大家最容易想到的實現方式：用兩個棧實現一個隊列。

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

歸根結底，棧和隊列相互實現正是依賴于棧和隊列的互相對立的特點。這也許就是數據結構的神奇之處，能夠把各種不同的數據結構緊密的聯系起來。我們可以在本站的數據結構和算法教程中找到更多類似的例子。