数据结构：栈（Stack）及其实现

栈（Stack）是计算机科学中常用的一种数据结构，它遵循先进后出（Last In, First Out，LIFO）的原则。也就是说，栈中的元素只能从栈顶进行访问，最后放入栈中的元素最先被取出。栈在很多应用中非常重要，例如函数调用、表达式求值、深度优先搜索等。

本文将介绍栈的基本概念、实现逻辑，并通过C语言代码演示栈的常见操作。

---

1. 栈的基本概念

栈是一种线性数据结构，其主要操作包括：

压栈（Push）：将一个元素压入栈顶。弹栈（Pop）：从栈顶移除一个元素。栈顶元素（Top/Peek）：获取栈顶的元素，但不移除它。栈空（IsEmpty）：检查栈是否为空。栈满（IsFull）：检查栈是否已满（对于固定大小的栈）。

栈的特点是只能从栈顶进行操作，所有元素的插入和删除都发生在栈顶。

---

2. 栈的实现逻辑

栈的实现可以基于数组或链表。这里我们采用数组实现栈，并且实现栈的常见操作。

栈的初始化：栈需要一个数组来存储元素，并且需要一个指针top来指示栈顶的位置。压栈操作（Push）：将元素放入栈顶，top指针向上移动。弹栈操作（Pop）：移除栈顶元素，top指针向下移动。查看栈顶元素（Top/Peek）：返回top指针位置的元素。检查栈空（IsEmpty）：判断top是否为-1，栈为空时top = -1。检查栈满（IsFull）：判断top是否等于栈的最大容量减1。

3. C语言实现栈

#include <stdio.h> #include <stdlib.h> #define MAX 5 // 栈的最大容量 // 栈结构体 typedef struct { int arr[MAX]; // 存储栈元素的数组 int top; // 栈顶指针 } Stack; // 栈初始化函数 void initStack(Stack* stack) { stack->top = -1; // 初始时栈为空，栈顶指针为-1 } // 判断栈是否为空 int isEmpty(Stack* stack) { return stack->top == -1; // 如果栈顶指针为-1，说明栈为空 } // 判断栈是否为满 int isFull(Stack* stack) { return stack->top == MAX - 1; // 如果栈顶指针为MAX-1，说明栈已满 } // 压栈操作 void push(Stack* stack, int value) { if (isFull(stack)) { printf("栈满，无法压栈！\n"); return; } stack->arr[++(stack->top)] = value; // 将元素放入栈顶，并更新栈顶指针 printf("元素 %d 压栈成功！\n", value); } // 弹栈操作 int pop(Stack* stack) { if (isEmpty(stack)) { printf("栈空，无法弹栈！\n"); return -1; } return stack->arr[(stack->top)--]; // 返回栈顶元素，并更新栈顶指针 } // 获取栈顶元素 int peek(Stack* stack) { if (isEmpty(stack)) { printf("栈空，无法获取栈顶元素！\n"); return -1; } return stack->arr[stack->top]; // 返回栈顶元素 } // 打印栈的所有元素 void printStack(Stack* stack) { if (isEmpty(stack)) { printf("栈空，无法打印栈元素！\n"); return; } printf("栈内元素："); for (int i = 0; i <= stack->top; i++) { printf("%d ", stack->arr[i]); } printf("\n"); } int main() { Stack stack; initStack(&stack); // 初始化栈 // 压栈操作 push(&stack, 10); push(&stack, 20); push(&stack, 30); push(&stack, 40); push(&stack, 50); // 打印栈元素 printStack(&stack); // 再压栈时，栈满的情况 push(&stack, 60); // 弹栈操作 printf("弹栈元素: %d\n", pop(&stack)); printf("弹栈元素: %d\n", pop(&stack)); // 打印栈元素 printStack(&stack); // 查看栈顶元素 printf("栈顶元素: %d\n", peek(&stack)); return 0; } 4. 代码注释说明

