两个队列实现一个栈
1.
龙港网站建设公司创新互联公司,龙港网站设计制作,有大型网站制作公司丰富经验。已为龙港1000多家提供企业网站建设服务。企业网站搭建\外贸网站建设要多少钱,请找那个售后服务好的龙港做网站的公司定做!
//使用两个队列实现一个栈,优化版(1.入栈只如q1,出栈将q1数据倒q2,删掉刚进来的, //若q1无数据,从q2倒,删q2中最后一个数据2.只保证一个栈中有数据,简单,易理解) //第一种实现
templateclass Stack { public: bool Empty() { return _q1.empty() && _q2.empty(); } void Push(const T& x) { _q1.push(x); } void Pop() { assert((!_q1.empty()) || (!_q2.empty())); if (_q1.empty()) { while (_q2.size()!= 1) { _q1.push(_q2.front()); _q2.pop(); } _q2.pop(); } else { while (_q1.size()!= 1) { _q2.push(_q1.front()); _q1.pop(); } _q1.pop(); } } int Size() { return _q1.size() + _q2.size(); } //先取_q1的back,若_q1为空,再取_q2的值 T& Top() { assert((!_q1.empty()) || (!_q2.empty())); if (!_q1.empty()) return _q1.back(); else return _q2.back(); } protected: queue _q1; queue _q2; };
2.
//第二种实现 templateclass Stack { public: void Push(const T& x) { if (!_q2.empty()) _q2.push(x); else _q1.push(x); } void Pop() { if (!_q1.empty()) { while (_q1.size() != 1) { _q2.push(_q1.front()); _q1.pop(); } _q1.pop(); } else { while (_q2.size() != 1) { _q1.push(_q2.front()); _q2.pop(); } _q2.pop(); } } T& Top() { if (!_q1.empty()) { return _q1.back(); } else return _q2.back(); } protected: queue _q1; queue _q2; }; void Test1() { Stack s1; s1.Push(1); s1.Push(2); s1.Push(3); s1.Push(4); s1.Push(5); s1.Pop(); cout << s1.Top() << endl; s1.Pop(); cout << s1.Top() << endl; //cout << s1.Size() << endl; s1.Push(6); cout << s1.Top() << endl; s1.Pop(); cout << s1.Top() << endl; s1.Push(7); cout << s1.Top() << endl; s1.Pop(); s1.Pop(); s1.Pop(); cout << s1.Top() << endl; }
网页题目:两个队列实现一个栈
网站链接:http://pwwzsj.com/article/jhpcpp.html