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

C语言栈的描述和详解

news 来源：原创 2025/9/5 17:37:36

什么是栈？

栈是一种特殊的线性数据结构。

定义及特点

- 栈是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出（Last In First Out，LIFO）的原则存储数据，就像一个只能从顶部取放物品的箱子，最后放入的物品会最先被取出。

实现方式

- 栈可以用数组或链表来实现。用数组实现时，通常用一个变量来记录栈顶元素的位置。用链表实现时，栈顶指针指向链表的头节点，入栈和出栈操作主要在链表头部进行。

最常见的栈为数组栈和链表栈

数组栈

#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100// 定义栈结构typedef struct {int data[MAX_SIZE];int top;} Stack;// 初始化栈void initStack(Stack *s) {s->top = -1;}// 判断栈是否为空int isEmpty(Stack *s) {return s->top == -1;}// 判断栈是否已满int isFull(Stack *s) {return s->top == MAX_SIZE - 1;}// 入栈操作void push(Stack *s, int value) {if (isFull(s)) {printf("栈已满，无法入栈\n");return;}s->data[++(s->top)] = value;}// 出栈操作int pop(Stack *s) {if (isEmpty(s)) {printf("栈为空，无法出栈\n");return -1;}return s->data[(s->top)--];}// 获取栈顶元素int peek(Stack *s) {if (isEmpty(s)) {printf("栈为空，无栈顶元素\n");return -1;}return s->data[s->top];}

数组栈采用静态连续内存，有一定的内存局限性，也有代码量小带来的方便性

链表栈

#include <stdio.h>#include <stdlib.h>// 定义链表节点结构typedef struct Node {int data;struct Node *next;} Node;// 定义栈结构typedef struct {Node *top;} Stack;// 初始化栈void initStack(Stack *s) {s->top = NULL;}// 判断栈是否为空int isEmpty(Stack *s) {return s->top == NULL;}// 入栈操作void push(Stack *s, int value) {Node *newNode = (Node *)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败\n");return;}newNode->data = value;newNode->next = s->top;s->top = newNode;}// 出栈操作int pop(Stack *s) {if (isEmpty(s)) {printf("栈为空，无法出栈\n");return -1;}Node *temp = s->top;int value = temp->data;s->top = s->top->next;free(temp);return value;}// 获取栈顶元素int peek(Stack *s) {if (isEmpty(s)) {printf("栈为空，无栈顶元素\n");return -1;}return s->top->data;}

链表栈内存分配灵活，不受限制。

你可以在上述代码基础上添加 main 函数来测试栈的各种操作

int main() {Stack stack;initStack(&stack);push(&stack, 10);push(&stack, 20);printf("栈顶元素: %d\n", peek(&stack));printf("出栈元素: %d\n", pop(&stack));printf("栈是否为空: %d\n", isEmpty(&stack));return 0;}

接下来用一串我写的描述清晰的代码

