使用兩個隊列實現一個棧
這個棧的聲明如下：
template<typename T>
class Stack_by_queue
{
public:
Stack_by_queue(){};
~Stack_by_queue(){};
void append_tail(const T& node);
T delete_head();
void Show_Stack(void);//從棧頂依次向棧低顯示輸出數據
protected:
private:
queue<T> queue1;
queue<T> queue2;
};
分析：棧的特性是先進後出，舉一個序列1,2,3,4來說，我們試著往一個queue1裡面push進去，這時候queue1的隊頭是1，隊尾是4，這時候要實現delete_head的話，對應的棧應該刪除4，對於queue1的隊尾，前面的1,2,3，都是不需要的。
實現dalete_head解決方法就是，依次彈出1,2,3並且壓入queue2中，queue1裡面只保存4，這時候要delete_head的話，對queue1進行pop操作就行了，然後queue1為空（注意這個狀態）,然後我要繼續delete_head,這個時候也是按照上面的思路，將queue2的1,2依次彈出，壓入queue1裡面，知道剩下最後一個隊尾元素3，將它pop掉就行了！這時候的狀態是queue1不為空，queue2為空。
實現append_tail的話也容易。注意上面的刪除頭以後的兩種狀態其實可以可以歸結為一種，那就是其中一個queue為空，另一個可以為空（這個時候模擬的stack就是空），或者不為空，append_tail來說，只需往非空的queue裡面添到隊尾就行了，若是都為空，隨便選一個即可
#include <queue>
#include <iostream>
using namespace std;
template<typename T>
class Stack_by_queue
{
public:
Stack_by_queue(){};
~Stack_by_queue(){};
void append_tail(const T& node);
T delete_head();
void Show_Stack(void);
protected:
private:
queue<T> queue1;
queue<T> queue2;
};
template<typename T>
void Stack_by_queue<T>::Show_Stack(void)
{
queue<T> Q1(queue1);
queue<T> Q2(queue2);
T tmp;
cout<<"\n this is Show_Stack!從棧頂到棧底顯示數據\n";
while(!Q1.empty() || !Q2.empty())
{
if(Q1.empty() && !Q2.empty())
{
//2->1
if (Q2.size() < 1)
{
return ;
}
while(Q2.size() != 1)
{
tmp = Q2.front();
Q2.pop();
Q1.push(tmp);
}
cout<<Q2.front()<<" ";
Q2.pop();
}
if(!Q1.empty() && Q2.empty())
{
//1->2
if (Q1.size() < 1)
{
return ;
}
while(Q1.size() != 1)
{
tmp = Q1.front();
Q1.pop();
Q2.push(tmp);
}
cout<<Q1.front()<<" ";
Q1.pop();
}
}
}
//保證在所有的過程中，至少隊列有一個是空的
template<typename T>
T Stack_by_queue<T>::delete_head()
{
T tmp;
if(queue1.empty() && !queue2.empty())
{
//2->1
if (queue2.size() < 1)
{
return -1;
}
while(queue2.size() != 1)
{
tmp = queue2.front();
queue2.pop();
queue1.push(tmp);
}
tmp = queue2.front();
queue2.pop();
return tmp;
}
if (!queue1.empty() && queue2.empty())
{
//1->2
T tmp;
if (queue1.size() < 1)
{
return -1;
}
while(queue1.size() != 1)
{
tmp = queue1.front();
queue1.pop();
queue2.push(tmp);
}
tmp = queue1.front();
queue1.pop();
return tmp;
}
else
return -1;
}
template<typename T>
void Stack_by_queue<T>::append_tail( const T& node )
{
//保證有一隊列為空，若全為空，則隊空,任選一個隊列就行
if (queue1.empty() && !queue2.empty())
queue2.push(node);
if (!queue1.empty() && queue2.empty())
queue1.push(node);
if (queue1.empty() && queue2.empty())
queue1.push(node);
else
return;
}
int main()
{
Stack_by_queue<char> my_stack;
my_stack.append_tail('a');
my_stack.append_tail('b');
my_stack.append_tail('c');
my_stack.Show_Stack();
my_stack.delete_head();
my_stack.delete_head();
my_stack.Show_Stack();
my_stack.append_tail('d');
my_stack.append_tail('e');
my_stack.Show_Stack();
my_stack.delete_head();
my_stack.Show_Stack();
my_stack.append_tail('f');
my_stack.Show_Stack();
}
/**************************
運行結果：
this is Show_Stack!從棧頂到棧底顯示數據
c b a
this is Show_Stack!從棧頂到棧底顯示數據
a
this is Show_Stack!從棧頂到棧底顯示數據
e d a
this is Show_Stack!從棧頂到棧底顯示數據
d a
this is Show_Stack!從棧頂到棧底顯示數據
f d a
***************************/
#include <queue>
#include <iostream>
using namespace std;
template<typename T>
class Stack_by_queue
{
public:
Stack_by_queue(){};
~Stack_by_queue(){};
void append_tail(const T& node);
T delete_head();
void Show_Stack(void);
protected:
private:
queue<T> queue1;
queue<T> queue2;
};
template<typename T>
void Stack_by_queue<T>::Show_Stack(void)
{
queue<T> Q1(queue1);
queue<T> Q2(queue2);
T tmp;
cout<<"\n this is Show_Stack!從棧頂到棧底顯示數據\n";
while(!Q1.empty() || !Q2.empty())
{
if(Q1.empty() && !Q2.empty())
{
//2->1
if (Q2.size() < 1)
{
return ;
}
while(Q2.size() != 1)
{
tmp = Q2.front();
Q2.pop();
Q1.push(tmp);
}
cout<<Q2.front()<<" ";
Q2.pop();
}
if(!Q1.empty() && Q2.empty())
{
//1->2
if (Q1.size() < 1)
{
return ;
}
while(Q1.size() != 1)
{
tmp = Q1.front();
Q1.pop();
Q2.push(tmp);
}
cout<<Q1.front()<<" ";
Q1.pop();
}
}
}
//保證在所有的過程中，至少隊列有一個是空的
template<typename T>
T Stack_by_queue<T>::delete_head()
{
T tmp;
if(queue1.empty() && !queue2.empty())
{
//2->1
if (queue2.size() < 1)
{
return -1;
}
while(queue2.size() != 1)
{
tmp = queue2.front();
queue2.pop();
queue1.push(tmp);
}
tmp = queue2.front();
queue2.pop();
return tmp;
}
if (!queue1.empty() && queue2.empty())
{
//1->2
T tmp;
if (queue1.size() < 1)
{
return -1;
}
while(queue1.size() != 1)
{
tmp = queue1.front();
queue1.pop();
queue2.push(tmp);
}
tmp = queue1.front();
queue1.pop();
return tmp;
}
else
return -1;
}
template<typename T>
void Stack_by_queue<T>::append_tail( const T& node )
{
//保證有一隊列為空，若全為空，則隊空,任選一個隊列就行
if (queue1.empty() && !queue2.empty())
queue2.push(node);
if (!queue1.empty() && queue2.empty())
queue1.push(node);
if (queue1.empty() && queue2.empty())
queue1.push(node);
else
return;
}
int main()
{
Stack_by_queue<char> my_stack;
my_stack.append_tail('a');
my_stack.append_tail('b');
my_stack.append_tail('c');
my_stack.Show_Stack();
my_stack.delete_head();
my_stack.delete_head();
my_stack.Show_Stack();
my_stack.append_tail('d');
my_stack.append_tail('e');
my_stack.Show_Stack();
my_stack.delete_head();
my_stack.Show_Stack();
my_stack.append_tail('f');
my_stack.Show_Stack();
}
/**************************
運行結果：
this is Show_Stack!從棧頂到棧底顯示數據
c b a
this is Show_Stack!從棧頂到棧底顯示數據
a
this is Show_Stack!從棧頂到棧底顯示數據
e d a
this is Show_Stack!從棧頂到棧底顯示數據
d a
this is Show_Stack!從棧頂到棧底顯示數據
f d a
***************************/
