算法基础_数据结构【单链表 + 双链表 + 栈 + 队列 + 单调栈 + 单调队列】

---------------单链表---------------

往期《算法基础》回顾：
算法基础_基础算法【快速排序 + 归并排序 + 二分查找】
算法基础_基础算法【高精度 + 前缀和 + 差分 + 双指针】
算法基础_基础算法【位运算 + 离散化 + 区间合并】

往期《算法精讲》回顾：
算法精讲【整数二分】（实战教学）

826.单链表

题目介绍

方法一：

#include <iostream>
using namespace std;

const int N = 100010;
// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
	head = -1;
	idx = 0;
}

// 将x插到头结点
void add_to_head(int x)
{
	e[idx] = x;

	ne[idx] = head;
	head = idx;

	idx++;
}

// 将x插到下标是k的点后面
void add(int k, int x)
{
	e[idx] = x;

	ne[idx] = ne[k];
	ne[k] = idx;

	idx++;
}

// 将下标是k的点后面的点删掉
void remove(int k)
{
	ne[k] = ne[ne[k]];
}

int main()
{
	int m;
	cin >> m;

	init();

	while (m--)
	{
		int k, x;
		char op;

		cin >> op;

		if (op == 'H')
		{
			cin >> x;
			add_to_head(x);
		}
		else if (op == 'D')
		{
			cin >> k;
			if (!k) head = ne[head];//k=0时，表示删除头节点
			remove(k - 1);
		}
		else
		{
			cin >> k >> x;
			add(k - 1, x);
		}
	}

	for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
	return 0;
}

代码片段解释

片段一：

if (!k) head = ne[head];//k=0时，表示删除头节点

在这段代码中，if (!k) head = ne[head]; 的作用是：处理删除头节点的特殊情况

---

链表的表示：

• 链表通过数组模拟实现：
  • head：表示头节点的下标，初始值为 -1
  • e[N]：存储节点的值
  • ne[N]：存储节点的 next 指针
  • idx：表示当前可用的节点下标

疑问：为什么需要单独处理 k = 0 的情况？

• 头节点没有前驱节点：
  • 普通节点的删除是通过修改前驱节点的 next 指针实现的。
  • 头节点没有前驱节点，因此无法通过 remove(k) 直接删除，需要单独处理 k = 0 的情况。
• 直接更新 head：
  • 通过 head = ne[head];，直接将 head 指向下一个节点，实现头节点的删除。

解题思路给分析

这里要区分几种操作：

//头插当中的核心两步
ne[idx] = head;  //idx对应的节点连接上head对应的节点
head = idx; //head指向idx节点

//任意插当中的核心两步
ne[idx] = ne[k]; //idx对应的节点连接上k对应的节点的下一个节点
ne[k] = idx;

第一条：ne数组写在等号前面的情况：在图像上的表示就是从索引代指的节点出发的一条线

第二条：ne数组写在等号后面的情况：在图像上的表示就是索引代指的节点的下一个节点的指针

第三条：等号前面不是ne数组的情况：在图像上的表示就是该值的节点的指针

第四条：等号后面不是ne数组的情况：在图像上的表示就是该值的节点的指针

---

如果你理解上面的四条定则之后：可以尝试分析一下下面的代码

void add_to_head_before(int x)
{
    e[idx] = x;      // 将值 x 存储到新节点
    
    ne[idx] = head;  // 新节点的 next 指向当前的头节点
    head = idx;      // 更新头节点为新节点
    
    idx++;           // 移动到下一个可用位置
}

void add_to_head_after(int x)
{
    e[idx] = x;          // 将值 x 存储到新节点
    
    ne[idx] = ne[head];  // 新节点的 next 指向头节点的下一个节点
    ne[head] = idx;      // 头节点的 next 指向新节点
    
    idx++;               // 移动到下一个可用位置
}

---------------双链表---------------

827.双链表

题目讲解

方法一：

#include <iostream>
using namespace std;

const int N = 100010;
int m;
int e[N], l[N], r[N], idx;