来解释链式栈如何构建和使用。

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;//数据域
struct node *next;//指针域存储下一个节点的位置，末节点的next为空
}Node;//栈节点结构体
typedef struct h{
Node *top; //栈头指向的节点
}Head;//栈头结构体Head * creat_head()//栈头的创建
{
Node *newhead=(Node *)malloc(sizeof(Node));//为创建栈头分配内存
newhead->next=NULL;//栈头初始指向空
return newhead;//返回创建的地址返回给所需栈头
}Node *creat_node(int data)//节点的创建
{
Node *newnode=(Node *)malloc(sizeof(Node));//为新创建的节点分配内存
newnode->data=data; //新节点数据域存储用户输入数据
newnode->next=NULL; //新节点默认指向空
return newnode;//返回创造新节点的地址
}
int isNULL(Head *head) {//判断栈是否为空return head->top == NULL;
}
void in(Head *head,int data)//in 数据入栈
{
Node *N = creat_node(data);
N->next = head->top;//将新建的节点插入栈顶，成为新的栈顶
head->top = N;//刷新栈头指针指向新的栈顶元素
}int out(Head *head) //out 数据出栈
{
if(isNULL(head))
{
printf("栈空了");
return -1;
}
int N = head->top->data;//获取节点数据域数值
Node *huan = head->top->next;//存储下一节点的地址
free(head->top);//释放掉当前访问的节点内存
head->top = huan;//将栈头指针指向下一个节点
return N;//返回该节点数据域数值
}
void freehead(Head *head)//释放未访问的栈内存
{
Node *temp = head->top; //获取栈头指针地址
while(temp!=NULL)
{
Node *huan = temp->next; //反复储存下一节点，释放当前节点内存
free(temp);
temp = huan;//刷新指针指向下一节点
}
free(head);//最后释放栈头指针，此步骤之后，栈内存已经被全部释放
}int peek(Head *head) {//访问栈顶元素if (isNULL(head)) {printf("栈为空，无栈顶元素\n");return -1;}return head->top->data;
}int main()//主函数使用栈
{
Head *head = creat_head();//创建栈头
int data;
scanf("%d",&data);//获取用户存储的数据
int ctr=1;
while(ctr)//循环存储栈元素
{
in(head,data);//数据存入栈内
printf("继续向栈内存储请输入 1 \n结束并输出栈请输入 0\n您的输入：");
scanf("%d",&ctr);
if(!ctr)//判断是否继续存储数据
break;
printf("请继续存储数值:");
scanf("%d",&data);
}
printf("\n栈顶元素：%d",peek(head));//访问前访问栈顶元素
printf("\n\n");
while(!isNULL(head))//遍历访问出栈输出
printf("%d\n",out(head));printf("\n\n\n%d",peek(head));//全访问后访问栈顶元素freehead(head);//释放未访问空间//该函数如果只访问一部分栈元素，可用于剩余未访问栈元素的内存释放return 0;}

栈的一些运用方面

迷宫求解

- 可以用栈来记录路径。从起点开始，将当前位置压入栈，然后探索相邻的未访问过的位置。如果遇到死胡同，就从栈中弹出当前位置，回溯到上一个位置，继续尝试其他路径，直到找到出口或遍历完整个迷宫。

汉诺塔问题

- 汉诺塔问题是经典的递归问题，也可以用栈来辅助解决。通过将圆盘的移动过程模拟为栈的操作，用栈来记录每个柱子上圆盘的状态，从而实现对汉诺塔问题的求解。

树的遍历

- 例如二叉树的深度优先遍历（先序、中序、后序遍历），可以借助栈来实现非递归算法。以先序遍历为例，先将根节点入栈，然后每次取出栈顶节点进行访问，并将其右孩子和左孩子（如果存在）依次入栈，重复这个过程，直到栈为空。

状态机实现

- 在状态机中，栈可以用来存储状态信息。当状态发生转换时，将当前状态压入栈，以便在需要时可以回溯到之前的状态。例如，在编译器的词法分析器中，用栈来保存扫描到的单词的状态，以实现对输入字符流的正确解析。

函数调用和递归

在程序执行过程中，函数调用会使用栈来管理调用上下文。当一个函数被调用时，系统会将当前函数的状态（如局部变量、返回地址等）压入栈中，形成一个栈帧。当函数执行完毕后，再从栈中弹出栈帧，恢复之前的执行状态。递归调用也是基于栈来实现的，每一次递归调用都会在栈上创建一个新的栈帧，直到满足终止条件后，再依次从栈中弹出栈帧返回结果

表达式求值

在编译器和解释器中，栈可以用于计算算术表达式的值。例如，对于中缀表达式转后缀表达式（逆波兰表达式），以及后缀表达式的求值过程，栈都起着关键作用。在计算后缀表达式时，遇到操作数就将其压入栈中，遇到运算符则从栈中弹出相应数量的操作数进行计算，并将结果压入栈中。

括号匹配检查

在编写代码或处理文本时，需要检查括号是否匹配。可以使用栈来实现这个功能，遍历字符串，遇到左括号时将其压入栈中，遇到右括号时从栈中弹出一个左括号进行匹配，如果不匹配或栈为空则说明括号不匹配。

路径简化问题

在文件系统里，路径可能包含 .（当前目录）、..（上级目录）等特殊符号。栈可用于简化这些路径，去除不必要的符号。遍历路径中的每个目录部分，若遇到 . 则忽略；若遇到 .. 且栈不为空，就从栈中弹出一个目录；若遇到普通目录名，则将其压入栈。

深度优先搜索（DFS）

在图和树的遍历算法中，深度优先搜索是一种常用的算法。栈可用于实现非递归的深度优先搜索。从起始节点开始，将其压入栈，接着不断从栈中弹出节点并访问，同时把该节点的未访问邻接节点压入栈。

浏览器的后退和前进功能

浏览器的后退和前进功能可以用两个栈来实现。访问新页面时，将当前页面压入后退栈，同时清空前进栈；点击后退按钮时，将当前页面压入前进栈，从后退栈中弹出一个页面并显示；点击前进按钮时，将当前页面压入后退栈，从前进栈中弹出一个页面并显示。