Here we are talking about using arrays to simulate stacks and queues, not the subsequent STL. Monotonic stacks and queues are interesting, and the monotonic stacks and queues are the main ones here, while the ordinary stacks and queues for array emulation are passed over.

The stack

Stack is a kind of data structure called “in, out”. We can think of it as putting things in a bucket, and the earlier you put them, the later you take them out.

Ordinary stack

The implementation of a normal stack is as follows

// tt represents the top of the stack
int stk[N], tt = 0;

// Insert a number to the top of the stack
stk[ ++ tt] = x;

// Pop a number from the top of the stack
tt -- ;

// The top value of the stack
stk[tt];

// Check whether the stack is empty
if (tt > 0) {}Copy the code

Monotonous stack

A monotone stack is a stack in which the elements are monotone. The basic purpose is to find the elements of a number that satisfy certain conditions in the stack. For example, for each number, find the number that meets the following conditions: the nearest and largest (small) number on the left. If the number at the top of the stack is larger than the number at the top of the stack, the number at the top of the stack will be popped until the number at the top of the stack is smaller than it. Construct a monotone stack

Example -AcWing 830. Monotone stack

Given an integer sequence of length NN, print the first number to the left of each number less than it, or −1−1 if none exists.

Input format

The first line contains the integer NN, which represents the length of the sequence. The second row contains NN integers, representing the integer sequence.

The output format

It contains NN integers, where the iith number is the first number to the left of the iith number that is smaller than it. If it does not exist, the output is −1−1.

Data range

1≤N≤1051≤N≤105 1≤ Elements in the sequence ≤1091≤ Elements in the sequence ≤109

Example Input:

5, 3, 4, 2, 7, 5Copy the code

Example output:

Minus 1, 3, 1, 2, 2Copy the code

Code implementation

/* * @Author: IndexYang * @Date: 2021-11-19 16:52:16 * @Last Modified by: IndexYang * @Last Modified time: The 2021-11-23 21:17:37 * /
 
#include<iostream>
using namespace std;
const int N = 100010;
int stk[N],tt; //tt points to the top of the stack
int n;
int main(a){
    cin >> n;
    for(int i = 0; i < n; i++){
        int x;
        cin>>x;
        // Pop the top of the stack until the number is smaller than it; Construct a monotone stack
        while(tt && stk[tt] >= x) tt--;
        if(tt) cout<<stk[tt]<<' ';
        else cout<<- 1<<' ';
        
        // push x onto the stack
        tt++;
        stk[tt] = x;
    }
    return 0;
}
Copy the code

The queue

Queue, however, is a first-in, first-out data structure, which is more consistent with our daily cognitive regulation. First-come, first-served, first-served, first-go, which can be understood as going to the canteen for dinner. Those who go first finish eating first leave the canteen.

The average queue

The implementation of a normal queue is as follows

// hh indicates the head of the team and tt indicates the tail of the team
int q[N], hh = 0, tt = - 1;

// Insert a number to the end of the queue
q[ ++ tt] = x;

// Pop a number from the queue head
hh ++ ;

// Queue header value
q[hh];

// Check whether the queue is empty
if (hh <= tt)
{

}
Copy the code

The monotonous queue

Application is also relatively simple, see the example.

Example -AcWing 154. Sliding Windows

Given an array of size N ≤106n≤106.

There is a sliding window of size KK that moves from the left to the right of the array.

You can only see kK numbers in the window.

You move the window one position to the right at a time.

Here’s an example:

The array is [1 3-1-3 5 3 6 7] and kk is 33.

Your task is to determine the maximum and minimum values in the sliding window at each location.

Input format

The input contains two lines.

The first line contains two integers nn and kk, representing the length of the array and the length of the sliding window, respectively.

The second line has nn integers representing the specific values of the array.

Data in the same row are separated by Spaces.

The output format

The output contains two.

The first line outputs, from left to right, the minimum value in the sliding window at each position.

The second line of output, from left to right, slides the maximum value in the window at each position.

Example Input:

Eight, three, one, three, three, five, three, six, sevenCopy the code

Example output:

Minus 1, 3, 3, 3, 3, 5, 5, 6, 7Copy the code

Code implementation

/* * @Author: IndexYang * @Date: 2021-11-23 21:16:26 * @Last Modified by: IndexYang * @Last Modified time: The 2021-11-23 23:18:48 * /
 
#include<iostream>
using namespace std;

const int N = 1000010;
int n,k;
int a[N],q[N];
// the real index stored in the q array
int main(a){
    cin>>n>>k;
    for(int i = 0; i<n; i++) cin>>a[i];int hh=0,tt=- 1;
    for(int i =0; i<n; i++){// Check if you have slid out of the window, if so, move forward
        if(hh <= tt && i-k+1 > q[hh]) hh++;
        // if a[I] is longer than the number at the end of the queue, delete the end of the queue
        while(hh<=tt && a[q[tt]]>= a[i]) tt--;
        // add the new index to the queue
        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 && i-k+1 > q[hh]) hh++;
        while(hh<=tt && a[q[tt]] <= a[i]) tt--;
        q[ ++tt] = i;
        if(i>= k- 1) printf("%d ",a[q[hh]]);
    }
    puts("");
    
    return 0;
}
Copy the code