Question: How do you use two stacks to implement a pair of columns?

Queue from stack A, queue from stack B. (The two most important operations of a queue, enqueue and enqueue.)

  • Enqueue: Enqueue from stack A.
  • Out of the queue: divided into two cases
    • If stack B is not empty, pop it.
    • If stack B is empty, all data in stack A is pushed into stack B, and data is ejected from stack B

The code implementation is as follows:

//2 stacks implement a queue
#include<stack>
#include<cassert>
#include<iostream>
using namespace std;

template<class T>
class Queue
{
public:
	Queue(){}
	virtual ~Queue(){}

	void push(const T& e) {
		m_stackA.push(e);
	}

	void pop(a) {
		if(m_stackB.empty()) {
			while(! m_stackA.empty()) { m_stackB.push(m_stackA.top()); m_stackA.pop(); } } m_stackB.pop(); }size_t size() const {
		return m_stackA.size() + m_stackB.size();
	}

	bool empty(a) {
		return m_stackA.empty() && m_stackB.empty();
	}

	T top(a) {
		if(m_stackB.empty()) {
			while(!m_stackA.empty()) {
				m_stackB.push(m_stackA.top());
				m_stackA.pop();
			}
		}
		return m_stackB.top();
	}

protected:
	stack<T> m_stackA;	/ / stack A
	stack<T> m_stackB;	B / / stack
};

int main(a) {
	Queue<int> m_queue;
	m_queue.push(1);
	m_queue.push(2);
    assert(m_queue.top() == 1);
    m_queue.pop();
    assert(2 == m_queue.top());

	return 0;
}
Copy the code

Extended thinking: how to use two queues to achieve the function of a stack?

Ideas: for example: there are D — — — — > B > C > A data in turn into the stack, the output sequence should be A — — — — > C > B > D. First, queue D–>C–>B–>A to queue 1, and eject C–>B–>A to queue 2, leaving only one, eject D; Add all data from queue 2 to queue 1 and continue with the above steps…… That’s the general idea.