Stack, monotone stack, queue, monotone queue

---

One 、 What are stacks and queues ？

A stack is a last in, first out （Last in First out） The linear table , abbreviation LIFO, Insert and delete operations are only allowed at one end ;
A queue is a first in, first out （FIrst in First out） The linear table , abbreviation FIFO, Insertion is only allowed at one end , Delete at the other end .

---

1. Implementation principle of stack

The core operation of stack with stack is stack top stack 、 There are two operations of stack top and stack out , Pictured ：

Yes 1 ,3 ,2 ,4 ,5 Perform the operations of entering and exiting the stack respectively

See here for the application and operation of stack

---

2.1 Monotonic stack

seeing the name of a thing one thinks of its function , A monotone stack is a stack with monotone properties
Right now 1 ,3 ,2 ,4 ,5 Perform simulation operations

• 1 When entering the stack , The stack is empty. , Direct stack , The elements in the stack are ：1
• 3 When entering the stack , Top element of stack 1 Than 3 Small ,1 Out of the stack , The stack is empty. ,3 Push , The elements in the stack are ：3
• 2 When entering the stack , Top element of stack 3 Than 2 Big , Direct stack , The elements in the stack are ：3,2
• 4 When entering the stack , Top element of stack 2 Than 4 Small ,2 Out of the stack , Top element of stack 3 Than 4 Small ,3 Out of the stack , The stack is empty. ,4 Push , The elements in the stack are ：4
• 5 When entering the stack , Top element of stack 4 Than 5 Small ,4 Out of the stack , The stack is empty. ,5 Push , The elements in the stack are 5

---

Pseudo code

for ( Traversal array ){
    
	if ( The stack is empty  ||  Top element of stack  >=  The current element ){
    
		 Push ;
	} else {
    
		while ( Stack is not empty.  &&  Top element of stack  <  The current element ){
    
			 Stack top element out of stack ;
		}
		 The current element is put on the stack ;
	}
}

2.3 Application example

Title source ：acwing 830. Monotonic stack

Title Description :

Given a length of N The whole number sequence of , Output the first number smaller than it on the left of each number , If not, output −1.

Input format

The first line contains integers N, Represents the length of a sequence .

The second line contains N It's an integer , Represents an integer sequence .

Output format

All in one line , contain N It's an integer , Among them the first i The number represents the number i The first smaller number on the left of the number , If not, output −1.

Data range

1≤N≤105
1≤ The elements in the sequence ≤109

sample input

5
3 4 2 7 5

sample output

-1 3 -1 2 2

Analog monotone stack ：

    #include <iostream>
    
    using namespace std;
    
    const int N=100010;
    
    int n;
    int skt[N],tt;
    
    int main()
    {
    
    	cin>>n;
    	while(n--)
    	{
    
    		int x;
    		cin>>x;
    		while(tt&&skt[tt]>=x)	tt--;
    		if(tt)	cout<<skt[tt]<<' ';
    		else	cout<<-1<<' ';
    		
    		skt[++tt]=x; 
    	}
    	return 0;
     } 

3.1 queue

Yes 1, 3, 2, 4, 5 The simulation operation is shown in the figure

3.2 Application example

Title source ：acwing 829. Simulation queue

Title Description :

Implement a queue , The queue is initially empty , Four operations are supported ：

• push x – Insert a number at the end of the line x;
• pop – Pop a number from the head of the team ;
• empty – Determines if the queue is empty ;
• query – Query the queue header element .

Now we're going to... The queue M Operations , Each of these operations 3 And operation 4 Output the corresponding results .

Input format

The first line contains integers M, Indicates the number of operations .

Next M That's ok , Each line contains an action command , The operation command is push x,pop,empty,query One of the .

Output format

For each empty and query All operations need to output a query result , Each result takes up one line .

among ,empty The query result of the operation is YES or NO,query The query result of the operation is an integer , Represents the value of the queue header element .

Data range

1≤M≤100000,
1≤x≤109,
All operations are legal .

