链表、队列、栈的数组模拟
1.链表
1.1单向链表
1.“数组模拟静态链表”的原因
-
相较于通过定义结构体实现的单链表，不能实现随机存取，插入/去除任何一个元素都必须从指向表头的head指针出发
-
cpp中new()内存动态分配函数执行速度较慢，相较于直接定义数组长度要慢得多
2.实现思路（空间换时间）
在此基础上实现初始化、插入、删除等操作
3.代码实现
const int N = 1e5 + 5;
int val[N], nex[N], head, idx;
//head存储链表头
//val[]存储节点的值
//nex[]存储节点的next指针
//idx表示当前用到了哪个节点
void init() {
head = -1; //注意：这里的head并不是虚拟头节点，指向的就是链表的第一个节点，这样做主要是为了方便在头节点插入数据，最开始没有插入节点，head指向-1
idx = 0; //还没插入节点，idx为0
}
void insertBeforeHead(int x) {
val[idx] = x; //新插入一个值为x的节点
nex[idx] = head; //x的下一个节点是原来的头节点，表示在头节点之前插入x
head = idx; //head指针指向新节点
++idx; //更新插入节点的个数
}
//在第K个节点后插入一个节点
void Insert(int k, int x) {
val[idx] = x;
nex[idx] = nex[k];
nex[k] = idx;
++idx;
}
//删除指定节点，这里只用改变nex[]，不需要释放其空间
void Delete(int k) {
nex[k] = nex[nex[k]];
}
2.双向链表（仅代码实现）
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;
// 初始化
void init(){
//0是左端点，1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
// 在节点a的右边插入一个数x
void insert(int a, int x){
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx;
idx++;
}
// 删除节点a
void remove(int a){
l[r[a]] = l[a];
r[l[a]] = r[a];
}
2.栈（仅代码实现）
2.1普通实现
1.算法模板
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{
}
2.经典例题（用栈实现表达式求值）
-
本人代码实现：
#include
#include
using namespace std;
#define not_exist 9
#define ERROR -1
const int N = 1E5 + 10;
vector num;
vector sign;
//判断各符号之间的优先级，1表示优先，0表示同级，-1表示低一级，not_exist表示情况不存在
int priority[6][6] = {//第一个空是一个序列中从左到右的前一个符号，第二个空是后一个符号
/*
1是push_back
0是pop_back
-1是cal
*/
{1, 0, 1, 1, 1, 1},//相对于（
{1, 1, 1, 1, 1, 1},//相对于）
{1, -1, -1, -1, 1, 1},//相对于+
{1, -1, -1, -1, 1, 1},//相对于-
{1, -1, -1, -1, -1, -1},//相对于*
{1, -1, -1, -1, -1, -1},//相对于/
};
//识别一个运算符并定位到数组
int ident_sign (char sign) {
switch (sign) {
case '(':
return 0;
break;
case ')':
return 1;
break;
case '+':
return 2;
break;
case '-':
return 3;
break;
case '*':
return 4;
break;
case '/':
return 5;
break;
default:
return ERROR;
break;
};
}
//将str中的字符串读入到数字栈和运算符栈中,边度边算
int read_str_and_cal (string str) {
str.append(1,'+');//因为每次计算都是以符号为信号，所以最后有一步首尾工作
//str.push_back('+');
//str += '+';
for (int t = 0 ; t 1) {
int num2 = num.back(); num.pop_back();
int num1 = num.back(); num.pop_back();
sign.pop_back();
switch (c1) {//计算并压入num栈
case '+':
num.push_back(num1 + num2);
break;
case '-':
num.push_back(num1 - num2);
break;
case '*':
num.push_back(num1 * num2);
break;
case '/':
num.push_back(num1 / num2);
break;
default:
cout << "cal ERROR\n\n";
break;
}
}
goto loop;
break;
default:
printf("priority ERROR\n\n");
break;
}
}
else sign.push_back(str[t]);
}
}
return num[0];
}
int main () {
string str;
cin >> str;
int ans = read_str_and_cal(str);
cout << ans << endl;
return 0;
}
2.2单调栈
1.算法模板
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
2.经典例题（某个数左边最近比它小的数）
最开始AcWing上面单调栈的题因为没有看懂模板要干啥，所有用自己的想法写了一遍。虽然感觉也还算巧妙但确实比题解上面的写法差远了。这里附上原题、我的解法和题解解法帮助理解
-
原题题目
给定一个长度为
N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出−1。输入格式
第一行包含整数
N，表示数列长度。第二行包含N个整数，表示整数数列。输出格式
共一行，包含
N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出−1。数据范围
$$
1\le N \le 10^5 \
1\le 数列中的元素 \le 10^9
$$输入样例：
5 3 4 2 7 5输出样例：
-1 3 -1 2 2
-
自己的解法
#include
using namespace std;
const int N = 1e5 + 10;
int stack[N];//存放输入的数据
int t = 0;//指向栈顶的“指针”
struct record {
int value;
int site;
}min_l[N];//存放对于每一个点左边第一个比它小的数的“大小”和“坐标”
int main() {
int n; cin >> n;
//输入
for (int i = 0 ; i < n ; i ++ ) {
int x; cin >> x;
stack[++t] = x;
}
//min_1[1]
min_l[1].value = -1; min_l[1].site = -1;//site为-1表示该点不存在
cout << min_l[1].value << ' ';
for (int i = 2 ; i <= t ; i++) {
int k = i-1;
while (stack[k] >= stack[i]) {//出现左边的点比当前点要大
if (min_l[k].value >= stack[i])//不符合小于当前点i的条件，坐标跳转
k = min_l[k].site;
else {
min_l[i].value = min_l[k].value;
min_l[i].site = min_l[k].site;
break;
}
}
if (stack[k] < stack[i]) {//出现左边的点比当前点要小
min_l[i].value = stack[k];
min_l[i].site = k;
}
cout << min_l[i].value << ' ';
}
return 0;
}
-
使用“单调栈”算法模板的解法
#include
using namespace std;
const int N = 100010;
int stk[N], tt;
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
scanf("%d", &x);
while (tt && stk[tt] >= x) tt -- ;//如果栈顶元素大于当前待入栈元素，则出栈
if (!tt) printf("-1 ");//如果栈空，则没有比该元素小的值。
else printf("%d ", stk[tt]);//栈顶元素就是左侧第一个比它小的元素。
stk[ ++ tt] = x;
}
return 0;
}
3.队列（仅代码实现）
3.1普通队列
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{
}
3.2循环队列
// 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];
// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{
}
3.3单调队列
1.算法模板
常见模型：找出滑动窗口中的最大值/最小值
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;
}
2.经典例题（滑动窗口）
这个单调队列AcWing上面讲的老实讲，没看懂。参考了知乎上的一篇文章：算法学习笔记(66): 单调队列 - 知乎 (zhihu.com)，个人觉得写的还不错！比喻还算比较清晰。下面附上原题和相关代码。
-
原题链接：154. 滑动窗口 - AcWing题库
-
个人代码
#include
#include //双向队列
using namespace std;
const int N = 1e6 + 10;
int queue[N] = {0};
deque max_deque, min_deque;//双向队列中存储的是某个值在输入数据中对应的位置
int main() {
int n,k;
cin >> n >> k;
int total_win = n - ( k-1 );
int max_k[total_win] = {0}, min_k[total_win] = {0};//存储滑动窗口的最大最小值
//输入数据
for (int i = 0 ; i < n ; i++ ) cin >> queue[i];
//初始化双向队列max_deque, min_deque; 求出第一个滑动窗口(序号为0)的max与min
max_deque.push_back(0);
for (int i = 1 ; i < k ; i ++ ) {//此时i表示是第几个数据
while (max_deque.size() > k-1) max_deque.pop_front();//必须给新的元素留空
while (!max_deque.empty() and queue[max_deque.back()] <= queue[i]) max_deque.pop_back();
max_deque.push_back(i);
}
max_k[0] = max_deque.front();
min_deque.push_back(0);
for (int i = 1 ; i < k ; i ++ ) {
while (min_deque.size() > k-1) min_deque.pop_front();//必须给新的元素留空
while (!min_deque.empty() and queue[min_deque.back()] >= queue[i]) min_deque.pop_back();
min_deque.push_back(i);
}
min_k[0] = min_deque.front();
//从第二个滑动窗口开始，对( n - ( k-1 ) )个窗口进行计算维护
for (int i = 1 ; i < total_win ; i++) {//此时i表示是第几个滑动窗口
//维护最大值
while (!max_deque.empty() and max_deque.front() < i) max_deque.pop_front();//保证队首元素位置在当前窗口内
while (max_deque.size() > k-1) max_deque.pop_front();//必须给新的元素留空
while (!max_deque.empty() and queue[max_deque.back()] <= queue[k-1 + i]) max_deque.pop_back();//维护队尾元素
max_deque.push_back( k-1 + i );
max_k[i] = max_deque.front();
//维护最小值
while (!min_deque.empty() and min_deque.front() < i) min_deque.pop_front();//保证队首元素位置在当前窗口内
while (min_deque.size() > k-1) min_deque.pop_front();//必须给新的元素留空
while (!min_deque.empty() and queue[min_deque.back()] >= queue[k-1 + i]) min_deque.pop_back();//维护队尾元素
min_deque.push_back( k-1 + i );
min_k[i] = min_deque.front();
}
//输出
for (int i = 0 ; i < total_win ; i++) cout << queue[min_k[i]] << ' ';
cout << endl;
for (int i = 0 ; i < total_win ; i++) cout << queue[max_k[i]] << ' ';
return 0;
}
-
题解代码
#include
#include
#include
#include
using namespace std;
const int N = 1000010;
int a[N];
int main()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i ++ ) cin >> a[i];//读入数据
deque q;
for(int i = 1; i <= n; i++)
{
while(q.size() && q.back() > a[i]) //新进入窗口的值小于队尾元素，则队尾出队列
q.pop_back();
q.push_back(a[i]);//将新进入的元素入队
if(i - k >= 1 && q.front() == a[i - k])//若队头是否滑出了窗口，队头出队
q.pop_front();
if(i >= k)//当窗口形成，输出队头对应的值
cout << q.front() <<" ";
}
q.clear();
cout << endl;
//最大值亦然
for(int i = 1; i <= n; i++)
{
while(q.size() && q.back() < a[i]) q.pop_back();
q.push_back(a[i]);
if(i - k >= 1 && a[i - k] == q.front()) q.pop_front();
if(i >= k) cout << q.front() << " ";
}
}