栈的结构体：Stack结构体包含了一个大小为MAX的数组arr来存储栈元素，以及一个top变量来记录栈顶的位置。top的初始值为-1，表示栈为空。

initStack函数：初始化栈，将top设为-1，表示栈为空。

isEmpty函数：判断栈是否为空。如果top为-1，返回1表示栈空；否则返回0。

isFull函数：判断栈是否为满。如果top等于MAX-1，说明栈已满，返回1表示栈满；否则返回0。

push函数：将元素压入栈顶，首先检查栈是否已满，如果未满，top指针加1，然后将元素放入栈顶。

pop函数：从栈顶移除元素，首先检查栈是否为空，如果栈不为空，返回栈顶元素并将top指针减1。

peek函数：查看栈顶元素，但不移除它。首先检查栈是否为空，如果不为空，返回栈顶元素。

printStack函数：打印栈中所有的元素。首先检查栈是否为空，如果栈不为空，则依次打印从栈底到栈顶的所有元素。

5. 运行示例

假设我们运行上述程序，输出结果如下：

元素 10 压栈成功！ 元素 20 压栈成功！ 元素 30 压栈成功！ 元素 40 压栈成功！ 元素 50 压栈成功！ 栈内元素：10 20 30 40 50 栈满，无法压栈！ 弹栈元素: 50 弹栈元素: 40 栈内元素：10 20 30 栈顶元素: 30 初始时，栈为空，通过压栈操作逐步将元素10, 20, 30, 40, 50压入栈中。然后尝试压栈一个新的元素60，由于栈已满，无法压栈。接着，弹出栈顶元素50和40，并打印当前栈中的元素。最后，查看栈顶元素30。 6.栈在实际应用中的一些常见使用场景 6.1. 函数调用和递归

栈最常见的应用之一是函数调用，它在计算机的程序执行过程中被广泛使用。

实现过程：

当程序调用一个函数时，程序会将当前函数的执行状态（如局部变量、返回地址等）保存在栈中，这个过程叫做“入栈”。

当一个函数调用另一个函数时，栈会继续“压入”当前函数的状态。当一个函数执行完毕，栈会“弹出”当前函数的状态，并恢复到上一个函数的执行状态。

这种机制是通过栈来实现的，也就是函数调用栈。当递归调用发生时，每次递归调用都将当前的执行环境推入栈中，直到递归结束并返回时，栈中的元素逐步弹出，恢复到原来的状态。

示例：

递归计算斐波那契数列时，栈用于存储每次递归调用的状态。

int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); }

每次fibonacci函数调用时，程序都会把当前调用的返回地址和局部变量压入栈中。栈的大小随着递归深度的增加而增加，直到递归返回时，栈逐一弹出，恢复状态。

6.2. 表达式求值

栈是计算机中表达式求值的常用工具，特别是在处理后缀表达式（逆波兰表示法）和前缀表达式时。

后缀表达式（逆波兰表示法）：

例如，给定一个表达式3 4 + 5 *，可以通过栈来实现求值。

遇到操作数（如3、4），将其压入栈。遇到操作符（如+、*），弹出栈顶的两个操作数，进行计算，然后将结果重新压入栈。最终栈中剩下的就是结果。

示例：

例如计算表达式3 4 + 5 *：

第一步：遇到3和4，压栈，栈为[3, 4]。第二步：遇到+，弹出栈顶的两个数4和3，计算3 + 4 = 7，将结果压入栈，栈为[7]。第三步：遇到5，压栈，栈为[7, 5]。第四步：遇到*，弹出栈顶的两个数5和7，计算7 * 5 = 35，将结果压入栈，栈为[35]。

最终栈中的元素即为结果35。

6.3. 括号匹配

栈常用于括号匹配问题，特别是在编译器和解释器中，栈是检查是否存在匹配括号的一种有效方式。

实现过程：

通过栈可以有效地检查括号的匹配情况，例如：

