【愚公系列】2023年11月 数据结构(四)-栈
🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，阿里云专家博主，腾讯云优秀博主，掘金优秀博主，51CTO博客专家等。 🏆《近期荣誉》：2022年CSDN博客之星TOP2，2022年华为云十佳博主等。
🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏
🚀前言
数据结构是计算机科学中的一个重要概念，它描述了数据之间的组织方式和关系，以及对这些数据的访问和操作。常见的数据结构有：数组、链表、栈、队列、哈希表、树、堆和图。
- 数组（Array）：是一种线性数据结构，它将一组具有相同类型的数据元素存储在一起，并为每个元素分配一个唯一的索引。数组的特点是具有随机访问的能力。
- 链表（Linked List）：也是一种线性数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的引用。链表的特点是可以动态地插入或删除节点，但访问某个节点时需要从头开始遍历。
- 栈（Stack）：是一种后进先出（LIFO）的数据结构，它只能在栈顶进行插入和删除操作。栈通常用于实现递归算法、表达式求值和内存管理等场景。
- 队列（Queue）：是一种先进先出（FIFO）的数据结构，它可以在队尾插入元素，在队头删除元素。队列通常用于数据的缓存、消息队列和网络通信等场景。
- 哈希表（Hash Table）：也称为散列表，它是一种根据关键字直接访问数据的数据结构。哈希表通常由数组和散列函数组成，可以在常数时间内进行插入、删除和查找操作。
- 树（Tree）：是一种非线性数据结构，它由一系列的节点组成，每个节点可以有若干个子节点。树的特点是可以动态地插入或删除节点，常见的树结构包括二叉树、平衡树和搜索树等。
- 堆（Heap）：是一种特殊的树结构，它通常用于实现优先队列和堆排序等算法。堆分为最大堆和最小堆，最大堆的每个节点的值都大于等于其子节点的值，最小堆则相反。
- 图（Graph）：是一种由节点和边组成的非线性数据结构，它可以用来表示各种实体之间的关系，如社交网络、路线图和电路图等。图的遍历和最短路径算法是常见的图算法。
🚀一、栈
🔎1.基本思想
栈是一种数据结构，它基于后进先出的原则，也被称为LIFO（Last In First Out）结构。栈可以用来表示任何具有“一端进、一端出”的数据结构。它包括两个基本操作：入栈（push）和出栈（pop）。
栈的基本思想是，数据元素按照后进先出的顺序插入和删除，插入和删除元素只能在栈顶进行。当有新元素插入时，它就成为了新的栈顶元素，当元素被删除时，栈顶元素被移除，下一个元素成为新的栈顶元素。
栈可以使用数组或链表实现。使用数组实现的栈被称为顺序栈，使用链表实现的栈被称为链式栈。在实现栈的过程中，需要注意栈空间的管理，包括栈的空间分配和释放等问题。
🔎2.栈常用操作
以下是C#中栈(Stack)常用操作及示例：
- Push：向栈中添加元素
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);- Pop: 从栈中弹出元素
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
int result = stack.Pop(); // result 的值为 2- Peek: 查看栈顶元素，不弹出
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
int result = stack.Peek(); // result 的值为 2，但栈中依然有 2- Count: 获取栈中元素个数
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
int count = stack.Count; // count 的值为 2- Clear: 清空栈中所有元素
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Clear(); // 栈中没有元素了- Contains: 判断栈中是否包含指定元素
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
bool contains = stack.Contains(2); // contains 的值为 true- CopyTo: 将栈中元素复制到数组中
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
int[] array = new int[stack.Count];
stack.CopyTo(array, 0); // array 的值为 {2, 1}- TrimExcess: 优化栈内存使用，释放不必要的空间
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.TrimExcess(); // 优化内存使用🔎3.栈的实现
🦋3.1 基于链表的实现
图解：
示例：
// === File: linkedlist_stack.cs ===
/* 基于链表实现的栈 */
class LinkedListStack {
private ListNode? stackPeek; // 将头节点作为栈顶
private int stkSize = 0; // 栈的长度
public LinkedListStack() {
stackPeek = null;
}
/* 获取栈的长度 */
public int size() {
return stkSize;
}
/* 判断栈是否为空 */
public bool isEmpty() {
return size() == 0;
}
/* 入栈 */
public void push(int num) {
ListNode node = new ListNode(num);
node.next = stackPeek;
stackPeek = node;
stkSize++;
}
/* 出栈 */
public int pop() {
if (stackPeek == null)
throw new Exception();
int num = peek();
stackPeek = stackPeek.next;
stkSize--;
return num;
}
/* 访问栈顶元素 */
public int peek() {
if (size() == 0 || stackPeek == null)
throw new Exception();
return stackPeek.val;
}
/* 将 List 转化为 Array 并返回 */
public int[] toArray() {
if (stackPeek == null)
return Array.Empty<int>();
ListNode node = stackPeek;
int[] res = new int[size()];
for (int i = res.Length - 1; i >= 0; i--) {
res[i] = node.val;
node = node.next;
}
return res;
}
}在链表实现中，链表的扩容非常灵活，不存在数组扩容时效率降低的问题。但是，入栈操作需要初始化节点对象并修改指针，因此效率相对较低。不过，如果入栈元素本身就是节点对象，那么可以省去初始化步骤，从而提高效率。
🦋3.2 基于数组的实现表
图解：
示例：
/* 基于数组实现的栈 */
class ArrayStack {
private List<int> stack;
public ArrayStack() {
// 初始化列表（动态数组）
stack = new();
}
/* 获取栈的长度 */
public int size() {
return stack.Count();
}
/* 判断栈是否为空 */
public bool isEmpty() {
return size() == 0;
}
/* 入栈 */
public void push(int num) {
stack.Add(num);
}
/* 出栈 */
public int pop() {
if (isEmpty())
throw new Exception();
var val = peek();
stack.RemoveAt(size() - 1);
return val;
}
/* 访问栈顶元素 */
public int peek() {
if (isEmpty())
throw new Exception();
return stack[size() - 1];
}
/* 将 List 转化为 Array 并返回 */
public int[] toArray() {
return stack.ToArray();
}
}数组实现额外支持随机访问，但这已超出了栈的定义范畴，因此一般不会用到。
在基于数组的实现中，入栈和出栈操作都是在预先分配好的连续内存中进行，具有很好的缓存本地性，因此效率较高。然而，如果入栈时超出数组容量，会触发扩容机制，导致该次入栈操作的时间复杂度变为 𝑂(𝑛)。
🔎4.优点和缺点
栈是一种常见的数据结构，在程序设计中广泛使用。它有以下优点和缺点：
优点：
- 方便快捷：栈的操作是简单明了的，主要包括Push和Pop两个操作，非常方便快捷。
- 逻辑清晰：栈的特性使得程序的逻辑非常清晰，因为它保证了操作的顺序和依赖关系。
- 节省空间：栈是一种线性的数据结构，不需要额外的空间开销，因此可以节省空间。
- 支持递归：栈的特性使得它可以支持递归调用，这是一种非常便利的编程方式。
缺点：
- 存储限制：栈的大小是有限制的，因为栈的大小和系统的内存大小有关。
- 难以遍历：栈只能从栈顶进行操作，而不能从中间进行访问或遍历，因此有时候难以满足复杂的操作需求。
- 容易出现溢出：由于栈的大小是有限制的，如果Push操作过多，会导致栈溢出，程序崩溃。
- 不支持随机访问：栈只支持从栈顶进行操作，因此不支持随机访问，有时候难以满足复杂的操作需求。
在使用栈时，应该根据实际需求来选择，权衡其优缺点，选择最适合的数据结构。
🔎5.应用场景
栈是一种数据结构，其特点是先进后出，后进先出。栈在计算机科学中有很多应用场景，其中一些包括：
1.函数调用：在编程中，每次调用函数时，系统都会将函数（及其参数和局部变量）压入栈中。当函数返回时，系统将函数从栈中弹出。
2.表达式求值：在编译器中对表达式求值时，使用栈来实现运算符优先级的处理。
3.括号匹配：在编译器中，使用栈来检测括号是否匹配，以确保代码的正确性。
4.迭代算法：在深度优先搜索（DFS）等算法中，可以使用栈来实现迭代。
5.逆序输出：可以使用栈来逆序输出数据。
6.撤销操作：许多应用程序（如文本编辑器）可以通过使用栈来支持撤销操作。
栈是一种非常有用的数据结构，在计算机科学中有很多实际应用。
腾讯云开发者
