当前位置： 首页 > news >正文

数据结构：顺序栈与链栈的原理、实现及应用

news 2025/9/4 6:22:51

数据结构详解：顺序栈与链栈的原理、实现及应用

1. 引言：栈的核心概念

栈（Stack）是一种重要的线性数据结构，它遵循后进先出（Last In First Out, LIFO）的原则。这意味着最后一个被添加到栈中的元素将是第一个被移除的元素。栈的这种特性使其在多种计算场景中非常有用，例如函数调用、表达式求值和括号匹配等。
栈的基本操作包括：

  • Push（入栈）：在栈顶添加一个元素
  • Pop（出栈）：移除栈顶元素并返回其值
  • Peek/Top（查看栈顶）：返回栈顶元素但不移除它
  • isEmpty（判空）：检查栈是否为空
    在这篇技术文章中，我们将详细探讨栈的两种主要实现方式：顺序栈（基于数组）和链栈（基于链表），分析它们的优缺点，并提供实际代码示例和应用场景。

2. 顺序栈：数组实现

2.1 顺序栈的结构与特点

顺序栈使用数组作为底层存储结构，这意味着它需要一块连续的内存空间。顺序栈通常包含两个主要部分：一个用于存储元素的数组和一个用于跟踪栈顶位置的整型变量（通常称为"top"或"栈顶指针"）。
顺序栈的主要特点：

  • 内存连续，访问速度快
  • 需要预先指定栈的最大容量
  • 当栈满时无法再添加新元素（除非动态扩容）
  • 操作时间复杂度为O(1)

2.2 顺序栈的实现代码（C语言）

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100 // 定义栈的最大容量typedef struct {int data[MAX_SIZE]; // 存储栈元素的数组int top;            // 栈顶指针
} SeqStack;// 初始化栈
void InitStack(SeqStack *S) {S->top = -1; // 初始化为-1表示空栈
}// 判断栈是否为空
int IsEmpty(SeqStack *S) {return (S->top == -1);
}// 判断栈是否已满
int IsFull(SeqStack *S) {return (S->top == MAX_SIZE - 1);
}// 入栈操作
int Push(SeqStack *S, int value) {if (IsFull(S)) {printf("Stack is full! Push operation failed.\n");return 0;}S->data[++(S->top)] = value; // 栈顶指针先加1，再将元素放入栈顶位置return 1;
}// 出栈操作
int Pop(SeqStack *S, int *value) {if (IsEmpty(S)) {printf("Stack is empty! Pop operation failed.\n");return 0;}*value = S->data[(S->top)--]; // 先取出栈顶元素，再将栈顶指针减1return 1;
}// 获取栈顶元素（但不删除）
int GetTop(SeqStack *S, int *value) {if (IsEmpty(S)) {printf("Stack is empty!\n");return 0;}*value = S->data[S->top];return 1;
}// 打印栈中的所有元素
void PrintStack(SeqStack *S) {if (IsEmpty(S)) {printf("Stack is empty!\n");return;}printf("Stack elements (from bottom to top): ");for (int i = 0; i <= S->top; i++) {printf("%d ", S->data[i]);}printf("\n");
}

2.3 顺序栈的优缺点分析

优点：

  1. 访问速度快：由于内存连续，CPU缓存友好，访问效率高
  2. 实现简单：代码逻辑直接，易于理解和实现
  3. 内存开销小：只需要一个数组和一个整型变量，无需额外指针开销
    缺点：
  4. 固定容量：需要预先定义栈的大小，可能导致空间浪费或栈溢出
  5. 扩容困难：当栈满时，扩容需要创建新数组并复制所有元素，时间复杂度为O(n)
  6. 不灵活：难以适应动态变化的数据规模

3. 链栈：链表实现

3.1 链栈的结构与特点

链栈使用链表作为底层存储结构，每个元素包含数据部分和指向下一个节点的指针。链栈通常将链表的头部作为栈顶，这样入栈和出栈操作可以直接在链表头部进行，时间复杂度为O(1)。
链栈的主要特点：

  • 使用离散的内存空间，通过指针连接
  • 无需预先指定容量，可以动态增长
  • 只有当内存耗尽时才会出现"栈满"情况
  • 每个元素需要额外空间存储指针