遇到一个左括号(时，将其压入栈中。遇到右括号)时，弹出栈顶元素，并确保栈中存在对应的左括号(。如果栈为空或者遇到不匹配的括号，则说明括号不匹配。

示例：

检查括号匹配的代码：

#include <stdio.h> #include <stdbool.h> #define MAX 100 typedef struct { char items[MAX]; int top; } Stack; void initStack(Stack* stack) { stack->top = -1; } bool isEmpty(Stack* stack) { return stack->top == -1; } void push(Stack* stack, char value) { stack->items[++(stack->top)] = value; } char pop(Stack* stack) { return stack->items[(stack->top)--]; } bool isValid(char* s) { Stack stack; initStack(&stack); for (int i = 0; s[i] != '\0'; i++) { if (s[i] == '(') { push(&stack, s[i]); } else if (s[i] == ')') { if (isEmpty(&stack)) { return false; // 没有匹配的左括号 } pop(&stack); // 弹出栈顶左括号 } } return isEmpty(&stack); // 如果栈为空，说明所有括号匹配 } int main() { char s[] = "(())"; if (isValid(s)) { printf("括号匹配!\n"); } else { printf("括号不匹配!\n"); } return 0; } 6.4. 浏览器历史记录和撤销操作

栈还被广泛用于实现浏览器的历史记录和撤销操作，这是由于栈的后进先出（LIFO）特性。

浏览器历史记录：

浏览器通过栈来保存用户访问的网页，每访问一个新网页时，当前网页的URL会被压入栈中，用户点击"后退"按钮时，浏览器会从栈顶弹出上一个网页的URL，展示该页面。

撤销操作：

例如在文本编辑器中，栈用于保存操作记录（如文本插入、删除等），当用户点击"撤销"时，可以通过弹出栈顶的操作记录来撤销最近的操作。

6.5. 深度优先搜索（DFS）

栈是深度优先搜索（DFS）算法的基础。在图的遍历中，深度优先搜索使用栈来存储待访问的节点，直到访问完所有可能的节点。

实现过程：

从某个节点开始，访问该节点并将其压入栈中。然后遍历该节点的所有未访问的邻居，将它们压入栈中。每次弹出栈顶节点，继续遍历该节点的邻居，直到栈为空为止。

这种方式常用于遍历无向图、有向图或解决迷宫问题等。

6.6. 逆序操作

栈可以用于实现逆序操作，例如将一个序列反转。

实现过程：

通过将序列中的元素压入栈中，然后再从栈中逐个弹出元素，这样就能得到一个逆序的序列。

示例：

反转字符串的代码：

#include <stdio.h> #include <string.h> #define MAX 100 typedef struct { char items[MAX]; int top; } Stack; void initStack(Stack* stack) { stack->top = -1; } void push(Stack* stack, char value) { stack->items[++(stack->top)] = value; } char pop(Stack* stack) { return stack->items[(stack->top)--]; } void reverseString(char* str) { Stack stack; initStack(&stack); int length = strlen(str); // 将字符串字符压入栈 for (int i = 0; i < length; i++) { push(&stack, str[i]); } // 从栈中弹出字符，形成逆序字符串 for (int i = 0; i < length; i++) { str[i] = pop(&stack); } } int main() { char str[] = "Hello, World!"; reverseString(str); printf("逆序字符串: %s\n", str); return 0; } 7. 总结

栈是一种遵循LIFO（先进后出）原则的线性数据结构，它的常见应用包括递归函数调用、表达式求值、括号匹配等。本文通过C语言实现了一个基于数组的栈，演示了栈的基本操作：压栈、弹栈、查看栈顶元素、判断栈空和栈满，并附上了详细的注释。栈是一种非常简单但功能强大的数据结构，理解栈的基本操作和应用场景对于学习计算机科学非常重要。

栈作为一种数据结构，在许多计算机科学和实际应用中都扮演着重要的角色。其最典型的应用包括：

函数调用和递归。

表达式求值。

括号匹配。

浏览器历史记录和撤销操作。

深度优先搜索。

逆序操作。

版权声明：本文为原创文章，转载请注明出处。