sample input

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

sample output

NO
6
YES
4

Don't use stl

#include <iostream>

using namespace std;

const int N=100010;

int hh,tt=-1;
int q[N];

int main ()
{
    
    int x,m;
    string op;
    
    cin>>m;
    while(m--)
    {
    
        cin>>op;
        if(op=="push")
        {
    
            cin>>x;
            q[++tt]=x;
        }
        else if(op=="pop")  hh++;
        else if(op=="empty")
        {
    
            if(hh<=tt)  cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
        else cout<<q[hh]<<endl;
    }
    return 0;
}

Use stl

#include <iostream>
#include <queue>

using namespace std;

queue<int> q;

int main()
{
    
	int x,m;
    string op;
    
    cin>>m;
    while(m--)
    {
    
        cin>>op;
        if(op=="push")
        {
    
            cin>>x;
            q.push(x);
        }
        else if(op=="pop")  q.pop();
        else if(op=="empty")
        {
    
            if(q.size())  cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
        else cout<< q.front() <<endl;
    }
    return 0;
}

4.1 A monotonous queue

Same as monotone stack , Monotone queues are queues with monotone properties
As shown in the figure 1, 3, 2, 4, 5 Perform monotonic queue operation

To take the minimum value , Maintain a monotonically increasing queue

• 1 When you join the team , The queue is empty , Join the team directly , Elements in the team ：1
• 3 When you join the team , Team tail element 1 Less than 3, Join the team directly , Elements in the team ：1,3
• 2 When you join the team , Team tail element 3 Greater than 2, Fork out 3, Team tail element 1 Less than 2,2 The team , Elements in the team ：1,2
• 4 When you join the team , Team tail element 2 Less than 4,4 The team , Elements in the team ：1,2,4
• 5 When you join the team , Team tail element 4 Less than 5,5 The team , Elements in the team ：1,2,4,5

4.2 Application example

Title source ：acwing 154. The sliding window

Title Description :

Given a size of n≤10^6 Array of .

There is a size of k Sliding window of , It moves from the far left to the far right of the array .

You can only see in the window k A digital .

Move the window one position to the right each time .

Here is an example ：

The array is [1 3 -1 -3 5 3 6 7],k by 3.

window position	minimum value	Maximum
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3[ 5 3 6] 7	3	6
1 3 -1 -3 5[ 3 6 7]	3	7

Your task is to make sure that the sliding window is in each position , Maximum and minimum values in the window .

Input format

The input contains two lines .

The first line contains two integers n and k, Represents the length of the array and the length of the sliding window .

The second line has n It's an integer , Represents the specific value of an array .

Separate peer data with spaces .

Output format

The output contains two .

The first line outputs , From left to right , Minimum value in each position slide window .

The second line outputs , From left to right , Maximum value in each position slide window .

sample input

8 3
1 3 -1 -3 5 3 6 7

sample output

-1 -3 -3 -3 3 3
3 3 5 5 6 7

yxc’s solution

#include <iostream>
#include<algorithm>

using namespace std;

const int N=1000010;

int n,k;
int a[N],q[N]; 

int main()
{
    
	scanf("%d%d",&n,&k);
	
	for (int i=0;i<n;i++)	scanf("%d",&a[i]);
	
	int hh=0,tt=-1;
	for (int i=0;i<n;i++)
	{
    
		if(hh <= tt && q[hh] < i-k+1)	hh++;
		while(hh <= tt && a[q[tt]]>=a[i])	tt--;
		q[++tt]=i;
		
		if(i>=k-1)	printf("%d ",a[q[hh]]);
	}
	puts("");
	
	hh=0,tt=-1;
	for (int i=0;i<n;i++)
	{
    
		if(hh <= tt && q[hh] < i-k+1)	hh++;
		while(hh <= tt && a[q[tt]]<=a[i])	tt--;
		q[++tt]=i;
		
		if(i>=k-1)	printf("%d ",a[q[hh]]);
	}
	
	return 0;
}