Queue and stack

queue （queue） And the stack （stack）

queue queue

queue （queue） It's a first in, first out FIFO（first in first out） The linear table . It only allows inserting elements at one end of the table , And delete the element at the other end , The first element in the queue is the first to leave . In the queue , The inserted paragraph is called the tail of the team （back）, The deleted paragraph is called team leader （front）

Queues are defined in < queue > Header file

The prototype of the queue class member function is as follows ：

//---- Capacity capacity----
bool empty(); // Test whether the queue is empty 
size_type size(); // Return queue length 

//---- Element access element access----
front(); // Return to team leader element 
back(); // Return to the end of the team 

//---- Queue operation operations----
void push(const T& x); // Insert an element to the end of the queue 
void pop(); // Delete the next element in the queue 

example ： Examples of queue applications

#include<iostream>
#include<string>
#include<algorithm>
#include<queue> // Using the queue  
using namespace std; // Queues are defined in std Namespace 

int main()
{
    
	// Queue example 
	queue<int> Q;
	for(int i=1;i<=6;i++)
		Q.push(i); // Enter the team  Q：1 2 3 4 5 6
	Q.front() -= Q.back(); //Q：-5 2 3 4 5 6
	while(!Q.empty()) {
    
		cout<<Q.front()<<" ";
		Q.pop(); // Out of the team  
	} 
	return 0;
 } 

Example ： There is a stack of cards on the table , Start with the first card and number from top to bottom 1~n. When there are at least two cards left, do the following ： Throw away the first card , Then put the new first card behind the whole stack . Please enter the total number of cards n, Output the cards thrown each time , And the last two cards

 for example ： The total number of cards is 7
 Input :7
 Output :1 3 5 7 4
     2 6

Case code ：

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

int main()
{
    
	queue<int> q; // Declaration queue 
	int n;
	cin>>n; // Total number of cards output 
	for(int i=1;i<=n;i++)
		q.push(i);
	while(q.size()>2) {
    
		cout<<q.front()<<" "; // The first element of the output queue 
		q.pop(); // The first element in the queue is out of the queue 
		q.push(q.front()); // Put the first element of the current queue at the end of the queue 
		q.pop(); // Now the first element in the queue is out of the queue  
	} 
	cout<<endl;
	while(!q.empty()) {
     // The remaining elements in the output queue  
		cout<<q.front()<<" ";
		q.pop();
	}
	return 0;
}

Stack stack

Stack （stack） It's last in, first out LIFO（last in first out） The linear table . therefore , The tail of the table has a special meaning for the stack , It's called the top of the stack （top）, Accordingly , The header is called the bottom of the stack （bottom）, Empty tables without elements are called empty stacks

Stack defined in < stack > Header file

The prototype of stack class member function is as follows ：

//---- Capacity capacity----
bool empty(); // Test whether the stack is empty 
size_type size(); // Returns the stack length 

//---- Element access element access----
top(); // Back to top of stack element 

//---- Stack operation operations----
void push(const T& x); // Into the stack 
void pop(); // Out of the stack 

example ： Stack application example

#include<iostream>
#include<string>
#include<stack> // Use stack  
using namespace std; // Stack defined in std Namespace 

int main()
{
    
	// Stack example 
	stack<int> S;
	for(int i=1;i<=6;i++)
		S.push(i); // Into the stack  S：1 2 3 4 5 6
	while(!S.empty()) {
    
		cout<<S.top()<<" ";
		S.pop(); // Out of the stack  
	} 
	return 0; 
 } 

Example ： Solve with stack “ Symbol balance problem ”.< >,{ },[ ],( ) These symbols must appear in pairs , Enter a string , Determine whether the above symbols match

Their thinking ：
（1） If the character is an open symbol , Then push it into the stack
（2） If the character is a closed symbol , If the stack is empty, it is wrong ; Otherwise, the stack element will pop up . If the pop-up symbol is not the corresponding open symbol , False report
（3） At the end of the file , If the stack is not empty, an error is reported

Case code ：

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

bool isbalance(const string &str) {
    
	int len=str.size();
	stack<char> mystack;
	for(int i=0;i<len;i++) {
     // Traverse the characters in the string 
		// If it is a bracket, it will be pushed into the stack 
		if(str[i]=='[' || str[i]=='{' || str[i]=='(' || str[i]=='<')
			mystack.push(str[i]);
		// If it is a parenthesis 
		if(str[i]==']' || str[i]=='}' || str[i]==')' || str[i]=='>') {
    
			if(mystack.empty()) {
     // If the stack is empty , Then it means imbalance 
				cout<<"the string is Unblanced"<<endl;
				return false; 
			}
			switch(str[i]) {
    
				case ']':
					{
    	
						if('['!=mystack.top())
							return false;
						mystack.pop();
						break;
					}
				case ')':
					{
    	
						if('('!=mystack.top())
							return false;
						mystack.pop();
						break;
					}
				case '}':
					{
    	
						if('{'!=mystack.top())
							return false;
						mystack.pop();
						break;
					}
				case '>':
					{
    	
						if('<'!=mystack.top())
							return false;
						mystack.pop();
						break;
					}
			} // end switch structure  
		}
	}
	if(mystack.empty()) {
     // An empty stack means that the string is balanced 
		return true; 
	}
	else {
     // There is no correct match 
		mystack.pop();
		return false; 
	}
}

int main()
{
    
	bool bal;
	string str;
	cin>>str;
	bal=isbalance(str);
	if(bal)
		cout<<"string is blanced!"<<endl;
	else
		cout<<"string is unblanced!"<<endl;
	return 0;
}