# Stack and Queue

## 2. Definition of stack

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=100010;

int stk[N],tt;

//insert
stk[++tt]=x;

//Eject
tt--;

//Determine if stack is empty
if(tt>0) not empty
else empty

//Top of Stack
stk[tt];

```

## 3. Queue Definition

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=100010;

//Insert element at end of queue, eject element at head
int q[N],hh,tt = -1;//hh for the head and tt for the tail

//insert
q[++tt]=x;

//Eject
hh++;

//Determine whether it is empty
if(hh<=tt) not empty
else empty

q[hh]

//Remove the tail element
q[tt]

```

Picture in the form of Queue Popup_

## 4. Monotonic Stack

Given an integer column of length N, output the first number to the left of each number smaller than it, or output 1 if it does not exist.

#### Input Format

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

The second row contains N integers, representing an integer column.

#### Output Format

A row containing N integers, where the number i represents the first number to the left of the number i that is smaller than it and outputs 1 if it does not exist.

#### Data Range

1 ≤ N ≤ 105
Elements in columns 1 or less < 109

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

#### Output sample:

```-1 3 -1 2 2
```

#### AC Code

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=100010;

int n;
int stk[N],tt;

int main()
{
cin>>n;

//Delete all points in reverse order, and the remaining points must monotonically increase
for(int i=0;i<n;i++)
{
int x;
cin>>x;
while(tt && stk[tt]>=x)
{
tt--;
}
if(tt)
{
cout<<stk[tt]<<' ';
}
else
{
cout<<-1<<" ";
}

stk[++tt] = x;
}
}

```

## 5. Monotonic Queue (Sliding Window)

Given an array of size n < 106.

There is a sliding window of size k that moves from the leftmost to the rightmost side of the array.

You can only see k numbers in the window.

Slide 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 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 sliding window at each location.

#### Input Format

The input contains two lines.

The first row contains two integers, n and k, representing the length of the array and the length of the sliding window, respectively.

The second row 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 of output, from left to right, slides the minimum value in the window at each location.

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

#### Input sample:

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

#### Output sample:

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

#### thinking

Two steps for each move:

1. Insert new elements at the end of the queue
2. Elements that slip out pop up from the end of the queue

#### Practices for monotonic stacks and queues:

They use violence to simulate the problem first, then find out which elements in the stack and queue are not useful in the simple algorithm, delete all the useful elements, and then see if they are monotonic. If the remaining elements are monotonic, they can be optimized. If you take the extreme value, it becomes two endpoints. If you find a value, you can use two points...

#### AC Code

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1000010;

int a[N],q[N];

int main()
{
int n,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++)
{
//Determine if the team leader has slid out of the window
if(hh <= tt && i - k + 1 > q[hh])//The window will only go one bit to the right, so only one last number is not in the window at a time
{
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++)
{
//Determine if the team leader has slid out of the window
if(hh <= tt && i - k + 1 > q[hh])//The window will only go one bit to the right, so only one last number is not in the window at a time
{
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;
}
```

Keywords: C++ Algorithm data structure

Added by markjia on Thu, 10 Mar 2022 19:03:08 +0200