栈与队列

2.1栈

思路

1. 初始化栈
2. 判断栈是否为空
3. 将元素压入栈
4. 获得栈顶元素
5. 从栈顶弹出一个元素

代码

初始化栈

int N=100010;
int stk[N],tt=0;

向栈顶插入一个数

stk[++tt]=x;

从栈顶弹出一个数

tt--

获得栈顶元素

stk[tt]

判断栈是否为空

if(tt>0)

2.2队列

思路

1. 向队尾插入一个数
2. 从队头弹出一个数
3. 队头的值
4. 判断队列是否为空

代码

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)
{

}

2.3循环队列

思路

1. 向队尾插入一个数
2. 从队头弹出一个数
3. 队头的值
4. 判断队列是否为空

代码

// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt)
{

}

2.3单调栈

思路

单调栈（Monotone Stack）：一种特殊的栈。在栈的先进后出规则基础上，要求从栈顶到栈底 的元素是单调递增（或者单调递减）。其中满足从栈顶到栈底的元素是单调递增的栈，叫做「单调递增栈」。满足从栈顶到栈底的元素是单调递减的栈，叫做「单调递减栈」

单调递减栈：

1. 假设当前进栈元素为 x，如果栈顶元素大于 x，则直接入栈
2. 否则从栈顶开始遍历栈中元素，把大于 x 或者等于 x 的元素弹出栈，直到遇到一个小于 x 的元素为止，然后再把 x 压入栈中

代码

找出每个数左边离它最近的比它大/小的数：

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int n;
int stk[N], tt;

int main() {
	cin >> n;
	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 << endl;
		stk[++tt] = x;
	}
	return 0;
}

2.4单调队列

代码

常见模型：找出滑动窗口中的最大值/最小值

int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

题目

链接：https://leetcode.cn/problems/sliding-window-maximum

代码

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int hh=0,tt=-1;
        vector<int> res;
        int q[100100];
        int size=nums.size();
        for(int i=0;i<size;i++)
        {
            if(hh<=tt &&i-k+1>q[hh]) hh++;
            while(hh<=tt && nums[i]>nums[q[tt]]) tt--;
            q[++tt]=i;
            if(i-k+1>=0) res.push_back(nums[q[hh]]);
        }
        return res;
    }