// 在节点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];
}

int main()
{
	cin >> m;

	// 0是左端点，1是右端点
	r[0] = 1, l[1] = 0;
	idx = 2;

	while (m--)
	{
		string op;
		cin >> op;
		int k, x;
		if (op == "L")
		{
			cin >> x;
			insert(0, x);
		}
		else if (op == "R")
		{
			cin >> x;
			insert(l[1], x);
		}
		else if (op == "D")
		{
			cin >> k;
			remove(k + 1);
		}
		else if (op == "IL")
		{
			cin >> k >> x;
			insert(l[k + 1], x);
		}
		else
		{
			cin >> k >> x;
			insert(k + 1, x);
		}
	}

	for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';

	return 0;
}

代码片段解释

片段一：

// 0是左端点，1是右端点
r[0] = 1, l[1] = 0;

在这段代码中，l[N] 和 r[N] 是用于实现双向链表的数组。l[N] 存储每个节点的左指针（前驱节点），r[N] 存储每个节点的右指针（后继节点）

---

双向链表的表示

• e[N]：存储每个节点的值
• l[N]：存储每个节点的左指针（前驱节点）
• r[N]：存储每个节点的右指针（后继节点）
• idx：表示当前可用的节点下标

---

r[0] = 1, l[1] = 0; 的作用

• 初始化链表的边界：

  • 0 和 1 是两个虚拟节点，分别表示链表的左边界和右边界。
  • 0 是左边界节点，1 是右边界节点。
  • 它们不存储实际的值，仅用于简化链表的操作。

• 赋值逻辑：

  • r[0] = 1：表示左边界节点的右指针指向右边界节点。
  • l[1] = 0：表示右边界节点的左指针指向左边界节点。
  • 这样，初始链表的结构是：0 <-> 1

• 为什么需要虚拟边界节点：

  • 虚拟边界节点可以避免在插入和删除操作时处理边界条件。
    • 例如：插入到链表头部或尾部时，不需要特殊处理。

片段二：

else if (op == "R")
{
	cin >> x;
	insert(l[1], x);
}

else if (op == "IL")
{
	cin >> k >> x;
	insert(l[k + 1], x);
}		

疑问：为什么上面的代码中insert函数的位置参数为什么都需要 l[]

insert(l[1], x);：原因是因为双链表的左右端点和单链表的头节点的性质是一样的。

它们只是为了方便我们操作单/双链表而被设计出来，辅助实现插入删除操作。

所以：这里要插入的节点的位置是右端点左侧节点的右侧

insert(l[k + 1], x);：原因是我们的插入函数是在第K个节点的右侧插入一个节点，所以想在第K节点左侧插入一个节点就要传入第K个节点左侧的节点。

片段三：

for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';

这行代码的作用是：遍历双向链表并输出链表中的所有元素

---

双向链表的表示：

• r[N]：存储每个节点的右指针（后继节点）
• e[N]：存储每个节点的值
• 虚拟边界节点：
  • 0 是左边界节点，1 是右边界节点。
  • 它们不存储实际的值，仅用于简化链表的操作。

---

代码的逻辑：

1. r[0]

• r[0] 是左边界节点 0 的右指针，指向链表的第一个实际节点。
  • 如果链表为 0 <-> 3 <-> 2 <-> 1，则 r[0] = 3（指向第一个实际节点 3）

2. i != 1

• 1 是右边界节点，表示链表的结束。
• 当 i = 1 时，表示已经遍历到链表的末尾。

3. i = r[i]

• r[i] 是节点 i 的右指针，指向下一个节点。
• 通过 i = r[i]，可以移动到链表的下一个节点。

4. cout << e[i] << ' ';

• 输出节点 i 的值 e[i]

解题思路分析

输入：

5
L 10
R 20
IL 1 15
IR 1 18
D 1

初始化

• 链表结构：
  • 0 <-> 1（0 是左边界节点，1 是右边界节点）
• idx：
  • 初始值为 2（因为 0 和 1 已经被占用）

---

1. 操作 L 10

