C语言-数据结构-stack讲解

本篇文章讲解了数据结构与算法中非常重要的一部分——stack （1）首先讲解stack的概述与定义； （2）然后分析stack的理论与结构； （3）讲解stack的具体实现步骤； （4）最后通过例题的形式深入了解stack如何使用；例题选自力扣上的经典OJ题——有效的括号。 ### C语言-数据结构-stack讲解 #### 一、Stack概述与定义 栈（Stack）是一种特殊的线性表，它的特点是只允许在一端进行插入和删除操作。这一端被称为栈顶（Top），而另一端则被称为栈底（Bottom）。栈遵循“后进先出”（LIFO, Last In First Out）原则，这意味着最后一个被添加到栈中的元素将是第一个被移除的元素。 - **压栈（Push）**：栈的插入操作，新元素总是被添加到栈顶。 - **出栈（Pop）**：栈的删除操作，总是从栈顶移除元素。 - **查看栈顶元素（Peek/Top）**：返回栈顶元素而不删除它。 - **判空（IsEmpty）**：判断栈是否为空。 - **判满（IsFull）**：判断栈是否已满（仅适用于固定大小的栈）。 栈可以比喻为一个箱子，当我们向箱子里放置小盒子时，相当于执行压栈操作；从箱子中取出小盒子则对应于出栈操作。取出的小盒子总是最近放入的那个，即“后入先出”。 #### 二、Stack理论与结构 栈本质上是一种操作受限的线性表，它只允许在一端进行操作。可以将栈想象成一堆盘子，每次只能在顶部添加或移除盘子。栈的操作特点如下： - **数据结构**：栈可以由数组或链表实现。数组实现较为常见，因为它简单且访问速度快。链表实现虽然稍微复杂一些，但它能够动态扩展栈的大小。 - **存储**：使用数组时，栈的大小通常是固定的。而在链表实现中，可以通过分配新的节点来动态扩展栈的大小。 #### 三、Stack的具体实现步骤 下面我们将详细介绍如何在C语言中实现栈的数据结构。 ##### 1. 定义栈类型 ```c typedef int STDataType; typedef struct Stack { STDataType* a; // 指向数组的指针 int top; // 栈顶位置 int capacity; // 栈的最大容量 } ST; ``` `typedef`用于定义新的类型名，这样可以使代码更加清晰易读。 ##### 2. 初始化栈 初始化栈时，可以选择静态分配固定大小的数组，也可以动态分配内存。这里我们选择动态分配内存的方式，以实现栈的灵活扩展。 ```c void StackInit(ST* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); // 初始容量设为4 if (ps->a == NULL) { printf("malloc fail\n"); exit(-1); } ps->capacity = 4; ps->top = 0; } ``` ##### 3. 入栈操作 ```c void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { STDataType* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; ps->top++; } ``` 入栈操作需要检查栈是否已满，并根据需要扩展栈的空间。 ##### 4. 出栈操作 ```c STDataType StackPop(ST* ps) { assert(ps); if (ps->top == 0) { printf("Stack is empty.\n"); exit(-1); // 栈为空时尝试出栈 } ps->top--; return ps->a[ps->top]; } ``` 出栈前要确保栈不是空的。 #### 四、Stack应用实例：有效的括号 本节通过解决经典的“有效的括号”问题来加深对栈的理解。 **问题描述**：给定一个只包含字符 `(`, `)`, `{`, `}`, `[`, `]` 的字符串，判断该字符串是否为有效的括号序列。 **解题思路**： 1. 遍历字符串中的每个字符。 2. 如果遇到左括号，则将其压入栈中。 3. 如果遇到右括号，则弹出栈顶元素，并检查是否与当前右括号匹配。 4. 如果栈为空，但仍有右括号未匹配，则返回false。 5. 遍历结束后，如果栈为空，则返回true；否则返回false。 **代码实现**： ```c bool isValid(char* s) { ST st; StackInit(&st); while (*s) { switch (*s) { case '(': case '[': case '{': StackPush(&st, *s); break; case ')': if (StackEmpty(&st) || StackPop(&st) != '(') return false; break; case ']': if (StackEmpty(&st) || StackPop(&st) != '[') return false; break; case '}': if (StackEmpty(&st) || StackPop(&st) != '{') return false; break; default: return false; } s++; } return StackEmpty(&st); } ``` 这段代码实现了“有效的括号”问题的解决方案，充分展示了栈在解决实际问题中的应用。通过本篇文章的学习，你应该能够更好地理解和应用栈这一重要的数据结构。