用兩個隊列模擬實現(xiàn)一個棧的過程

棧具有“后進(jìn)先出”的特點(diǎn)，即某個元素最后進(jìn)入棧，卻最先出棧；隊列具有“先進(jìn)先出”的特點(diǎn)，即元素從隊尾依次進(jìn)隊列，依次從隊頭出隊列；現(xiàn)在用兩個隊列模擬實現(xiàn)一個棧的過程，詳細(xì)過程請看下面這張本人制作的gif圖：

實現(xiàn)代碼：

#include <iostream>

using namespace std;

#include <queue>

template <typename T>

class Stack {

public:

void Push(T elem);//向隊列中添加元素

void Pop();//向隊列中刪除元素

T Top();//返回最后進(jìn)入的頭元素

bool Empty();//判斷隊列是否為空

int Size() const;//返回隊列中元素個數(shù)

private:

queue<T> q1;

queue<T> q2;

};

template <typename T>

bool Stack<T>::Empty()  //判斷模擬的棧是否為空

{

if (q1.empty() && q2.empty())

{

return true;

}

return false;

}

template <typename T>

int Stack<T>::Size() const //返回模擬棧中元素的個數(shù)

{

if (!q1.empty())

{

return q1.size();

}

else

{

return q2.size();

}

}

template <typename T>

T Stack<T>::Top()//返回最后進(jìn)入的頭元素

{

if (Empty())

{

throw;

}

else if (!q1.empty())

{

return q1.back();

}

else

{

return q2.back();

}

}

template <typename T>

void Stack<T>::Push(T elem) //向隊列中添加元素

{

if (q1.empty() && q2.empty())

{

q1.push(elem);

}

else if (!q1.empty())

{

q1.push(elem);

}

//q2不為空

else//兩個隊列不可能同時為空，因為在之前刪除元素操作時，有一個必為空隊列

{

q2.push(elem);

}

}

template <typename T>

void Stack<T>::Pop() //向隊列中刪除頭元素，先進(jìn)先出

{

if (Empty())//兩個隊列都為空，無法刪除

{

throw;

}

if (!q1.empty())

{

while (q1.size()>1)

{

q2.push(q1.front());

q1.pop();

}

q1.pop();

}

//q2不為空

else //if (!q2.empty() && q1.empty())

{

while (q2.size()>1)

{

q1.push(q2.front());

q2.pop();

}

q2.pop();

}

}

int main()

{

Stack<int> s;

int i = 0;

for (i = 1; i <= 5; i++)

{

s.Push(i);

}

cout << "出棧的順序為：" << endl;

while (!s.Empty())

{

cout << s.Top() << endl;

s.Pop();

}

system("pause");

return 0;

}

運(yùn)行結(jié)果：

出棧的順序為：

5

4

3

2

1

請按任意鍵繼續(xù). . .