用腾讯云做网站的好处,网站内容如何管理,江苏省建设厅网站权力阳光系统,中国建设工程交易信息网http://blog.csdn.net/hanjing_1995/article/details/51539578 使用两个栈实现一个队列 思路一#xff1a; 我们设定s1是入栈的#xff0c;s2是出栈的。 入队列#xff0c;直接压到s1即可 出队列#xff0c;先把s1中的元素倒入到s2中#xff0c;弹出s2中的栈顶元素#x…http://blog.csdn.net/hanjing_1995/article/details/51539578 使用两个栈实现一个队列 思路一 我们设定s1是入栈的s2是出栈的。 入队列直接压到s1即可 出队列先把s1中的元素倒入到s2中弹出s2中的栈顶元素再把s2的剩余元素全部倒回s1中。 缺点 每次只要出栈一个元素就要将元素倒来倒去麻烦 思路2 入队列时 如果s1为空把s2中所有的元素倒出压到s1中。否则直接压入s1 出队列时 如果s2不为空把s2中的栈顶元素直接弹出。否则把s1的所有元素全部弹出压入s2中再弹出s2的栈顶元素 思路1无条件地每次都要将元素倒来倒去思路2出队时较思路1简单 思路3 我们设定s1是入栈的s2是出栈的 入队列直接压入元素至s1即可 出队列如果s2不为空把s2中的栈顶元素直接弹出。否则把s1的所有元素全部弹出压入s2中再弹出s2的栈顶元素 相比于方法2入队直接压入即可~ 那么我们可以看出思路三最简单我们下面看下代码。 代码实现 1我们直接调用库里的stack来实现。一般调用库里的就行了 [cpp] view plain copy #define _CRT_SECURE_NO_WARNINGS 1 #includeiostream using namespace std; //两个栈实现一个队列 #includestack templateclass T class Queue { public: void appendTail(const T x) { s1.push(x); } void deleteHead() { if (s2.empty()) { while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } cout s2.top() ; s2.pop(); } else { cout s2.top() ; s2.pop(); } } private: stackT s1; stackT s2; }; void Test() { Queueint q; q.appendTail(1); q.appendTail(2); q.appendTail(3); q.appendTail(4); q.deleteHead(); q.deleteHead(); q.deleteHead(); q.deleteHead(); } int main() { Test(); system(pause); return 0; } 2自己实现栈实现。 [cpp] view plain copy #define _CRT_SECURE_NO_WARNINGS 1 #includeiostream using namespace std; #includeassert.h //直接实现Stack也可以用适配器实现栈或者用库。 //将Stack基本功能实现如下 templateclass T class Stack { public: Stack() :_array(NULL) , _size(0) , _capacity(0) {} StackT(const StackT s) : _array(new T[s._capacity]) { swap(_array, s._array); swap(_size, s._size); swap(_capacity, s._capacity); } StackT operator(const StackT s) { if (s ! this) { swap(_array, s._array); swap(_size, s._size); swap(_capacity, s._capacity); } return *this; } ~Stack() { if (_array) { delete[] _array; _array NULL; } } void _CheckCapacity() { if (_size 0) { _capacity 3; _array new T[_capacity]; } if (_size _capacity) { _capacity * 2; T* tmp new T[_capacity]; for (int index 0; index _size; index) { tmp[index] _array[index]; } delete[] _array; _array tmp; } } void Push(const T x) { _CheckCapacity(); _array[_size] x; } void Pop() { if (_size 0) { return; } --_size; } size_t Size() { return _size; } bool Empty() { return Size() 0; } T Top() { assert(_size 0); return _array[_size - 1]; } private: T* _array; size_t _size; size_t _capacity; }; templateclass T class Queue { public: void InQueue(const T x) { s1.Push(x); } void OutQueue() { //栈s2为空则将栈s1的元素全部倒入s2中再弹出最上面的那个元素 if (s2.Empty()) { while (!s1.Empty()) { s2.Push(s1.Top()); s1.Pop(); } s2.Pop(); } //栈s2不为空直接弹出元素 else { s2.Pop(); } } void Print() //打印队列元素分四种情况。 { if (s1.Empty() s2.Empty()) { cout The Queue is Empty!; } else if (!s1.Empty() s2.Empty()) { while (!s1.Empty()) { s2.Push(s1.Top()); s1.Pop(); } while (!s2.Empty()) { cout s2.Top() ; s2.Pop(); } } else if (s1.Empty() !s2.Empty()) { while (!s2.Empty()) { cout s2.Top() ; s2.Pop(); } } else { while (!s2.Empty()) { cout s2.Top() ; s2.Pop(); } while (!s1.Empty()) { s2.Push(s1.Top()); s1.Pop(); } while (!s2.Empty()) { cout s2.Top() ; s2.Pop(); } } cout endl; } private: StackT s1; //入队 StackT s2; //出队 }; //测试两个栈实现一个队列 void Test1() { Queueint q1; q1.InQueue(1); q1.InQueue(2); q1.InQueue(3); q1.InQueue(4); /*q1.Print();*/ q1.OutQueue(); /*q1.Print();*/ q1.InQueue(5); q1.InQueue(6); q1.InQueue(7); q1.Print(); } int main() { Test1(); system(pause); return 0; } (1个细节) 注意再将元素倒入另一个栈时代码并不是先pop,再push。因为这样push后元素就找不到了。因此要先访问到栈顶元素top,再push,而后pop。 本文出自 “Han Jings Blog” 博客请务必保留此出处http://10740184.blog.51cto.com/10730184/1763006