3.2 链栈的实现代码（C语言）

#include <stdio.h>
#include <stdlib.h>// 定义栈节点结构
typedef struct StackNode {int data;               // 数据域struct StackNode *next; // 指针域
} StackNode;// 定义链栈结构
typedef struct {StackNode *top; // 栈顶指针
} LinkStack;// 初始化栈
void InitLinkStack(LinkStack *S) {S->top = NULL;
}// 判断栈是否为空
int IsEmpty(LinkStack *S) {return (S->top == NULL);
}// 入栈操作
void Push(LinkStack *S, int value) {// 创建新节点StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));if (newNode == NULL) {printf("Memory allocation failed! Push operation failed.\n");return;}newNode->data = value;newNode->next = S->top; // 新节点指向原栈顶S->top = newNode;       // 更新栈顶指针为新节点
}// 出栈操作
int Pop(LinkStack *S, int *value) {if (IsEmpty(S)) {printf("Stack is empty! Pop operation failed.\n");return 0;}StackNode *temp = S->top; // 临时保存栈顶节点*value = temp->data;S->top = S->top->next; // 更新栈顶指针为下一个节点free(temp);            // 释放原栈顶节点的内存return 1;
}// 获取栈顶元素（但不删除）
int GetTop(LinkStack *S, int *value) {if (IsEmpty(S)) {printf("Stack is empty!\n");return 0;}*value = S->top->data;return 1;
}// 打印栈中的所有元素
void PrintStack(LinkStack *S) {if (IsEmpty(S)) {printf("Stack is empty!\n");return;}printf("Stack elements (from top to bottom): ");StackNode *current = S->top;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}// 销毁栈，释放所有节点内存
void DestroyStack(LinkStack *S) {StackNode *current = S->top;while (current != NULL) {StackNode *temp = current;current = current->next;free(temp);}S->top = NULL;
}

3.3 链栈的优缺点分析

优点：

  1. 动态大小：无需预先指定栈的大小，可以随需求动态增长
  2. 内存高效：只分配实际需要的空间，没有容量浪费
  3. 灵活性：适合数据规模动态变化较大的场景
    缺点：
  4. 额外内存开销：每个节点需要额外空间存储指针
  5. 访问速度稍慢：由于内存不连续，CPU缓存不友好
  6. 内存管理复杂：需要手动管理内存分配和释放，容易导致内存泄漏如果处理不当

4. 顺序栈与链栈的对比

为了更清晰地理解两种实现的差异，下表列出了顺序栈和链栈的主要特性对比：

特性顺序栈链栈
存储方式连续的内存空间（数组）离散的内存空间（链表）
容量固定，需预先定义动态增长，受限于可用内存
空间效率可能有浪费（数组固定大小）无浪费（按需分配）
时间效率所有操作 O(1)所有操作 O(1)
内存管理简单，系统自动回收需手动管理节点内存的申请和释放
适用场景数据规模已知或变化不大的场景数据规模动态变化较大的场景

选择建议：

  • 如果数据规模已知且变化不大，或者对性能要求极高，优先选择顺序栈
  • 如果数据规模变化较大或无法预估最大容量，优先选择链栈

5. 栈的应用实例

例题名称核心知识点难度
括号匹配栈的基本操作、LIFO特性⭐
表达式求值栈管理运算符优先级、后缀表达式⭐⭐
模拟浏览器前进后退双栈协作、状态管理⭐⭐
递归的非递归实现栈模拟函数调用栈⭐⭐
行编辑程序（含退格）栈处理输入、删除逻辑⭐⭐

📝 5.1 括号匹配问题

问题描述：检查一个字符串中的括号是否正确匹配，有效的字符串需满足：左括号必须用相同类型的右括号闭合，且左括号必须以正确的顺序闭合。

解决思路：遍历字符串，遇到左括号就入栈；遇到右括号时，检查栈顶的左括号是否与之匹配。匹配则弹出栈顶，否则无效。最后栈应为空。