• 作用：在链表头部插入 10
• 执行：
  • 调用 insert(0, 10)
  • 在节点 0 的右边插入 10
  • 新节点的下标为 2
  • 更新链表：0 <-> 10 <-> 1
• 链表状态：
  • e = [0, 0, 10]
  • l = [0, 0, 0]
  • r = [2, 1, 1]
  • idx = 3

2. 操作 R 20

• 作用：在链表尾部插入 20
• 执行：
  • 调用 insert(l[1], 20)
  • l[1] = 2（右边界节点的前驱节点是节点 2）
  • 在节点 2 的右边插入 20
  • 新节点的下标为 3
  • 更新链表：0 <-> 10 <-> 20 <-> 1
• 链表状态：
  • e = [0, 0, 10, 20]
  • l = [0, 0, 0, 2]
  • r = [2, 1, 3, 1]
  • idx = 4

3. 操作 IL 1 15

• 作用：在第 1 个插入的节点的左边插入 15
• 执行：
  • 第 1 个插入的节点是节点 2（值为 10）
  • 调用 insert(l[2], 15)
  • l[2] = 0（节点 2 的前驱节点是左边界节点 0）
  • 在节点 0 的右边插入 15
  • 新节点的下标为 4
  • 更新链表：0 <-> 15 <-> 10 <-> 20 <-> 1
• 链表状态：
  • e = [0, 0, 10, 20, 15]
  • l = [0, 0, 4, 2, 0]
  • r = [4, 1, 3, 1, 2]
  • idx = 5

4. 操作 IR 1 18

• 作用：在第 1 个插入的节点的右边插入 18
• 执行：
  • 第 1 个插入的节点是节点 2（值为 10）
  • 调用 insert(2, 18)
  • 在节点 2 的右边插入 18
  • 新节点的下标为 5
  • 更新链表：0 <-> 15 <-> 10 <-> 18 <-> 20 <-> 1
• 链表状态：
  • e = [0, 0, 10, 20, 15, 18]
  • l = [0, 0, 4, 2, 0, 2]
  • r = [4, 1, 5, 1, 2, 3]
  • idx = 6

5. 操作 D 1

• 作用：
  • 删除第 1 个插入的节点（即节点 2，值为 10）
• 执行：
  • 调用 remove(2)
  • 删除节点 2
  • 更新链表：0 <-> 15 <-> 18 <-> 20 <-> 1
• 链表状态：
  • e = [0, 0, 10, 20, 15, 18]
  • l = [0, 0, 4, 5, 0, 4]
  • r = [4, 1, 5, 1, 5, 3]
  • idx = 6

---

最终链表

• 链表结构：0 <-> 15 <-> 18 <-> 20 <-> 1
• 有效节点：15, 18, 20

输出

15 18 20

---------------栈---------------

828.模拟栈

题目介绍

方法一：

#include <iostream>
#include <vector>
using namespace std;

int n, x;
string str;

//模拟栈 ----> 一个一维数组 + 一个int变量
const int N = 1e5 + 10;
vector<int> stk(N);
int tt = 0;

