本文共 2380 字，大约阅读时间需要 7 分钟。
面试题：用两个栈（Stack）实现一个队列（Queue）
思路：
1、入队时，将元素压入s1。
2、出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。
这个思路，避免了反复“倒”栈，仅在需要时才“倒”一次。
具体实现如下：
#include using namespace std;#include #include #include //assert必须为.h库文件template class Queue{public: void Push(const T& x); void Pop(); void PrintQueue(); bool Empty(); size_t Size(); T& Front(); T& Back();public: stack s1;//栈s1进行入队 stack s2;//栈s2进行出队};template void Queue ::Push(const T& x){ s1.push(x);//s1栈入队}template void Queue ::Pop(){ if (s1.empty() && s2.empty())//两个队列为空 { return; } if (!s2.empty())//s2栈非空元素出栈 { s2.pop(); } else { while (!s1.empty()) //s2栈为空，s1中所有元素导入s2中进行s2的出栈，s1进行pop() { s2.push(s1.top()); s1.pop(); } s2.pop();//pop掉s2的栈顶元素 }}template void Queue ::PrintQueue(){ stack sk1 = s1; stack sk2 = s2; if (s1.empty() && s2.empty()) { cout << "queue is empty!" << endl; return; } while (!sk2.empty())//先输出sk2中的元素，进行sk2的出栈 { cout << sk2.top() << " "; sk2.pop(); } while (!sk1.empty())//再进行sk1中元素导入到sk2中，进行sk1的出栈 { sk2.push(sk1.top()); sk1.pop(); } while (!sk2.empty())//最后在sk2中输出sk1中元素，达到队列出队的效果 { cout << sk2.top() << " "; sk2.pop(); } cout << endl;}template bool Queue ::Empty()//判空{ return s1.size() == 0 && s2.size() == 0;}template size_t Queue ::Size()//队列元素个数{ return s1.size() + s2.size();}template T& Queue ::Front()//队头{ assert(s1.empty() && s2.empty());//断言队列是否为空 if (!s2.empty())//s2不为空，则s2栈顶为队头 { return s2.top(); } else//s2为空，则将s1中所有元素导入s2中，新s2栈顶为队头 { while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } return s2.top(); }}template T& Queue ::Back()//队尾{ assert(!s1.empty() || !s2.empty());//s1和s2中至少有一个不为空 if (!s1.empty())//s1不为空，则s1栈顶为队尾 { return s1.top(); } else//s1为空，则将s2中所有元素导入s1中，新s1栈顶为队尾 { while (!s2.empty()) { s1.push(s2.top()); s2.pop(); } return s1.top(); }}
测试用例如下：
void Test2(){ //Queue q1; //q1.s1.push(3); //q1.s2.push(4); //q1.s2.push(5); //q1.Push(2); //q1.Push(1); //q1.PrintQueue(); q1.Pop(); q1.Pop(); q1.Pop(); q1.Pop(); q1.Pop(); q1.Pop(); q1.PrintQueue(); Queue q1; q1.s1.push("lllll"); q1.s2.push("yyyyy"); q1.s2.push("fffff"); q1.Push("xxxxx"); q1.Push("yyyyy"); q1.PrintQueue(); cout << "empty: " << q1.Empty() << endl; cout << "size: " << q1.Size() << endl; cout << "front: " << q1.Front() << endl; cout << "back: " << q1.Back() << endl;} 本文出自 “” 博客，请务必保留此出处
转载地址：http://nilbi.baihongyu.com/