1, First of all, we should understand the concept of stack. In c + +, STL exists, which can facilitate us to do many things, and stack is a part of it. In short, stack is a kind of first in and last out data organization

By thinking and simulating the structure of stack, we find that we can use one-dimensional array and a variable tt to realize the data structure of stack

stk[100010] is used to represent stack. tt represents a pointer

Stack read operation

//  add  insert
int x;
cin>>x;
stk[++tt]  = x; // Here, I start the subscript of the stack from 1 to distinguish it from the queue
                // So we have read x into our simulation stack

Pop up operation of stack

// remove
tt--;//In this way, the element of the team head has been ejected

Because the stack is similar to the barrel, and tt# it always points to the top of the barrel; So when {TT}, the top element will pop up

This question comes from AcWing question 830 and is also about the application of monotone stack

Given an integer sequence with a length of − NN, output the first number smaller than it on the left of each number. If it does not exist, output − 1 − 1.

Input format

The first row contains the integer NN, which represents the length of the sequence.

The second row contains {NN} integers, representing the integer sequence.

Output format

There is one line in total, including − NN integers, where the − ii − number represents the first number smaller than it on the left of the − ii − number. If it does not exist, it outputs − 1 − 1.

Data range

1≤N≤1051≤N≤105
1 ≤ elements in sequence ≤ 1091 ≤ elements in sequence ≤ 109

Input example:

5
3 4 2 7 5

Output example:

-1 3 -1 2 2

This is the solution

#include <iostream>

using namespace std;

const int N = 1e5 +10;

int stk[N],tt;
int a[N];
int main(void)
{
    int n;
    cin>>n;
    for(int i = 0;i<n;i++)
    {
        while(tt && stk[tt] > a[i]) tt--; // Here, the elements in the array will be traversed to pop up the number greater than the value
                                          // Because the first value less than a[i] is found in the meaning of the question
                                          // If the previous value is greater than a[i], the next values are
                                          // The value is not selected
        if(!tt) cout<<"-1";
        stk[++tt] = x;
    }
}

Let's simulate the queue. The queue is also a container in STL. The difference between it and the stack is first in first out, which is similar to the water pipe,

That is, enter from the end of the team and eject from the opposite end

Similarly, through the simulation of queue, we can also use array to realize the function of queue

q[100010] , tt , hh;

hh team leader

tt team tail

Read in operation of queue

// add
hh = 0,tt = -1;// Here we set the subscript of the queue to separate from the stack from the beginning
int x;
cin>>x;
q[++tt] = x;// Inserted elements from the end of the team

Queue pop-up

// remove
hh++;

The pop-up here is also somewhat similar to the stack pop-up, hh is equivalent to the upper part of a water pipe, and tt is equivalent to the lower part

When hh + +, it is equivalent to hh moving down, so the element q[hh] in front of hh will be ejected

 

This question comes from the sliding window problem of AcWing question 154

Give an array with a size of n ≤ 106n ≤ 106.

There is a sliding window with a size of {kk}, which moves from the leftmost to the rightmost of the array.

You can only see kk{numbers in the window.

Slide the window one position to the right at a time.

Here is an example:

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

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 determine the maximum and minimum values in the window when the sliding window is in each position.

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.

Peer data is separated by spaces.

Output format

The output contains two.

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

The second line outputs the maximum value in the sliding window from left to right in each position.

Input example:

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

Output example:

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

The following is the solution

#include <iostream>
using namespace std;
const int N = 1e6 +10;

int q[N];
int a[N];
int hh,tt = -1;
int main(void)
{
    int n,k;
    cin>>n>>k;// n represents the length of the array and k represents the length of the window
    for(int i = 0;i<n;i++) cin>>a[i];
    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--; // Here, all elements larger than a[i] are bounced out
                                                  //Because if the last person in the queue comes in more than the first one
                                                  //If it is small, all the previous values will not be used
                                                  //In order to pop up the useless elements, let's find the large value
                                                  //Time is also a truth
        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]]);
    }
    cout<<endl;
}

 

Some people may have doubts that STL can be used. Why should we bother to simulate it? This is because simulating STL can save a lot of time and optimize the efficiency of the program, which is particularly important when doing algorithm problems