The last article wrote about using two stacks to implement a queue. This article implements using two queues to implement a stack. In fact, the ideas of both almost the same.
Continue drawing instructions below:
The implementation code is given below:
#includetemplate class Stack{public: void Push(const T& x) {//q1, q2 are empty, push into q1 if (_q1.empty()&&_q2.empty()) {_q1.push(x);} else if (!_q1.empty() )//If q1 is not empty, then push into q1 {_q1.push(x);} //q1 is empty, q2 is not empty (put q1 directly, so pop may be more convenient), if you need to push later, it is not convenient The else//q2 is not empty, push into q2 {_q2.push(x);}} T Pop() {if (_q1. empty() && _q2.empty()) {exit(EXIT_FAILURE);} if (! _q1.empty()) {while (_q1.size() != 1) {T tmp = _q1.front(); _q1.pop(); _q2.push(tmp);} T ret = _q1.front() ; _q1.pop(); return ret;} if (!_q2.empty()) {while (_q 2.size() != 1) {T tmp = _q2.front(); _q2.pop(); _q1.push(tmp);} T ret = _q2.front(); _q2.pop(); return ret ;} }private: queue _q1; queue _q2;};void test(){ Stack s; s.Push(1); s.Push(4); s.Push(5) ; s.Push(6); s.Push(7); cout << s.Pop() << endl; cout << s.Pop() << endl; cout << s.Pop() << endl ; cout << s.Pop() << endl; cout << s.Pop() << endl;}int main(){ test(); system("pause"); return 0;}
通过上边的代码，我们可以看出，这段代码的实现方法是图片里的方法2 , That is, every time you push into a queue that is not empty, when pop
regards the empty queue as an auxiliary team to achieve this method It is more effective than the method 1 given in the picture.
The output result of the above program 7 6 5 4 1 (the two numbers are separated by a carriage return), so that the advanced out.
For method 1 in the picture, the code is not given here, and you can implement it yourself if you are interested. ~~~