使用两个栈实现一个队列-创新互联
面试题:用两个栈(Stack)实现一个队列(Queue)
创新互联是一家集网站建设,陇川企业网站建设,陇川品牌网站建设,网站定制,陇川网站建设报价,网络营销,网络优化,陇川网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。思路:
1、入队时,将元素压入s1。
2、出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
这个思路,避免了反复“倒”栈,仅在需要时才“倒”一次。
具体实现如下:
#includeusing 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() { //Queueq1; //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; }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
分享名称:使用两个栈实现一个队列-创新互联
当前链接:http://pwwzsj.com/article/cegjdd.html