int main()
{
    cin >> n;

    while (n--)
    {
        cin >> str;
        if (str == "push")
        {
            //入栈操作
            cin >> x;
            stk[++tt] = x;
        }
        else if (str == "pop")
        {
            //出栈操作
            tt--;
        }
        else if (str == "empty")
        {
            //栈判空
            if (tt > 0) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
        else if (str == "query")
        {
            //显示栈顶元素
            cout << stk[tt] << endl;
        }
    }

    return 0;
}

解题思路分析

数组模拟栈 ----> 一个**一维数组 + 一个int变量**：vector<int> stk(N); int tt = 0;

入栈操作 ：stk[++tt] = x

出栈操作：tt--

栈判空：if (tt > 0)

显示栈顶元素：stk[tt]

3302.表达式求值

题目介绍

方法一：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;

stack<int> num;
stack<char> opt;

void eval()
{
    auto b = num.top(); num.pop(); //先出op栈的数字是后一个运算数
    auto a = num.top(); num.pop(); //后出op栈的数字是前一个运算数
    auto c = opt.top(); opt.pop();

    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;

    num.push(x);
}

int main()
{
    unordered_map<char, int> pr{ {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i++)
    {
        auto c = str[i];

        if (isdigit(c)) //提取到的字符是数字
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
            {
                x = x * 10 + str[j] - '0';
                j++;
            }               
            i = j - 1; //j现在指向的位置不是数字，该位置的字符应该重新判定应该执行那个操作了，所以i应该=j
            //但是for循环里有i++操作，所以这里让i先等于j-1
            num.push(x);
        }
        else if (c == '(') opt.push(c); //提取到的字符是(
        else if (c == ')') //提取到的字符是)
        {
            while (opt.top() != '(') eval();
            opt.pop();//将'('出栈
        }
        else//提取到的字符是:'+','-','*','/'
        {
            while (opt.size() && opt.top() != '(' && pr[opt.top()] >= pr[c])  eval();
            opt.push(c);//将新遍历到的操作符入栈
        }
    }
    while (opt.size()) eval();
    cout << num.top() << endl;
    return 0;
}

程序执行流程

代码片段解释

片段一：

if (isdigit(c))

函数的介绍：

isdigit()：用于检查一个字符是否是数字字符（即 0 到 9 之间的字符）

函数的原型：

int isdigit(int c);

• c：是待检查的字符。
  • 函数接收一个 int 类型的参数，这是因为该函数可以处理 EOF（文件结束符）
  • 在实际使用时，可直接传入 char 类型的变量，因为 char 类型会自动转换为 int 类型

函数的返回值：

• 若参数 c 是十进制数字字符（即：字符 '0' 到 '9'），函数返回一个非零值（通常为 true）
• 若参数 c 不是十进制数字字符，函数返回 0（即 false）

疑问：为什么不将str[j] - '0' 改为 str[j] + '0'？

• str[j] - '0'：是将字符转换为对应的数字值。

  • 例如：字符 '5' 的 ASCII 值是 53，字符 '0' 的 ASCII 值是 48，所以 '5' - '0' 的结果是 5

• str[j] + '0'：会将字符的 ASCII 值加上 '0' 的 ASCII 值，结果是一个完全不同的数值。

  • 例如：字符 '5' 的 ASCII 值是 53，加上 '0' 的 ASCII 值 48，结果是 101，这显然不是我们想要的数字值

片段二：

while (j < str.size() && isdigit(str[j]))
{
    x = x * 10 + str[j] - '0';
    j++;
}

这段代码的作用是提取表达式中的多位数，并将其转换为整数存储到 num 栈中

---

代码的作用：

• 提取多位数：

  • 表达式中的数字可能是多位数（例如：12、345 等），而 str[i] 只能提取单个字符。
  • 这段代码通过循环遍历连续的字符，将多个数字字符组合成一个完整的整数。

• 转换为整数：

  • 通过 x = x * 10 + str[j] - '0';，将字符形式的数字转换为整数。

---

示例：

输入：12+34

1. 遍历到字符 1：

   • isdigit('1') 为真，进入循环
   • x = 0 * 10 + 1 = 1
   • j++，j = 1

2. 遍历到字符 2：

   • isdigit('2') 为真，继续循环
   • x = 1 * 10 + 2 = 12
   • j++，j = 2

3. 遍历到字符 +：

   • isdigit('+') 为假，退出循环
   • i = j - 1 = 1
   • 将 x = 12 压入 num 栈

4. 遍历到字符 3：

   • isdigit('3') 为真，进入循环
   • x = 0 * 10 + 3 = 3
   • j++，j = 4

5. 遍历到字符 4：

   • isdigit('4') 为真，继续循环
   • x = 3 * 10 + 4 = 34
   • j++，j = 5

6. 遍历到字符串末尾：

   • j = 5，超出字符串范围，退出循环
   • i = j - 1 = 4
   • 将 x = 34 压入 num 栈

片段三：

while (op.top() != '(') eval();

疑问：c == ')'时为什么要这样写while (op.top() != ‘(’) eval();

在表达式求值的代码中，当遇到右括号 ) 时，需要计算括号内的表达式。

• 确保括号内的表达式优先计算：
  • 括号内的表达式需要优先计算，因此需要从 op 栈中弹出操作符并计算，直到遇到左括号 (
• 处理嵌套括号：
  • 如果表达式中有嵌套的括号（例如：(2+(3*4))），这段代码也能正确处理。

片段四：

while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c])  eval();