代码实现（C语言，顺序栈）：

#include <stdio.h>
#include <stdbool.h>#define MAX_SIZE 100typedef struct {char data[MAX_SIZE];int top;
} SeqStack;void initStack(SeqStack *s) { s->top = -1; }
bool isEmpty(SeqStack *s) { return s->top == -1; }
bool isFull(SeqStack *s) { return s->top == MAX_SIZE - 1; }bool push(SeqStack *s, char c) {if (isFull(s)) return false;s->data[++(s->top)] = c;return true;
}bool pop(SeqStack *s, char *c) {if (isEmpty(s)) return false;*c = s->data[(s->top)--];return true;
}bool peek(SeqStack *s, char *c) {if (isEmpty(s)) return false;*c = s->data[s->top];return true;
}bool isValid(char* s) {SeqStack stack;initStack(&stack);char topChar;for (int i = 0; s[i] != '\0'; i++) {if (s[i] == '(' || s[i] == '[' || s[i] == '{') {push(&stack, s[i]);} else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {if (!peek(&stack, &topChar)) return false; // 栈空，有右括号无左括号匹配if ((s[i] == ')' && topChar == '(') ||(s[i] == ']' && topChar == '[') ||(s[i] == '}' && topChar == '{')) {pop(&stack, &topChar);} else {return false; // 括号类型不匹配}}}return isEmpty(&stack); // 检查是否所有左括号都被匹配
}int main() {char expr[] = "({[]})";printf("%s is %s\n", expr, isValid(expr) ? "valid" : "invalid");return 0;
}

🧮 5.2 表达式求值

问题描述：计算算术表达式的值，例如 4 + 2 * 3 - 10 / (7 - 5)。

解决思路：使用两个栈，一个存放操作数，一个存放运算符。根据运算符的优先级决定计算顺序。

代码概要（C语言）：

// 此处假设已定义顺序栈结构 SeqStack 及其基本操作int getPriority(char op) {switch(op) {case '+': case '-': return 1;case '*': case '/': return 2;default: return 0;}
}int calculate(int a, int b, char op) {switch(op) {case '+': return a + b;case '-': return a - b;case '*': return a * b;case '/': return a / b; // 注意除零错误default: return 0;}
}int evalExpression(char* expr) {SeqStack opnd; // 操作数栈SeqStack optr; // 运算符栈initStack(&opnd);initStack(&optr);push(&optr, '#'); // 预设一个起始符int i = 0;char ch, topOp, arithmeticOp;int num, a, b;while (expr[i] != '\0' || !isEmpty(&optr)) {ch = expr[i];if (ch == ' ') { i++; continue; } // 跳过空格if (ch >= '0' && ch <= '9') { // 处理数字num = 0;while (expr[i] >= '0' && expr[i] <= '9') {num = num * 10 + (expr[i] - '0');i++;}push(&opnd, num);} else if (ch == '(') {push(&optr, '(');i++;} else if (ch == ')') {peek(&optr, &topOp);while (topOp != '(') {pop(&optr, &arithmeticOp);pop(&opnd, &b); pop(&opnd, &a);push(&opnd, calculate(a, b, arithmeticOp));peek(&optr, &topOp);}pop(&optr, &topOp); // 弹出左括号i++;} else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {peek(&optr, &topOp);while (getPriority(topOp) >= getPriority(ch)) {pop(&optr, &arithmeticOp);pop(&opnd, &b); pop(&opnd, &a);push(&opnd, calculate(a, b, arithmeticOp));peek(&optr, &topOp);}push(&optr, ch);i++;} else {i++; // 处理其他字符或结束}}pop(&opnd, &num); // 最终结果return num;
}
// 主函数中测试
int main() {char expr[] = "4 + 2 * 3 - 10 / (7 - 5)";printf("Result of %s is %d\n", expr, evalExpression(expr));return 0;
}

🌐 5.3 模拟浏览器前进后退功能

问题描述：使用两个栈模拟浏览器的前进后退功能。

解决思路：使用两个栈，backStack 存放后退的页面，forwardStack 存放前进的页面。访问新页面时压入 backStack 并清空 forwardStack；后退时从 backStack 弹出并压入 forwardStack；前进时从 forwardStack 弹出并压入 backStack。

代码概要（C语言，链栈）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct PageNode {char url[100];struct PageNode* next;
} PageNode;typedef struct {PageNode* top;
} LinkStack;void initStack(LinkStack* s) { s->top = NULL; }
bool isEmpty(LinkStack* s) { return s->top == NULL; }void push(LinkStack* s, const char* url) {PageNode* newNode = (PageNode*)malloc(sizeof(PageNode));strcpy(newNode->url, url);newNode->next = s->top;s->top = newNode;
}bool pop(LinkStack* s, char* url) {if (isEmpty(s)) return false;PageNode* temp = s->top;strcpy(url, temp->url);s->top = s->top->next;free(temp);return true;
}bool peek(LinkStack* s, char* url) {if (isEmpty(s)) return false;strcpy(url, s->top->url);return true;
}// 模拟浏览器
LinkStack backStack, forwardStack;
void initBrowser() {initStack(&backStack);initStack(&forwardStack);
}void visitUrl(const char* url) {push(&backStack, url);// 访问新页面时清空前进栈char tempUrl[100];while (pop(&forwardStack, tempUrl)) { /* 只是清空 */ }printf("Visited: %s\n", url);
}void goBack() {char currentUrl[100], backUrl[100];if (pop(&backStack, currentUrl) && peek(&backStack, backUrl)) {push(&forwardStack, currentUrl);printf("Back to: %s\n", backUrl);} else {printf("Cannot go back.\n");}
}void goForward() {char forwardUrl[100];if (pop(&forwardStack, forwardUrl)) {push(&backStack, forwardUrl);printf("Forward to: %s\n", forwardUrl);} else {printf("Cannot go forward.\n");}
}int main() {initBrowser();visitUrl("www.homepage.com");visitUrl("www.news.com");visitUrl("www.mail.com");goBack();   // 回到 www.news.comgoBack();   // 回到 www.homepage.comgoForward(); // 前进到 www.news.comvisitUrl("www.search.com"); // 此时前进栈被清空return 0;
}

🔄 5.4 递归的非递归实现

问题描述：使用栈模拟递归过程，例如计算阶乘。

解决思路：递归的本质是函数调用栈，我们可以用显式栈来模拟。

代码实现（C语言，顺序栈实现阶乘）：

#include <stdio.h>long factorialIterative(int n) {SeqStack stack; // 假设使用之前的顺序栈，存储类型为intinitStack(&stack);long result = 1;if (n == 0 || n == 1) return 1;while (n > 1) {push(&stack, n);n--;}int current;while (!isEmpty(&stack)) {pop(&stack, &current);result *= current;}return result;
}int main() {int n = 5;printf("Iterative %d! = %ld\n", n, factorialIterative(n));return 0;
}

⌨️ 5.5 行编辑程序

问题描述：输入若干串字符，遇到换行符 \n 则输出本行当前处理结果。输入以 # 结束。输入 @ 表示回退到本行行首，输入 `` 表示回退一格。

解决思路：使用栈存储当前行的字符。遇到普通字符入栈；遇到 `` 则出栈（相当于退格）；遇到 @ 则清空栈（相当于清空当前行）。

代码概要（C语言，顺序栈）：

#include <stdio.h>void lineEditor() {SeqStack s;initStack(&s);char ch, temp;printf("Enter your text (end with #, use @ to clear line, use  to backspace):\n");while ((ch = getchar()) != '#') {if (ch == '\n') {// 输出当前行printf("\nLine output: ");// 逆序输出栈内容较为复杂，可以先用一个临时栈反转SeqStack tempStack;initStack(&tempStack);while (!isEmpty(&s)) {pop(&s, &temp);push(&tempStack, temp);}while (!isEmpty(&tempStack)) {pop(&tempStack, &temp);putchar(temp);}printf("\n");initStack(&s); // 清空栈准备下一行} else if (ch == '@') {initStack(&s); // 清空栈（回退到行首）} else if (ch == '') {pop(&s, &temp); // 出栈（回退一格）} else {if (!isFull(&s)) {push(&s, ch); // 普通字符入栈} else {printf("Stack is full!\n");}}}
}int main() {lineEditor();return 0;
}

