Two stacks implement one queue

Hello everyone , I meet you again , I'm your friend, Quan Jun .

Using stack to realize queue

1、 The characteristics of the stack

The characteristic of stack is first in first out , In and out elements are on the same end （ To the top of the stack ）.

Push ：

Out of the stack ：

2、 Characteristics of the queue

The queue is characterized by first in, first out , The in and out elements are at different ends （ Team head and tail ）.

The team ：

Out of the team ：

3、 Two stacks implement queues

We have two stacks , One of the stacks can be used as the entry of the queue , Responsible for inserting new elements ; Another stack serves as the exit of the queue , Responsible for removing old elements .

There are only two main operations of the queue ： In and out of the team . When simulating queuing operations , Every new element is pushed onto the stack A among .

Let the elements 1“ The team ”：

Let the elements 2“ The team ”：

Let the elements 3“ The team ”：

Now , We want to be first “ The team ” The elements of 1“ Out of the team ”, What needs to be done ？

Let the stack A All the elements in are listed in order , Then press it into the stack according to the order of the stack B. thus , Elements from the stack A Pop up and push into the stack B The order is 3,2,1, And when I entered the stack A The order of 1,2,3 It's the opposite ：

Now let the element 1“ Out of the team ”, That is, let the elements 1 From stack B eject ：

Let the elements 2“ Out of the team ”：

What if you want to join the team again at this time ？ When new elements join the team , Push the new element onto the stack again A.

Let the elements 4“ The team ”：

The dequeue operation at this time is still from the stack B Pop up elements .

Let the elements 3“ Out of the team ”：

This time stack B It's empty , What if you want to join the team again ？ Just stack A And elements, just like just now , Put the stack A Elements pop up and push onto the stack B.

Let the elements 4“ Out of the team ”：

4、 Realize the idea

（1） Use two stacks A,B, Which assumes A be responsible for push operation ,B be responsible for pop operation . Use a variable back_elem To store the last added element .

（2） Implementation of the queue push operation , Every time you add , Will be corresponding to the stack A Add elements . Also on back_elem assignment

（3） Implementation of the queue pop operation , Every time you delete , Because of the stack B be responsible for pop operation ,

First judge the stack B Is it empty ？

a. If B It's empty , Then judge A Is it empty ？

If A Also empty , Then output error message , The queue is empty .

If A Not empty , Then stack A All data in is stored in B in . Of board B.push(A.top()), A.pop(). Then on the stack B perform ,B.pop() operation , Delete the header element of the queue

b. If B Not empty , Directly to B perform B.pop() operation .

For example a,b,c Realization push operation , Then implement pop operation

（4） Implementation of the queue front() operation , The method is as follows pop Same operation , Just use in the last step B.top() Return value .

（5） Implementation of the queue back() operation , Because we variable back_elem Save the last input data , So return it directly .

（6） Implementation of the queue size() operation , and empty() operation , That's right A,B Perform operations separately .

5、 Code implementation

#include <iostream>
#include <stack>
#include <string>
using namespace std;

template<typename T>
class Queue {
private:
	stack<T>stackA;	// Stack A
	stack<T>stackB;	// Stack B
	T back_elem;	// Used to store newly added elements 
public:
	void push(T elem);	// Push the new element into the queue （ Push to stack A） in 
	void pop();			// Pop the element out of the queue （ From stack B Pop up in ）
	T front();			// Team first element 
	T back();			// Team tail element 
	int size()const;    // The queue length 
	bool empty()const;  // Whether the queue is empty 
};

/*
 Joining operation 
 Implementation of the queue push operation ,  Every time you add , Will be corresponding to the stack A Add elements . Also on back_elem assignment 
*/
template<typename T>
void Queue<T>::push(T elem)
{
	stackA.push(elem);// Push elements into the queue 
	back_elem = elem;	// Store the newly added element 
}

/*
 Out of line operation 
 Implementation of the queue pop operation , Every time you delete , Because of the stack B be responsible for pop operation .
 First judge the stack B Is it empty ？
a. If the stack B It's empty , Then judge A Is it empty ？
		 If A Also empty , Then output error message , The queue is empty .
		 If A Not empty , Then stack A All data in is stored in B in . Of board B.push(A.top()), A.pop(). Then on the stack B
			 perform ,B.pop() operation , Delete the header element of the queue 
b. If the stack B Not empty ,  Then directly stack B perform  B.pop() operation .

*/
template<typename T>
void Queue<T>::pop()
{
	// Judgment stack B Is it empty ？
	if (!stackB.empty())	// Stack B Not empty ,  Then directly stack B perform  B.pop() operation .
	{
		stackB.pop();
	}
	else if (!stackA.empty())	// Stack B It's empty , Then judge the stack A Is it empty ？ Stack A Not empty , Then stack A All data in 
   // Store in B in . Of board B.push(A.top()), A.pop(). Then on the stack B perform ,B.pop() operation , Delete the header element of the queue 
	{
		stackB.push(stackA.top());
		stackA.pop();
	}
	else
	{
		std::cout << "error pop(),empty queue!" << std::endl;
	}
}

/*
 Team first element 
*/
template<typename T>
T Queue<T>::front()
{
	if (!stackB.empty())
	{
		return stackB.top();
	}
	else if (!stackA.empty())
	{
		while (!stackA.empty())
		{
			stackB.push(stackA.top());
			stackA.pop();
		}
		return stackB.top();
	}
	else
	{
		std::cout << "error front(),empty queue!" << std::endl;
	}
}

/*
 Team tail element 
*/
template<typename T>
T Queue<T>::back()
{
	if (!empty())
	{
		return back_elem;
	}
	else
	{
		std::cout << "error back(),empty queue!" << std::endl;
	}
}

/*
 The queue length 
*/
template<typename T>
int Queue<T>::size() const
{
	return stackA.size() + stackB.size();
}

/*
 Whether the queue is empty 
*/
template<typename T>
bool Queue<T>::empty() const {
	return stackA.empty() && stackB.empty();
}

int main()
{
	Queue<int>queue;
	// Joining operation 
	queue.push(1);
	queue.push(2);
	queue.push(3);
	queue.push(4);
	cout << "Four times push() After:" << endl;
	// Team first element 
	cout << "The queue front:" << queue.front() << endl;
	// Team tail element 
	cout << "The queue back:" << queue.back() << endl;
	// queue size
	cout << "The queue size:" << queue.size() << endl;
	// Out of line operation 
	queue.pop();
	queue.pop();
	queue.pop();
	queue.pop();
	cout << "----------------------------" << endl;
	cout << "Four times pop() After:" << endl;
	// Team first element 
	cout << "The queue front:" << queue.front() << endl;
	// Team tail element 
	cout << "The queue back:" << queue.back() << endl;
	// queue size
	cout << "The queue size:" << queue.size() << endl;

	//system("pause");
	return 0;
}

Copy

result ：

Four times push() After: The queue front:1 The queue back:4 The queue size:4 —————————- Four times pop() After: error front(),empty queue! The queue front:260750304 error back(),empty queue! The queue back:260750304 The queue size:0 Please press any key to continue . . .

6、 Time complexity

The time complexity of the queue operation is obviously O(1). As for the out of team operation , If stack is involved A And the stack B Element migration of , The time complexity is O(n), If you don't use element migration , The time complexity is O(1).

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/124970.html Link to the original text ：https://javaforall.cn