題目
兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧
思路1
兩個(gè)隊(duì)列queue1, queue2。不管是插入還是彈出纳本，保證總有一個(gè)隊(duì)列為空窍蓝。
- 入棧操作：總是往有數(shù)據(jù)的列隊(duì)插入，默認(rèn)兩個(gè)列隊(duì)空繁成，插入
queue1 - 出棧操作：從非空列隊(duì)中刪除數(shù)據(jù)并插入空列隊(duì)吓笙，一直到非空列隊(duì)剩下一個(gè)元素，該元素就是出棧的元素
分析：
如圖所示巾腕，先往棧內(nèi)壓入一個(gè)元素a面睛。由于兩個(gè)隊(duì)列現(xiàn)在都是空的，可以選擇把a插入兩個(gè)隊(duì)列的任意一個(gè)祠墅。
不妨把a插入queue1侮穿。接下來繼續(xù)往棧內(nèi)壓入b、c兩個(gè)元素毁嗦，把它們也都插入queue1亲茅。這個(gè)時(shí)候queue1包含3個(gè)元素a、b狗准、c克锣，其中a位于隊(duì)列的頭部、c位于隊(duì)列的尾部
現(xiàn)在考慮從棧內(nèi)彈出一個(gè)元素腔长，根據(jù)棧的后入先出原則袭祟，最后被壓入棧的c應(yīng)該先彈出。由于c位于queue1的尾部捞附，而每次只能從隊(duì)列的頭部刪除元素巾乳，因此可以先從queue1中因此刪除a您没、b并插入queue2，再從queue1中刪除c胆绊。這就相當(dāng)于從棧中彈出元素c了氨鹏。可以使用同樣的方法從棧內(nèi)彈出元素b压状。
接下來再考慮往棧內(nèi)壓入一個(gè)元素d仆抵。此時(shí)queue1已經(jīng)有一個(gè)元素，就把d插入queue1的尾部种冬，如果再從棧內(nèi)彈出一個(gè)元素镣丑，同樣先從頭刪除queue1的元素并插入queue2，直到queue1遇到d再直接把它刪除
算法實(shí)現(xiàn)
- 定義棧
template<typename T>
class QueueStack
{
public:
void push(const T& data);
T pop();
int size();
QueueStack()
{
count = 0;
}
private:
queue<T> q1;
queue<T> q2;
int count;
};
- Push操作
// 進(jìn)棧
template<typename T>
void QueueStack<T>::push(const T& data)
{
if (q1.size()==0 && q2.size() ==0) // 默認(rèn)情況下都為空娱两，插入q1
{
q1.push(data);
}
else if (q1.size()>0) // q1非空插入q1
{
q1.push(data);
}
else if(q2.size()>0) // q2非空插入q2
{
q2.push(data);
}
++count; // 元素加1
}
- Pop操作
// 出棧
template<typename T>
T QueueStack<T>::pop()
{
if (q1.size()==0 && q2.size() ==0) // 列隊(duì)為空莺匠，拋出異常
{
logic_error ex("stack is empty");
throw exception(ex);
}
T element;
if (q2.size() == 0) // q2為空
{
while(q1.size() != 1) // 遍歷q1，將元素添加到q2谷婆，只留一個(gè)元素
{
q2.push(q1.front());
q1.pop();
}
element = q1.front(); // 即最后一個(gè)入列隊(duì)的元素出棧
q1.pop(); // 刪除元素
}
else
{
while(q2.size() != 1) // q2不為空慨蛙，并且個(gè)數(shù)不止一個(gè)
{
q1.push(q2.front());
q2.pop();
}
element = q2.front();
q2.pop();
}
--count; // 元素減1
return element;
}
- 棧大小
template<typename T>
int QueueStack<T>::size()
{
return count;
}
簡(jiǎn)單使用
void test() {
QueueStack<string> stack;
stack.push("a");
stack.push("b");
stack.push("c");
cout<<"current size: "<<stack.size()<<endl; // 3
cout<<stack.pop()<<endl; // c
cout<<"current size: "<<stack.size()<<endl; // 2
cout<<stack.pop()<<endl; // b
stack.push("d");
cout<<"current size: "<<stack.size()<<endl; // 2
cout<<stack.pop()<<endl; // d
}
思路2
兩個(gè)隊(duì)列queue1, queue2辽聊。不管是插入還是彈出纪挎，保證總有一個(gè)隊(duì)列為空。
隊(duì)列入棧：將元素插入空隊(duì)列跟匆，同時(shí)將非空隊(duì)列的元素依次插入到空隊(duì)列异袄。此時(shí)之前的非空隊(duì)列變?yōu)榭贞?duì)列，空隊(duì)列變?yōu)榉强贞?duì)列玛臂。
隊(duì)列出棧：將非空隊(duì)列的隊(duì)首彈出即可烤蜕。
分析：
執(zhí)行下述操作：先將1、2迹冤、3入棧讽营，接著3出棧，然后4入棧泡徙。兩個(gè)隊(duì)列元素的變化情況如下：
1橱鹏、 初始情況下：queue1 , queue2都為空，先將1壓入queue1堪藐。此時(shí)queue1為非空莉兰，queue2為空。
2礁竞、元素2入棧 糖荒，因?yàn)?code>queue2為空所以壓入。之前queue1非空模捂，將1彈出壓入queue2捶朵。此時(shí)queue1為空 queue2為2 蜘矢、1。
3综看、元素3入棧 硼端，queue1為空所以壓入。之前queue2非空寓搬，將2珍昨、1依次彈出壓入queue1。此時(shí)queue2為空 句喷，queue1為3镣典、2、1唾琼。
4兄春、元素3出棧 queue1非空 3出棧。queue1為2 1 queue2為空锡溯。
5赶舆、元素4入棧 queue2為空所以壓入。之前queue1非空祭饭，將2芜茵、1依次彈出壓入queue2。此時(shí)queue1為空 queue2為4倡蝙、2九串、1。
說白了就是將插入的數(shù)據(jù)直接排好序寺鸥，后插入的數(shù)據(jù)在列隊(duì)的頭部猪钮，先插入的數(shù)據(jù)在列隊(duì)尾部
算法實(shí)現(xiàn)
- 定義棧
#include <iostream>
#include <queue>
#include <exception>
using namespace std;
class QueueStack {
public:
void push(int x);
void pop();
int top();
bool empty();
unsigned long size();
private:
queue<int> q1;
queue<int> q2;
};
- Push操作
// 保證每個(gè)時(shí)刻都有一個(gè)隊(duì)列為空隊(duì)列
void QueueStack:: push(int x) {
if (q1.empty()) // 列隊(duì)1為空
{
q1.push(x); // 向列隊(duì)1插入元素
while (!q2.empty()) // 隊(duì)列2不為空
{
q1.push(q2.front()); // 獲取隊(duì)列2的首元素添加到隊(duì)列1
q2.pop(); // 去除隊(duì)列首元素
}
}
else // 列隊(duì)1不為空
{
q2.push(x); // 將元素t入隊(duì)列2
while (!q1.empty()) // 同理在隊(duì)列1不為空的情況下，將隊(duì)列1的元素添加到隊(duì)列2
{
q2.push(q1.front());
q1.pop();
}
}
}
- Pop操作
// 從棧頂去除元素
void QueueStack:: pop() {
if (empty()) { // 為空拋出異常
logic_error ex("stack is empty");
throw exception(ex);
}
if (q1.empty()) {
q2.pop();
}
else
{
q1.pop();
}
}
- Top操作
// 獲取頂部元素
int QueueStack:: top() {
if (empty()) {
logic_error ex("stack is empty");
throw exception(ex);
}
if (q1.empty()) {
return q2.front();
}
else
{
return q1.front();
}
}
- Empty胆建、棧數(shù)量操作
// 是否為空
bool QueueStack:: empty() {
return q1.empty() && q2.empty();
}
// 個(gè)數(shù)
unsigned long QueueStack:: size() {
return q1.size() + q2.size();
}
簡(jiǎn)單使用
void test() {
QueueStack stack;
stack.push(1);
stack.push(2);
stack.push(3);
cout<<"current size: "<<stack.size()<<endl; // 3
cout<<stack.top()<<endl; // 3
stack.pop(); // 去除元素3
cout<<"current size: "<<stack.size()<<endl; // 2
cout<<stack.top()<<endl; // 2
stack.pop(); // 去除元素2
stack.pop(); // 去除元素1
cout<<"is empty: "<<stack.empty()<<endl; // 1
}
