acwing算法基础之数据结构--栈和队列

1 知识点

栈：先进后出。先进的就是栈底，后进的就是栈顶。后进先出嘛，所以在栈顶弹出元素。

队列：先进先出。先进的就是队头，后进的就是队尾。先进先出嘛，所以在队头弹出元素。

单调栈：输入数组，求每个元素左边的某个元素，满足（1）比它小，（2）离它最近。

//输入数组nums
//输出上述要求的数值
for (int i = 0; i < nums.size(); ++i) {while (tt && stk[tt] >= nums[i]) {tt--;}if (tt) {cout << stk[tt] << " ";} else {cout << "-1 ";}stk[++tt] = nums[i];
}
cout << endl;

单调队列：求滑动窗口中的最大值或最小值，

//输入数组nums，区间长度k
//（1）找到滑动窗口的最小值
int hh = 0, tt = -1;
for (int i = 0; i < nums.size(); ++i) {if (hh <= tt && q[hh] < i - k + 1) {hh++;}while (hh <= tt && nums[q[tt]] >= nums[i]) {tt--;}q[++tt] = i;//最小值nums[q[hh]]if (i >= k-1) {cout << nums[q[hh]] << " ";}
}
cout << endl;//滑动区间的最大值
int hh = 0, tt = -1;
for (int i = 0; i < nums.size(); ++i) {if (hh <= tt && q[hh] < i - k + 1) {hh++;}while (hh <= tt && nums[q[tt]] <= nums[i]) {tt--;}q[++tt] = i;//最大值nums[q[hh]]if (i >= k - 1) {cout << nums[q[hh]] << " ";}
}
cout << endl;

用数组来模拟上述数据结构。

2 模板

（一）用数组来模拟栈的模板，

const int N = 1e6 + 10;
int stk[N], tt = 0;//tt表示栈顶下标，stk[tt]表示栈顶的值。//（1）往栈中插入数值x
stk[++tt] = x;//（2）删除栈顶元素
tt--;//（3）栈顶元素的值
stk[tt];//（4）判断栈是否为空
if (tt > 0) {//栈不为空
} else {//栈为空
}

（二）用数组来模拟队列的模板，

const int N = 1e6 + 10;
int q[N], hh = 0, tt = -1;//hh表示队头下标，tt表示队尾下标。q[hh]表示队头的值，q[tt]表示队尾的值。//（1）往队列中插入数值x
q[++tt] = x;//（2）往队列中删除元素
hh++;//（3）取队头元素
q[hh];//（4）取队尾元素
q[tt];//（5）判断队列是否为空
if (hh <= tt) {//队列不为空
} else {//队列为空
}