您现在的位置是：首页 >技术杂谈 >day05.数据结构--1（链表+栈+队列+kmp）网站首页技术杂谈
day05.数据结构--1（链表+栈+队列+kmp）
简介day05.数据结构--1（链表+栈+队列+kmp）
本节均用数组模拟。
一、单链表与邻接表：树与图的存储
单链表多用于邻接表，存储树和图；双链表多用于优化一些问题。
1.思想&&模板
// head存储链表头，idx表示当前用到了哪个节点或指节点个数
// e[]存储节点的值，ne[]存储节点的next指针
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0; // 单链表目前无节点
}
// 在链表头插入一个数a
void insert(int a)
{
e[idx] = a; // 插入是元素是链表中第idx个节点
ne[idx] = head;
head = idx;
idx++;
}
// 将头结点删除，需要保证头结点存在
void remove()
{
head = ne[head];
}
2.题目（AcWing 826.单链表）
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int head, idx;
int e[N], ne[N];
void init() {
head = -1;
idx = 0;
}
void add_to_head(int x) {
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
void remove(int k) { // 删除第k个插入的数后面的数
ne[k - 1] = ne[ne[k - 1]];
}
void add(int k, int x) { // 在第k个插入的数后面插入x
e[idx] = x;
ne[idx] = ne[k - 1];
ne[k - 1] = idx;
idx++;
}
int main() {
int m;
cin >> m;
init();
while (m--) {
int k, x;
char op[2];
cin >> op;
if (op[0] == 'H') {
cin >> x;
add_to_head(x);
} else if (op[0] == 'D') {
cin >> k;
if (!k) // k不合法时
head = ne[head];
remove(k);
} else {
cin >> k >> x;
add(k, x);
}
}
for (int i = head; i != -1; i = ne[i]) { // ！！遍历链表
cout << e[i] << ' ';
}
cout << endl;
return 0;
}
二、双链表
1.思想&&模板
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
//0是左端点，1是右端点。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的左边插入一个数，则insert(a-1,x)
// 删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}
2.题目（AcWing 827.双链表）
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int idx;
int e[N], l[N],r[N];
void init() {
r[0] = 1;
l[1] = 0;
idx = 2;
}
void remove(int k) { // 删除第k个点
r[k] = r[r[k]];
l[k] = l[l[k]];
}
void add(int k, int x) {
e[idx] = x;
r[idx] = r[k],l[idx] = k;
l[r[k]] = idx,r[k] = idx;
idx++;
}
int main() {
int m;
cin >> m;
init();
while (m--) {
int k, x;
char op[2];
cin >> op;
if (op[0] == 'L') {
cin >> x;
add(0,x); // 0的右边就是最左侧的位置
}else if (op[0] == 'R') {
cin >> x;
add(l[1],x); // 1的左边（即l[1]）是最右侧的位置
}else if (op[0] == 'D') {
cin >> k;
remove(k+1); // 第k个插入的数的序号为k+1
} else if(op[0] == 'IL'){
cin >> k >> x;
add(l[k+1],x); // 第k个插入的数左侧为l[k+1]
}else {
cin >> k >> x;
add(k+1, x);
}
}
for (int i = r[0]; i != -1; i = r[i]) {
cout << e[i] << ' ';
}
cout << endl;
return 0;
}
三、模拟栈
1.思想&&模板
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{
}
2.题目
（1）AcWing 828.模拟栈
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int top;
int st[N];
int main() {
int m;
cin >> m;
top = 0; // 初始化,指向栈顶
while (m--) {
int x;
string op;
cin >> op;
if (op[0] == 'push') {
cin >> x;
st[++top] = x;
} else if (op[0] == 'pop') {
top--;
} else if (op[0] == 'empty') {
if (top > 0)
cout << "YES" << endl;
else
cout << "NO" << endl;
} else {
cout << st[top];
}
}
return 0;
}
四、模拟队列
1. 思想&&模板
- 普通队列
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{
}
- 循环队列
// 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)
{
}
2.题目（AcWing 829.模拟队列）
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int queue[N],hh,tt=-1;
int main()
{
int n;
cin>>n;
while(n--)
{
string op;
cin>>op;
if(op=="push")
{
int x;
cin>>x;
queue[++tt]=x;
}
else if(op=="pop")
{
hh++;
}
else if(op=="query")
{
cout<<queue[hh]<<endl;
}
else
{
if(hh<=tt) puts("No");
else puts("Yes");
}
}
return 0;
}
五、单调栈
单调栈（Monotonic Stack）是一种数据结构，常用于解决一些特定的范围问题，特别是涉及到序列中元素的“单调性”问题（如求解 “下一个更大元素”、“下一个更小元素” 等问题）。
它的 核心思想是保持栈中元素的顺序，栈内的元素要么是递增的，要么是递减的，从而方便快速地求解某些类型的问题。
单调栈的特点：
1.栈内元素是单调的，可以是递增的或者递减的，这样便于快速找到某个元素的前一个或后一个满足条件的元素。
2.动态维护栈的状态，每次处理一个新元素时，栈中的元素可以根据新元素来调整，保持栈的单调性。
3.可以在 O(n) 的时间复杂度内解决一些问题，其中 n 是数组或序列的长度。
单调栈的实现原理：
递增单调栈：栈内元素从栈底到栈顶是递增的，可以用于解决“下一个更小元素”问题。
递减单调栈：栈内元素从栈底到栈顶是递减的，可以用于解决“下一个更大元素”问题。
1. 思想&&模板
比如：对于寻找前一个更小元素的情况。
常规操作两层for循环可实现
for(int i=0;i<n;i++){
for(int j=i;j>=0;j--){
if(a[j]<a[i])
cout << a[j];
break;
}
}
分析可知，对于每一个a[i]，只有a[j]<a[i]且j<i，a[j]才有可能成为输出值。
反之，由于寻找的是前一个最小值，j<i不可更改，而若 a[j]>=a[i] 时，则必不符合要求。此时可将a[j]弹出。
故流程如下：
① 求前一个更小→从左到右遍历构造递增栈；求前一个更大→从左到右遍历构造递减栈
求后一个更小→从右往左遍历构造递增栈；求后一个更大→从右往左遍历构造递减栈；
② 具体来说，对于每一个输入值，通过while循环构造栈。即：如果栈顶元素大于等于 / 小于等于 当前输入元素，则栈顶元素不符合条件，需要弹出。
③ 输出。栈顶元素即为该输入所求的更小or更大值，栈为空则说明不存在满足要求的值。
③ 最后，将该输入本身加入栈中。
常见模型：① 找出每个数左边离它最近的比它大/小的数
int tt = 0;
// for (int i=n;i>0;i--) ② 当求右边离它最近的更大 / 更小值时
for (int i = 1; i <= n; i ++ ) // 1.遍历
{
// tt 确保栈非空。或!stk.empty()
while (tt && check(stk[tt], i)) tt -- ; // 2.构造并弹出
if(tt) // 3.输出
printf("%d ",stk[tt]);
else
printf("-1 ");
stk[ ++ tt] = i; // 4.入栈
}
2.题目（AcWing 830.单调栈）O(n)
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int top=0;
int st[N];
int main() {
int n;
scanf("%d",&n);
while(n--){
int x;
scanf("%d",&x); // scanf 输入比cin快
while(top && st[top] >= x) //如果前一个元素大于等于后一个元素，不可能成为所以数值
top--; //while(top) 确保栈不为空
if(top)
printf("%d ",st[top]);
else
printf("-1 ");
st[++top] = x;
}
return 0;
}
六、单调队列
单调队列是一个具有特殊性质的队列，通常用于优化一些涉及“滑动窗口”或者“区间最大值、最小值”等问题。
单调队列的特点：队列中的元素按某种顺序（递增或递减）排列。这种队列的常见用途是用来维护一组数据的滑动窗口中最值，或者快速找出某个窗口内的最小值或最大值。
单调队列的两种类型：
- 递增单调队列：队列中的元素从前到后是递增的。常用于求解滑动窗口中的最小值。
- 递减单调队列：队列中的元素从前到后是递减的。常用于求解滑动窗口中的最大值。
单调队列的操作：
入队：在入队时，为了保持队列的单调性，我们可能会移除一些元素。
出队：出队时，队头元素始终是当前窗口的最值（最小或最大）
1.思想&&模板
① 使用一个递减单调队列来维护当前窗口内的元素，队头即为当前窗口的最大值。
② 移动窗口时，队头元素如果超出窗口范围，则队头出队。窗口范围是 [i - k + 1, i]
③ 对于每个新元素，检查队列是否满足单调性。如果不满足，弹出队尾元素，直到满足为止。
④ 加入队列。
⑤ 输出最值。
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1; // 初始化
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 2.判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ; //3.
q[ ++ tt] = i; // 4.
}
2.题目（AcWing 154.滑动窗口）
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int top;
int q[N], a[N]; // a存储数组,q中存储a数组的下标
int main() {
int n, k;
scanf("%d&d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
// 最小值
int front = 0, tail = -1; // 初始化
for (int i = 0; i < n; i++) {
//2.判断窗口出界，弹队头
if (front < tail && q[front] < i - k + 1) //数组下标 小于 窗口左边界
front++;
//3.判断是否满足单调性，弹队尾
while (front <= tail && a[q[tail]] >= a[i])
tail--;
q[++tail] = i; // 4.条件均符合，将当前元素下标 加入队列
// if((i-k+1)>=0)
if (i >= k - 1) //确保只在完整的滑动窗口形成后才输出当前窗口的最小值
printf("%d", a[q[front]]); // 5.输出队头，即最小值
}
puts("");
// 最大值
for (int i = 0; i < n; i++) {
//2.判断窗口出界，弹队头
if (front < tail && q[front] < i - k + 1) //数组下标 小于 窗口左边界
front++;
//3.判断是否满足单调性，弹队尾
while (front <= tail && a[q[tail]] <= a[i])
tail--;
q[++tail] = i; // 条件均符合，将当前元素下标 加入队列
if (i >= k - 1)
printf("%d", a[q[front]]); // 输出队头，即最小值
}
puts("");
return 0;
}
七、KMP
1.思想&&模板
- 构造next数组 (当匹配不上时，需向右滑动的位数)
- 对模式串进行预处理，构造一个 next 数组，next[i] 表示模式串 pattern[0…i-1] 的最长相等前后缀长度（即前缀和后缀的最大重叠部分的长度）。
- 通过构造 next 数组，可以在匹配失败时，将模式串向右滑动 next[i] 位，从而避免重新比较已经匹配的部分。
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：（只需要模式串）
// for(int i=1,j=-1;i<m;i++) // 当文本s下标从0开始，next[0]=-1,所以从i=1开始遍历
for (int i = 2, j = 0; i <= m; i ++ ) // 当文本s下标从1开始，next[1]=0,所以从i=2开始遍历
{
// 如果没有回到起点 && 第i 个位置和第 j + 1 个位置不匹配
while (j && p[i] != p[j + 1])
j = ne[j]; // 失败时，根据next数组 回溯
if (p[i] == p[j + 1]) j ++ ; // 继续向右匹配
ne[i] = j; // ！更新next数组
}
- 匹配过程：
- 使用两个指针，一个指向主串（文本串）text，一个指向模式串（模式串）pattern。
- 如果当前字符匹配，则同时向右移动两个指针。
- 如果遇到不匹配的情况，根据 next 数组的信息跳过一些字符，使得模式串能够根据前缀的匹配情况继续匹配，而不需要重新比较已知匹配的部分。
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m) // 完全匹配
{
j = ne[j];
// 匹配成功后的逻辑
}
}
2.题目（AcWing 831.KMP字符串匹配）
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int s[N], p[N];
int ne[N];
int main() {
int n, m;
//将输入的值存储到 p[1]（即数组的第二个位置），也就是跳过 p[0]
cin >> n >> p[1] >> m >> s[1];
// next数组
for (int i = 2, j = 0; i <= n; i++) { // j比i小1
while (j && p[i] != p[j + 1])
j = ne[j];
if (p[i] == p[j + 1])
j++;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= m; i++) {
while (j && s[i] != p[j + 1])
j = ne[j];
if (s[i] == p[j + 1])
j++;
if (j == n) {
printf("%d ", i - n); // 输出所有出现位置的起始下标
j = ne[j];
}
}
return 0;
}
八、总结
- 单链表，增删初始化。
- 双链表
无head，默认左端为0，右端为1。最左侧为r[0],最右侧为l[1]，调用时注意。
由于0和1已有含义，那么第一个插入的结点的序号为2，第k个插入的结点序号为k+1。 - 单调栈求前一个or后一个更大值/更小值。
- 单调队列求区间内最值。
- kmp注意for循环。
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效) - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。
QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。... - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权