First of all, we must be clear that the stack is first-in-last-out, and the queue is first-in-first-out. After this their respective characteristics, we use two stacks to implement a queue.
The pictures are given below:
The code is given below:
templateclass Queue{public: void Push(const T& x) {if (!_s2.empty()) {while (!_s2.empty()) {_s1.push(_s2.top()); _s2.pop();}} _s1.push(x);} void Pop () {if (_s1.empty() && _s2.empty())//s1, s2 are empty {return;} if (!_s2.empty())//s2 is not empty {_s2.pop() ;} if (!_s1.empty() && _s2.empty())//s1 is not empty {//while(!_s1.empty()) while (_s1.size() != 1) {_s2.push (_s1.top());//You can push one less time _s1.pop();} _s1.pop();}} void Display() {while (!_s2.empty()) {cout << _s2.top () << ""; _s2.pop();} while (!_s1.empty()) {_s2.pu sh(_s1.top()); _s1.pop();} while (!_s2.empty()) {cout << _s2.top() << ""; _s2.pop();}} int Size( ) {return _s1.size() + _s2.size(); }public: stack _s1; stack _s2;};void test(){ Queue q; cout << q.Size( ) << endl; q.Push(2); q.Push(3); q.Push(1); q.Pop(); q.Push(4); q.Push(5); q.Pop( ); cout << q.Size() << endl; q.Display();}int main(){ test(); system("pause"); return 0;}
The implementation method of the above code is described in the solution in the lower right corner of the picture (that is: when pushing, if stack 2 is not empty , Push the element of stack 2 into stack 1,
Then, directly push the new element into stack 1; if stack 2 is Empty, directly push into stack 1. When pop, when stack 2 is not empty, pop directly from stack 2; when stack
2 is empty , Push the element of stack 1 into stack 2 (you can push one less time), and pop the top element of the stack)
The other is given below An implementation method (that is, after a pop, the elements of stack 2 are pushed into stack 1, and the specific idea is not mentioned in the picture):
Look at the code below (only pop and push functions are given, other functions are the same as above)
< /p>
void Push(const T& x) {_s1.push(x);} void Pop() {if (_s1.empty() && _s2.empty())//s1, s2 are all empty {return;} if (!_s2.empty())//s2 is not empty {_s2.pop();} else if (!_s1.empty() && _s2.empty())//s1 Not empty {//while(!_s1.empty()) while (_s1.size() != 1) {_s2.push(_s1.top());//You can push once less _s1.pop(); } _s1.pop(); } while (!_s2.empty()) { _s1.push(_s2.top()); _s2.pop(); } }
The above code realizes that after each pop, the remaining elements in stack 2 are pushed into stack 1. This method may be better than the first This method is a bit more troublesome, but all
can be implemented.
If there is a problem with the above description, you can raise it~~~
< /p>