5.1 括号匹配问题

问题描述：给定一个只包括 '(', ')', '{', '}', '[', ']' 的字符串，判断字符串中的括号是否匹配正确。
解决方案：使用栈来检查括号匹配

  • 遇到左括号时，将其压入栈中
  • 遇到右括号时，检查栈顶的左括号是否与之匹配
  • 最后检查栈是否为空
    代码实现：
int isValid(char* s) {SeqStack stack;InitStack(&stack);int i = 0;char ch;while (s[i] != '\0') {if (s[i] == '(' || s[i] == '[' || s[i] == '{') {Push(&stack, s[i]); // 遇到左括号，入栈} else {if (IsEmpty(&stack)) { // 遇到右括号但栈已空，不匹配return 0;}GetTop(&stack, &ch); // 获取栈顶元素if ((s[i] == ')' && ch == '(') ||(s[i] == ']' && ch == '[') ||(s[i] == '}' && ch == '{')) {Pop(&stack, &ch); // 匹配成功，弹出栈顶元素} else {return 0; // 不匹配}}i++;}return IsEmpty(&stack); // 最后栈空则有效，非空则无效
}

6. 总结与展望

通过本文的详细讲解，我们了解了：

  1. 栈是一种后进先出（LIFO）的线性数据结构
  2. 栈有两种主要实现方式：顺序栈（基于数组）和链栈（基于链表）
  3. 顺序栈和链栈各有优缺点，适用于不同场景
  4. 栈在计算机科学中有广泛的应用，如括号匹配、表达式求值和函数调用等
http://www.xdnf.cn/news/1441405.html

相关文章：

  • 解析SWOT分析和PV/UV这两个在产品与运营领域至关重要的知识点。
  • 前端性能优化：请求和响应优化（HTTP缓存与CDN缓存）
  • Redis初阶学习
  • 宋红康 JVM 笔记 Day12｜执行引擎
  • 《SVA断言系统学习之路》【03】关于布尔表达式
  • 番茄生吃熟吃大PK！VC vs 番茄红素，谁更胜一筹？医生不说的秘密！
  • 【算法--链表】142.环形链表中Ⅱ--通俗讲解如何找链表中环的起点
  • Keras/TensorFlow 中 `fit()` 方法参数详细说明
  • 编程基础-eclipse创建第一个程序
  • 存算一体：重构AI计算的革命性技术（3）
  • 浅谈人工智能之阿里云搭建coze平台
  • 【大前端】React 父子组件通信、子父通信、以及兄弟（同级）组件通信
  • 【轨物方案】创新驱动、精准运维：轨物科技场站光伏组件缺陷现场检测解决方案深度解析
  • 【QT随笔】事件过滤器（installEventFilter 和 eventFilter 的组合）之生命周期管理详解
  • 卷积神经网络CNN-part2-简单的CNN
  • 深度学习篇---InceptionNet
  • 深度学习——卷积神经网络
  • 服务器搭建日记（十二）：创建专用用户通过 Navicat 远程连接 MySQL
  • Mac电脑Tomcat+Java项目中 代码更新但8080端口内容没有更新
  • 最新KeyShot 2025安装包下载及详细安装教程
  • leetcode210.课程表II
  • STM32F103按钮实验
  • Redis基础篇
  • 新后端漏洞（上）- Redis 4.x5.x 未授权访问漏洞
  • COB封装固晶载具/IC芯片固晶载具核心功能与核心要求
  • 《明朝那些事》读书笔记-王阳明：「知行合一」
  • Prometheus 配置主机宕机告警
  • 同城跑腿系统 跑腿小程序app java源码 跑腿软件项目运营
  • 存算一体：重构AI计算的革命性技术（2）
  • “互联网 +”时代商业生态变革：以开源 AI 智能名片链动 2+1 模式 S2B2C 商城小程序为例