使用两个队列实现一个栈-创新互联
首先,我们得了解队列和栈的基本原理。
成都创新互联公司成立与2013年,先为黄山等服务建站,黄山等地企业,进行企业商务咨询服务。为黄山企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。队列是一个“先进先出“的一个结构。队列的定义是在队尾插入,在队头删除,这就要求要用一种在尾部插入容易的,在头部删除容易的结构,你一定会想到单链表,对,库的实现就是用一个链表实现的。
栈,相信大家都不会陌生,函数栈帧等的实现,它是一种”先进后出“的结构。栈的插入删除都是在尾部进行的。
所以要用队列实现一个栈,要解决的问题就是在删除时要删除最后插入的那个元素。
我们先来模拟一下出栈和入栈的情况:
(1)入栈:Q1:1,2,3,4入队列(相当于入栈);
(2)出栈:Q1:1,2,3出队列,Q2:1,2,3入队列;(此时Q1只剩4,正是我们要出栈的元素)
(3)
1>入栈:Q1:5入队列(每次入栈都用Q1入队列实现,而不入队列Q2,这样会提高效率,后面会说到)
2>出栈:判断:如果Q1队列不为空就用(1)(2)步的方法出栈最后一个元素。否则,出栈Q2队列的最后一个元素。
我们首先来搭建这个栈的结构:
#pragma once #include#include #include #include using namespace std; template class MYStack { public: MYStack() :_size(0) { } ~MYStack() { } void Push(const T& x); void Pop(); bool Empty(); size_t Size(); void Print(); private: queue q1; queue q2; size_t _size; };
一个栈具有的功能我们都实现一下,Psh(),Pop(),Empty(),Size()等等。
在这个结构中数据成员是两个队列的对象,因为我们是用两个队列来实现的,还有一个_size用来记录栈中元素的个数。
下面是函数具体实现:
templatevoid MYStack ::Push(const T& x) { q1.push(x); ++_size; } template void MYStack ::Pop() { //assert(_size > 0); //size_t plen = q1.size(); //while (plen != 1) //{ // T tmp = q1.front(); // q2.push(tmp); // q1.pop(); // --plen; //} //q1.pop(); //plen = q2.size(); //while (plen) //{ // T tmp = q2.front(); // q1.push(tmp); // q2.pop(); // --plen; //} //--_size; assert(_size > 0); size_t plen = q1.size(); if (plen == 0) { //if (q2.size() == 0) // return; plen = q2.size(); while (plen != 1) { T tmp = q2.front(); q1.push(tmp); q2.pop(); --plen; } q2.pop(); } else { size_t plen = q1.size(); while (plen != 1) { T tmp = q1.front(); q2.push(tmp); q1.pop(); --plen; } q1.pop(); } --_size; } template bool MYStack ::Empty() { return _size ? false : true; } template size_t MYStack ::Size() { return _size; } template void MYStack ::Print() { //size_t plen = q1.size(); //while (plen--) //{ // cout << q1.front() << " "; // q1.pop(); //} size_t plen = q2.size(); while (plen--) { cout << q2.front() << " "; q2.pop(); } plen = q1.size(); while (plen--) { cout << q1.front() << " "; q1.pop(); } }
注释掉的部分也可以实现,它的原理是不管第(3)步是出栈还是入栈,都把剩下的元素从Q2出栈入栈到Q1,输出的时候只用输出Q1中的元素。但是它的效率较低。如果有这种情况:1,2,3.....100000入栈,然后1,2,3......100000出栈,这会导致Q1和Q2频繁的出栈和入栈,效率非常之低。
优化方法就是没有注释部分。它的实现就是入栈都是Q1入队列,出栈后不把Q2的元素移到Q1,这样的话效率就会提高,只是在输出的时候要先输出Q2里的元素,再输出Q1里的元素。因为Q1里的元素总是栈顶的元素。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站栏目:使用两个队列实现一个栈-创新互联
本文来源:http://scyanting.com/article/hjjhp.html