用2个栈实现队列
下面这段代码是我定义的Stack类模板,接下来介绍几种用2个该Stack类实现队列Queue的几种方法。
让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:主机域名、虚拟空间、营销软件、网站建设、阿拉善盟网站维护、网站推广。
templateclass Stack { public: Stack(); Stack(const Stack &st); Stack &operator=(const Stack &st); ~Stack(); public: void Push(const T &data); void Pop(); T &Top(); T &End(); bool Empty(); size_t Size(); void Print(); protected: void CheckCapacity(); protected: T *_arr; size_t _top; size_t _capacity; };
声明:为了实现除“入队”“出队”之外更多的功能,比如“打印”等,我将上面那个已造好的“轮子”Stack做了扩展,增加了一些成员方法。而如果你关注的重点是push和pop的算法,那么其实并不需要在意我造的下面这个“轮子”。可以直接跳过下面的代码,并把所有我使用的Stack类型当作库里的stack即可.
扩展后的Stack:
templateclass Stack { public: Stack() :_arr(NULL) , _top(0) , _capacity(0) {} Stack(const Stack &st) :_arr(new T[st._capacity]) , _top(st._top) , _capacity(st._capacity) { for (size_t i = 0; i < _capacity; i++) { _arr[i] = st._arr[i]; } } Stack &operator=(const Stack &st) { if (st._arr != _arr) { delete[] _arr; _arr = new T[st._capacity]; for (size_t i = 0; i < st._capacity; i++) { _arr[i] = st._arr[i]; } _top = st._top; _capacity = st._capacity; } return *this; } ~Stack() { if (_arr != NULL) { delete[] _arr; } } public: void Push(const T &data) { CheckCapacity(); _arr[_top] = data; ++_top; } void Pop() { --_top; } T &Top() { return _arr[_top - 1]; } T &End() { return _arr[0]; } bool Empty() { if (0 == _top) { return true; } else { return false; } } size_t Size() { return _top; } void Print() { for (size_t i = 0; i < _top; i++) { cout << _arr[i] << " "; } cout << endl; } void RePrint() { if (0 == _top) { return; } for (int i = _top - 1; i >= 0; i--) { cout << _arr[i] << " "; } cout << endl; } protected: void CheckCapacity() { if (_top == _capacity) { _capacity = _capacity + 3; T *tmp = new T[_capacity]; for (size_t i = 0; i < _top; i++) { tmp[i] = _arr[i]; } delete[] _arr; _arr = tmp; } } protected: T *_arr; size_t _top; size_t _capacity; };
--------------------------------------------------------------------------------
一、普通版本
栈的特点是“先入后出”,而队列的特点是“先入先出”。
所以可以定义一个类Queue,包含2个成员对象:
一个栈_stack1存放数据,另一个栈_stack2用来临时存放数据,通过一些压栈出栈的成员方法就可以实现对队列的入队、出队操作。
实现的2个栈组成的队列如下图所示,现在要将一组数据【1 2 3 4 5】放入队列中:
先将这组数依次压入_stack1中,然后再将_stack1中的元素依次出栈压入_stack2中:
这时候,_stack2中的元素依次出栈,就相当于队列的出队操作了。
用代码实现:
定义一个类模板Queue:
templateclass Queue { Queue() :_size(0) {} void Push(const T &data) //入队 { _stack1.Push(data); ++_size; } void Pop() //出队 { Converse(_stack2, _stack1); _stack2.Pop(); Converse(_stack1, _stack2); --_size; } protected: void Converse(Stack &dst, Stack &src) //src->dst { while (size--) { dst.Push(src.Top()); src.Pop(); } } protected: Stack _stack1; Stack _stack2; size_t _size; };
其中,
成员方法Converse():作用是将栈src中的内容依次出栈,压入栈dst中。
成员方法Push() :入队操作,每次将元素data存入成员对象_stack1中。
成员方法Pop() :出队操作,弹出第一个送入的元素。其中,第二个Converse的作用是还原。
可以看出,这种入队、出队的算法,需要保证元素始终在_stack1中维护,而只有在出栈的时候用到_stack2临时存放数据。
采用这种方式实现的队列,可以实现正常的入队、出队操作,但应该注意到,其中出队操作需要进行两次压栈,我们可以对一个细节稍作优化,进一步提高出队操作的执行效率。
下图为优化后的出队操作:
区别在于,在出队操作时,将_stack1中的(_size - 1)个元素弹出并压入_stack2中。
弹出后,也不需要将_stack2的元素“倒回”_stack1中。
二、代码优化
具体的实现步骤为:
出队操作时:
而是在每次执行出队的时候进行一次判断:
若_stack2为空,则将_stack1中的(_size - 1)个元素弹出并压入_stack2中,并弹出_stack中剩下的那个元素(就是我上面说的那个步骤);
若_stack2不为空,则弹出_stack2中最顶层的元素。
在入队操作时,判断_stack1是否为空:
若为空,则先将_stack2中的元素依次弹出并压入_stack1中,然后再将入栈元素压入_stack1中(左图)
否则,直接将入栈元素压入_stack1中
优化后的方案用代码实现如下:
templateclass queue { public: queue() :_size(0) {} queue(const queue &que) { _stack1 = que._stack1; _size = que._size; } public: void Push(const t &data) { if (_stack1.Empty() && !_stack2.Empty()) { Converse(_stack1, _stack2); } _stack1.Push(data); ++_size; } void Pop() { if (_stack2.Empty()) { if (_stack1.Empty()) { return; } RemainConverse(_stack2, _stack1); _stack1.Pop(); } else { _stack2.Pop(); } --_size; } void Print() { _stack1.Print(); _stack2.RePrint(); } bool Empty() { return (0 == _size); } t& Front() { if (_stack1.empty()) { return _stack2.top(); } else { return _stack1.end(); } } t& Back() { if (_stack1.Empty()) { return _stack2.End(); } else { return _stack1.Top(); } } size_t Size() { return _size; } protected: void RemainConverse(Stack &dst, Stack &src) { size_t count = src.Size() - 1; while (count--) { dst.Push(src.Top()); src.Pop(); } } void Converse(Stack &dst, Stack &src) //src->dst { while (!src.Empty()) { dst.Push(src.Top()); src.Pop(); } } protected: Stack _stack1; Stack _stack2; size_t _size; }; int main() { queue que1; que1.Push(1); que1.Push(2); que1.Push(3); que1.Push(4); que1.Print(); que1.Pop(); que1.Print(); que1.Push(5); que1.Print(); return 0; }
到目前我们已经实现了2种不同的方式实现这个队列。
这两种方法相比,第一种方法每次进行出队操作都要移动2次栈中的全部数据
而对于第二种方法实现的队列,如果连续进行入队或者出队操作,则不需要移动2个栈中的数据,能一定程度上提高效率。
三、进一步优化
可以看出,_stack1和_stack2中全部元素(或者说,全部元素-1)转移的次数越少,程序的执行效率就越高。
还有一种方法可以进一步减少_stack1和_stack2中全部元素交换的次数:
出队:
检测_stack2是否为空:
若为空,则将_stack1中的元素依次弹出并压入_stack2中,
若不为空,则弹出_stack2中栈顶的元素
入队:
将元素压入_stack。
可以看出,这种实现方式入队永远是从_stack2中弹出元素,出队永远是向_stack1中压入元素
而只有当入栈时检测到_stack2为空时,才执行2个栈之间全部元素的转移。
用如下的图能更形象地表示:
实现代码如下:
templateclass Queue { public: Queue() :_size(0) {} Queue(const Queue &que) { _stack1 = que._stack1; _size = que._size; } public: void Push(const T &data) { _stack1.Push(data); ++_size; } void Pop() { if (_size == 0) //异常 { return; } if (_stack2.Empty()) { Converse(_stack2, _stack1); } _stack2.Pop(); --_size; } void Print() { _stack2.RePrint(); _stack1.Print(); } bool Empty() { return (0 == _size); } T& Front() { if (_stack2.Empty()) { return _stack2.End(); } else { return _stack2.Top(); } } T& Back() { return _stack1.Top(); } size_t Size() { return _size; } protected: void Converse(Stack &dst, Stack &src) { while (!src.Empty()) { dst.Push(src.Top()); src.Pop(); } } protected: Stack _stack1; Stack _stack2; size_t _size; };
四、总结
这里一共提供了3种方法:
网页标题:用2个栈实现队列
路径分享:http://pwwzsj.com/article/jjoihi.html