本文共 2282 字，大约阅读时间需要 7 分钟。
面试题：实现两个队列实现一个栈。
思路：
1、入栈：所有元素依次入队列q1；
2、出栈：判断栈元素个数是否为1，如为真，队列q1出列；
如为假，队列q1除了最后一个元素其余所有元素出队列，入队列q2，输出此时的q1中元素；队列q2所有元素入队列q1；
eg：将1, 2, 3, 4入队列，将1, 2, 3出列，4输出来，1, 2, 3入队列q2，最后返回到队列q1，实现了栈的后进先出。
具体实现如下：
#include #include #include #include using namespace std;template class Stack{public: void Push(const T& x); void Pop(); void PrintStack(); bool Empty(); size_t Size(); T& Top();public: queue q1; queue q2;};template void Stack ::Push(const T& x){ while (!q2.empty())//如果qu2不为空，将qu2中元素入qu1队列 { q1.push(q2.front()); q2.pop(); } q1.push(x);//q1进行入队}template void Stack ::Pop(){ if (q1.empty() && q2.empty())//两个队列为空 { return; } while (!q2.empty())//如果q2不为空，将q2中元素入q1队列 { q1.push(q2.front()); q2.pop(); } while (q1.front() != q1.back())//q1中除了队尾元素其余元素入q2队列 { q2.push(q1.front()); q1.pop(); } q1.pop(); while (!q2.empty())//将q2中元素重新导入q1中；当两个队列初始时为空时，可在两个队列都进行出栈的操作 { q1.push(q2.front()); q2.pop(); }}template void Stack ::PrintStack(){ if (q1.empty() && q2.empty())//两个队列为空 { cout << "stack is empty!" << endl; return; } queue qu1 = q1; queue qu2 = q2; while (!qu2.empty())//如果qu2不为空，将qu2中元素入qu1队列 { qu1.push(qu2.front()); qu2.pop(); } while (!qu1.empty())//qu1不为空时，不断进行导入导出，输出qu1中元素 { while (qu1.front() != qu1.back()) { qu2.push(qu1.front()); qu1.pop(); } cout << qu1.front() << " "; qu1.pop(); while (!qu2.empty()) { qu1.push(qu2.front()); qu2.pop(); } } cout << endl;}template bool Stack ::Empty(){ return q1.empty() && q2.empty();}template size_t Stack ::Size(){ return q1.size() + q2.size();}template T& Stack ::Top(){ assert(!q1.empty());//q1判空 //queue qu1 = q1;//不能使用返回函数内定义的变量 //queue qu2 = q2; while (!q2.empty())//如果qu2不为空，将qu2中元素入qu1队列 { q1.push(q2.front()); q2.pop(); } return q1.back();//返回q1中的队尾元素}
测试用例如下：
void Test3(){ //Stack s1; //s1.q1.push(4); //s1.q2.push(5); //s1.Push(1); //s1.Push(2); //s1.Push(3); //s1.PrintStack(); s1.Pop(); s1.Pop(); s1.Pop(); s1.Pop(); s1.Pop(); s1.PrintStack(); Stack s1; s1.q1.push("lllll"); s1.q2.push("yyyyy"); s1.q2.push("fffff"); s1.Push("xxxxx"); s1.Push("ggggg"); s1.PrintStack(); cout << "empty: " << s1.Empty() << endl; cout << "size: " << s1.Size() << endl; cout << "top: " << s1.Top() << endl;} 本文出自 “” 博客，请务必保留此出处
转载地址：http://iilbi.baihongyu.com/