# yxc_ Chapter II data structure_ Stack and queue

catalogue

1, Code operation of stack and queue

1. AcWing 828 simulation stack

2. AcWing 829 analog queue

2, Monotone stack

1. AcWing 830 monotone stack

3, Monotone queue

1. AcWing 154 sliding window

# 1, Code operation of stack and queue

## 1. AcWing 828 simulation stack

Implement a stack. The stack is initially empty and supports four operations:

1. push x – insert a number # x to the top of the stack;
2. Pop – pop a number from the top of the stack;
3. Empty – judge whether the stack is empty;
4. Query – query the top element of the stack.

Now we need to perform M # operations on the stack, in which each operation # 3 # and operation # 4 # should output the corresponding results.

Input format

The first line contains the integer M, indicating the number of operations.

Next, there are # M # lines. Each line contains an operation command. The operation command is one of # push x, pop, empty, query #.

Output format

For each "empty" and "query" operation, a query result should be output, and each result occupies one row.

Where, the query result of empty ， operation is ， YES ， or ， NO, and the query result of query ， operation is an integer representing the value of the top element of the stack.

Data range

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

Input sample:

```10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty
```

Output example:

```5
5
YES
4
NO```
```#include<iostream>
using namespace std;

const int N = 100010;

int stk[N], tt;//stk[N] is the array simulation stack, tt is the pointer pointing to the top element of the stack

int main()
{
int m;
cin >> m;

while (m -- )
{
string op;
cin >> op;

//insert
if (op == "push")
{
int x;
cin >> x;
stk[ ++ tt] = x;
}
else if (op == "pop") tt -- ;//eject
else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;//Determine whether the stack is empty
else cout << stk[tt] << endl;//Output stack top element
}

return 0;
}```

## 2. AcWing 829 analog queue

Implement a queue. The queue is initially empty and supports four operations:

1. push x – insert a number # x to the end of the team;
2. Pop – pop a number from the head of the team;
3. Empty – judge whether the queue is empty;
4. Query – query the queue header element.

Now we need to perform M # operations on the queue, and each of the operations # 3 # and # 4 # should output the corresponding results.

Input format

The first line contains the integer M, indicating the number of operations.

Next, there are # M # lines. Each line contains an operation command. The operation command is one of # push x, pop, empty, query #.

Output format

For each "empty" and "query" operation, a query result should be output, and each result occupies one row.

Where, the query result of empty operation is YES or NO, and the query result of query operation is an integer representing the value of the queue head element.

Data range

1≤M≤100000
1≤x≤109
All operations shall be legal.

Input sample:

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

Output example:

```NO
6
YES
4```
```#include<iostream>
using namespace std;

const int N = 100010;

int q[N], hh, tt = -1;//hh points to the team head element and tt points to the team tail element

int main()
{
int m;
cin >> m;

while (m -- )
{
string op;
cin >> op;

//Insert element at end of queue
if (op == "push")
{
int x;
cin >> x;
q[ ++ tt] = x;
}
else if (op == "pop") hh ++ ;//Pop up the queue header element. Note that this is + + instead of--
else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;//Judge whether the queue is empty
else cout << q[hh] <<endl;//Output header element
}

return 0;
}```

# 2, Monotone stack

Monotone stack is more abstract, but there are not many question types that will be investigated. Almost only the question types such as AcWing 830 are investigated, so I only train for the question.

## 1. AcWing 830 monotone stack

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

Input format

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

The second row contains N # integers, representing the integer sequence.

Output format

A total of one line, including − N integers, where the − i − number represents the first number smaller than it on the left of the − i − number. If it does not exist, it outputs − 1.

Data range

1≤N≤105
1 ≤ element in sequence ≤ 109

Input sample:

```5
3 4 2 7 5
```

Output example:

`-1 3 -1 2 2`
```#include<iostream>
using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
int m;
cin >> m;

while (m -- )
{
int x;
cin >> x;

while (tt && stk[tt] >= x) tt -- ;

if (!tt) cout << "-1 ";
else cout << stk[tt] << " ";

stk[ ++ tt] = x;
}

return 0;
}```

The so-called monotone stack is actually a tool used to output the nearest number to the left of each number that is smaller than it. For each number in the sequence, we first make a judgment before entering the stack: if the stack is empty, there is no number on the left, let alone find a number smaller than x; If the stack is not empty and the top element is greater than or equal to x, the top element will pop up (because the top element will never be output due to the existence of X, leaving it in the stack will hinder). By constantly popping up stack top elements larger than x, the stack top elements must be smaller than X after the while loop ends. The stack obtained by this operation can keep the elements monotonically increasing all the time, so it is called monotonic stack.

# 3, Monotone queue

## 1. AcWing 154 sliding window

Give an array with a size of n ≤ 106.

There is a sliding window with the size of ， k ， which moves from the leftmost to the rightmost of the array.

You can only see k# 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 k  is  3.

window positionminimum valueMaximum
[1 3 -1] -3 5 3 6 7-13
1 [3 -1 -3] 5 3 6 7-33
1 3 [-1 -3 5] 3 6 7-35
1 3 -1 [-3 5 3] 6 7-35
1 3 -1 -3 [5 3 6] 736
1 3 -1 -3 5 [3 6 7]37

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 n and k, representing the length of the array and the length of the sliding window, respectively.

The second line has n # 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 sample:

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

Output example:

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

Before using monotone queue optimization, the time complexity of violent practice is O(nk).

```#include<iostream>
using namespace std;

const int N = 1000010;

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

int main()
{
int k;
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 && i - k + 1 > q[hh]) hh ++ ;
//This ensures that the elements in the queue are always a subset of the elements in the window
while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
//Ensure that the queue increases monotonically, that is, the queue head element is the minimum value of the element in the window
q[ ++ tt] = i;
//q[N] the array stores the subscripts of the elements of the sequence
if (i >= k - 1) printf("%d ", a[q[hh]]);
//When I > = k-1 (the starting position where the window is filled with elements), the queue head element is output
//a[q[hh]] represents the smallest number of window elements
}

puts("");//enter

hh = 0, tt = -1;//initialization

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 -- ;
//Ensure that the queue decreases monotonically, that is, the queue head element is the maximum value of the element in the window
q[ ++ tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
//When I > = k-1 (the starting position where the window is filled with elements), the queue head element is output
//a[q[hh]] indicates the maximum number of values in the window element
}

puts("");//enter

return 0;
}```

HH < = TT can ensure that the statement is not executed when the queue is empty, and the elements are added into the queue first.

Keywords: data structure

Added by ryanbutler on Thu, 03 Feb 2022 06:35:31 +0200