栈算法篇——LIFO后进先出，数据与思想的层叠乐章（上）

文章目录

前言
第一章：栈的基础知识回顾
1.1 栈的结构与实现
1.2 栈的应用
第二章：删除字符串中的所有相邻重复项
- 2.1 题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
- 2.2 题目分析：
- 2.3 思路讲解：
- 2.4 代码实现：
小结：栈的文学隐喻

前言

在计算的世界中，栈（Stack）是一种古老而又充满诗意的数据结构。它简洁、优雅，却也蕴藏着强大的力量。像一座孤独的山峰，它承载着来者的重量，却又让旅人只能按顺序前行，无法随意翻越。

栈的本质在于它的“后进先出”（LIFO, Last In First Out）原则。正如生活中许多事物，最新的往往是最先面对的，而那些久远的记忆则埋藏在更深的地方，需要层层剥开才能触及。栈便是如此，最新压入的元素总是最先被取出，而最早的那些则沉寂在底部，等待轮回的时机。

第一章：栈的基础知识回顾

1.1 栈的结构与实现

一个栈可以用数组或链表来实现，其操作如同一场无声的舞蹈。

以下是一个基于 C++ 的栈实现：

#include <iostream>
#include <vector>
#include <stdexcept>class Stack {
private:std::vector<int> stack;public:void push(int item) {stack.push_back(item);}int pop() {if (stack.empty()) {throw std::out_of_range("pop from empty stack");}int top = stack.back();stack.pop_back();return top;}int peek() const {if (stack.empty()) {throw std::out_of_range("peek from empty stack");}return stack.back();}bool isEmpty() const {return stack.empty();}
};int main() {Stack stack;stack.push(10);stack.push(20);stack.push(30);std::cout << "栈顶元素: " << stack.peek() << std::endl;std::cout << "弹出元素: " << stack.pop() << std::endl;std::cout << "栈是否为空: " << (stack.isEmpty() ? "是" : "否") << std::endl;return 0;
}

以下是基于 C 语言的栈实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;
} Stack;void init(Stack *stack) {stack->top = -1;
}bool is_empty(Stack *stack) {return stack->top == -1;
}bool is_full(Stack *stack) {return stack->top == MAX_SIZE - 1;
}void push(Stack *stack, int item) {if (is_full(stack)) {printf("栈已满，无法压栈\n");return;}stack->data[++stack->top] = item;
}int pop(Stack *stack) {if (is_empty(stack)) {printf("栈为空，无法弹栈\n");exit(EXIT_FAILURE);}return stack->data[stack->top--];
}int peek(Stack *stack) {if (is_empty(stack)) {printf("栈为空，无法查看栈顶\n");exit(EXIT_FAILURE);}return stack->data[stack->top];
}int main() {Stack stack;init(&stack);push(&stack, 10);push(&stack, 20);push(&stack, 30);printf("栈顶元素: %d\n", peek(&stack));printf("弹出元素: %d\n", pop(&stack));printf("栈是否为空: %s\n", is_empty(&stack) ? "是" : "否");return 0;
}

1.2 栈的应用

栈虽简单，却在计算机科学的广袤领域中扮演着不可或缺的角色。它如同一个忠诚的卫士，默默守护着程序的秩序。

1. 函数调用

当程序执行函数时，每一次调用都会将当前的上下文存入栈中，犹如一位旅人记录下旅途的足迹，以便归来时能够继续前行。当函数结束，记录被弹出，程序回到最初的位置。这是递归的灵魂所在，也是程序能够顺利运行的关键。

2. 表达式求值

在数学的殿堂中，栈是解析表达式的隐秘助手。无论是中缀表达式到后缀表达式的转换，还是后缀表达式的计算，栈总是穿针引线，确保每一步都井然有序。

3. 括号匹配

在编程语言的语法规则中，括号的配对如同舞蹈中的步伐，必须精准无误。栈便是这场舞蹈的裁判，记录着每一次开场与闭合，确保它们相遇时不失优雅。

以下是 C++ 实现的括号匹配示例：

#include <iostream>
#include <stack>
#include <string>bool isValidParentheses(const std::string &s) {std::stack<char> stack;for (char c : s) {if (c == '(' || c == '{' || c == '[') {stack.push(c);} else {if (stack.empty()) return false;char top = stack.top();stack.pop();if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {return false;}}}return stack.empty();
}int main() {std::string expression = "{[()]}";std::cout << "括号匹配结果: " << (isValidParentheses(expression) ? "匹配" : "不匹配") << std::endl;return 0;
}

下面我们将结合具体题目加以分析：

第二章：删除字符串中的所有相邻重复项

2.1 题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/

2.2 题目分析：

给出由小写字母组成的字符串 s，删除两个相邻且相同的字母，并删除它们。
在 s 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

2.3 思路讲解：

本题极像我们玩过的「开⼼消消乐」游戏，仔细观察消除过程，可以发现本题与我们之前做过的「括
号匹配」问题是类似的。当前元素是否被消除，需要知道上⼀个元素的信息，因此可以⽤「栈」来保
存信息。
但是，如果使⽤ stack 来保存的话，最后还需要把结果从栈中取出来。不如直接⽤「数组模拟⼀个
栈」结构：在数组的尾部「尾插尾删」，实现栈的「进栈」和「出栈」。那么最后数组存留的内容，
就是最后的结果。

2.4 代码实现：

class Solution {
public:string removeDuplicates(string s) {string ret;for(auto ch:s){if(ret.size()&&ret.back()==ch){ret.pop_back();}//删除操作else{ret+=ch;}}return ret;}
};

小结：栈的文学隐喻

如果把栈看作人生的隐喻，它提醒我们：最新的挑战总是最先面对，而那些曾经的经历，虽被压在时间的深处，却从未被遗忘。当我们解决了眼前的问题，回首往事时，才会发现每一步都意义深远。

栈也象征着一种简约之美。它拒绝过多的选择，只专注于当前的顶端。这种专注如同禅意，告诫我们放下多余的执念，专注于眼前的事物。

本篇关于栈算法的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！
在这里插入图片描述