棧和隊(duì)列作為兩種典型的線性表和特殊的數(shù)據(jù)結(jié)構(gòu)，有著非常鮮明甚至可以說是相互對(duì)立的特點(diǎn)；棧先進(jìn)后出（后進(jìn)先出），隊(duì)列先進(jìn)先出（后進(jìn)后出）。因此，在相同的輸入情況下，兩者產(chǎn)生的輸出卻截然相反。也正是因?yàn)檫@種截然相對(duì)的輸出，使得他們彼此之間有了更多的聯(lián)系，比如棧和隊(duì)列相互實(shí)現(xiàn)。簡而言之，就是我們可以用棧模擬出隊(duì)列的輸出，同樣也可以用隊(duì)列模擬出棧的輸出。

一、棧實(shí)現(xiàn)隊(duì)列

先說通俗易懂的也是大家最容易想到的實(shí)現(xiàn)方式：用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。

1.兩個(gè)棧S1，S2，S1負(fù)責(zé)數(shù)據(jù)的壓入(Enqueue),S2負(fù)責(zé)數(shù)據(jù)的彈出(Dequeue);

2.初始狀態(tài)兩個(gè)棧都為空；

3.壓入數(shù)據(jù)時(shí)，壓入S1;

4.彈出數(shù)據(jù)時(shí)候，如果S2為空，則將S1中所有數(shù)據(jù)項(xiàng)彈出然后壓入S2(倒序進(jìn)入S2),然后彈出S2的棧頂元素；如果S2不為空，則直接彈出S2棧頂元素；如果S2為空且S1為空，則隊(duì)列為空。例如對(duì)a,b,c實(shí)現(xiàn)push操作，然后實(shí)現(xiàn)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                               

二、用隊(duì)列實(shí)現(xiàn)棧

有了上面的經(jīng)驗(yàn)，我們可以再想想怎樣用兩個(gè)隊(duì)列實(shí)現(xiàn)棧呢？其實(shí)，思路或者說是原理，都是一樣，就是利用兩個(gè)容器，實(shí)現(xiàn)數(shù)據(jù)的翻轉(zhuǎn)。

1.使用兩個(gè)隊(duì)列 q1, q2, 還有兩個(gè)bool變量 q1_used， q2_used，分別表示q1是否在使用，q2是否在使用，兩者只有一個(gè)在使用，另一個(gè)不在使用。初始狀態(tài)為 q1_used = true;  q2_used = false;即此時(shí)q1在使用，q2閑置。

2.實(shí)現(xiàn)棧的push操作，首先判斷q1_used，q2_used，然后找出正在使用隊(duì)列，將其添加到隊(duì)列中。例如q1_used == true;  則將元素添加到隊(duì)列q1；  反之q2_used == true，則將元素添加到隊(duì)列q2中。

3.實(shí)現(xiàn)棧的pop操作，首先判斷q1_used ，q2_used，找出正在使用的隊(duì)列，然后將在使用的隊(duì)列元素取出來，放到閑置的隊(duì)列中，刪除隊(duì)列最后一個(gè)元素。然后修改q1_used, q2_used。

例如初始狀態(tài)為q1_used = true，a,b,c入棧，則將其插入隊(duì)列q1中，然后執(zhí)行出棧操作pop，則將a,b從q1中出隊(duì)列，然后進(jìn)入q2，將c進(jìn)行pop操作。

4.執(zhí)行top操作，判斷q1_used q2_used，然后找出正在使用的隊(duì)列，利用該隊(duì)列函數(shù)back()，返回棧頭元素值。

5.至于size()和empty()操作，就對(duì)正在使用的隊(duì)列，執(zhí)行size（）和empty（）函數(shù)，返回值。

具體實(shí)現(xiàn)代碼如下：

#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

歸根結(jié)底，棧和隊(duì)列相互實(shí)現(xiàn)正是依賴于棧和隊(duì)列的互相對(duì)立的特點(diǎn)。這也許就是數(shù)據(jù)結(jié)構(gòu)的神奇之處，能夠把各種不同的數(shù)據(jù)結(jié)構(gòu)緊密的聯(lián)系起來。我們可以在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中找到更多類似的例子。