疑问：当提取到的字符是:'+','-','*','/'是为什么要这么写while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();

1. op.size()：

   • 确保 op 栈不为空

2. op.top() != '('：

   • 如果栈顶操作符不是左括号 (，可以开始进行计算
   • 如果栈顶操作符是左括号 (，表示还不能进行计算，应当先将操作符入栈
     • 因为左括号表示一个新的子表达式开始，此时专心的入栈即可，等到遇到')'时再进行计算

3. pr[op.top()] >= pr[c]：

   • 确保栈顶操作符的优先级大于或等于当前操作符的优先级

4. eval()：

   • 从 op 栈中弹出一个操作符，从 num 栈中弹出两个操作数，进行计算，并将结果压入 num 栈

解题思路分析

---------------队列---------------

829.模拟队列

题目介绍

方法一：

#include <iostream>
#include <vector>
using namespace std;

//获取数据：
int n, x;
string str;

//使用数组模拟队列 ---> 一个原生的数组 + 两个int变量
const int N = 1e5 + 10;
int arr[N];
int hh, tt = -1;

int main()
{
    cin >> n;

    //处理数据：
    //1.队尾插入一个整数x  2.队头出对一个元素  3.判断队列是否为空  4.查询队头的元素
    while (n--)
    {
        cin >> str;
        if (str == "push")
        {
            cin >> x;
            arr[++tt] = x;
        }
        else if (str == "pop")
        {
            hh++;
        }
        else if (str == "empty")
        {
            if (hh <= tt) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
        else
        {
            cout << arr[hh] << endl;
        }
    }
    return 0;
}

---------------单调栈---------------

830.单调栈

题目介绍

方法一：

#include <iostream>
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;
}

解题思路分析

单调栈的思路步骤：

第一步：输入一个整数

第二步：使用while循环判断是否需要出栈

第三步：使用if语句判断当前的栈是否为空

• 第四步：如果栈不为空输出栈顶的元素

• 第五步：如果栈为空则输出-1

第六步：将整数入栈

---------------单调队列---------------

154.滑动窗口

题目介绍

方法一：

#include <iostream>
using namespace std;

const int N = 1000010;
int arr[N], que[N];
int hh = 0, tt = -1;

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

    for (int i = 0; i < n; i++)
    {
        
        if (hh <= tt && i - k + 1 > que[hh]) hh++; // 如果队头元素已经不在当前窗口范围内，则出队
        while (hh <= tt && arr[que[tt]] >= arr[i]) tt--; // 如果队尾元素大于等于当前元素，则出队

        que[++tt] = i;//入队操作

        if (i >= k - 1) printf("%d ", arr[que[hh]]);// 当窗口大小达到 k 时，输出队头元素（当前窗口的最小值）
    }

    puts("");

    hh = 0, tt = -1;
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && i - k + 1 > que[hh]) hh++;
        while (hh <= tt && arr[que[tt]] <= arr[i]) tt--;

        que[++tt] = i;

        if (i >= k - 1) printf("%d ", arr[que[hh]]);
    }
    puts("");
    return 0;
}

代码执行过程

解题思路分析

单调队列的思路步骤：

第一步：使用for循环遍历整个数组中的元素

第二步：使用if语句判断队头元素是否已经不在当前窗口范围内，如果是则将队头元素出队

第三步：使用while语句判断队尾元素是否大于等于当前元素，如果是则将队尾元素出队

第四步：将当前的元素入队

第五步：当窗口大小达到 k 时，输出队头元素