引言
栈是一种重要的线性数据结构，遵循“后进先出”（LIFO）的原则。栈的应用非常广泛，如表达式求值、括号匹配、递归实现等。在本文中，我们将深入探讨栈的概念，并通过顺序栈和链栈两种实现方式进行对比分析。
一、基本概念
1.1 定义
栈（Stack）是一种只能在一端进行插入和删除操作的集合，遵循“后进先出”（LIFO）原则。即最后加入的元素最先被移除
1.2 基本操作
- 入栈（Push）：将新元素添加到栈顶。
- 出栈（Pop）：移除并返回栈顶元素。
- 查看栈顶元素（Peek）：返回栈顶元素，但不删除它。
- 判断是否为空（isEmpty）：检查栈是否没有元素。
- 统计栈的大小（Size）：获取栈中有效元素个数。
1.3 特点
操作限制：只能在栈顶进行元素的添加（入栈）和移除（出栈）。
栈顶元素：栈顶是当前可以访问和操作的元素。
空栈：栈为空时，无法进行出栈操作。
二、栈的实现
2.1 顺序栈
使用数组实现栈时，我们可以将数组的尾部作为栈顶。
入栈与出栈操作分别对应在数组尾部。添加元素与删除元素，时间复杂度都为 𝑂(1) 。
2.1.1 基本结构
typedef struct Stack { DataType* arr;//数组实现 int top;//栈顶 int capacity;//记录容量 }ST;
2.1.2 功能实现
1).初始化栈
//初始化栈 void StackInit(ST* p) { assert(p); p->arr = NULL; p->top = p->capacity = 0; }
2).销毁栈
//销毁栈 void StackDestory(ST* p) { assert(p); if (p->arr) { free(p->arr); } p->arr = NULL; p->top = p->capacity = 0; }
3).入栈
//入栈 void StackPush(ST* p,DataType x) { assert(p); checkcapacity(p); p->arr[p->top++] = x; }
4).判空
//判断栈顶是否为空 bool StackEmpty(ST* p) { assert(p); return p->top == 0; }
5).出栈
//出栈 void StackPop(ST* p) { assert(p); assert(!StackEmpty(p));//栈顶不为空才能删除 --p->top; }
6).取栈顶元素
//取栈顶元素 DataType StackTop(ST* p) { assert(p); assert(!StackEmpty(p)); return p->arr[p->top - 1]; }
7).栈长度
//获取栈中有效元素个数 int StackSize(ST* p) { assert(p); return p->top; }
2.2 链式栈
使用链表实现栈时，我们可以将链表的头节点视为栈顶，尾节点视为栈底。
对于入栈操作，我们只需将元素插入链表头部，这种节点插入方法被称为“头插法”。而对于
出栈操作，只需将头节点从链表中删除即可。
2.2.1 基本结构
//定义节点结构 typedef struct Node { DataType data;//数据域 struct Node *next;//指针域 }Node; // 定义链栈结构 typedef struct Stack{ Node* top; // 栈顶指针 int size; // 栈中有效元素个数 } ST;
2.2.2 功能实现
1).初始化栈
//初始化栈 void StackInit(ST* p) { assert(p); p->top = NULL; p->size = 0; }
2).销毁栈
//销毁栈 void StackDestory(ST* p) { Node* pcur = p->top; // 从栈顶开始 Node* temp; while (pcur != NULL) { temp = pcur; // 记录当前节点 pcur = pcur->next; // 移动到下一个节点 free(temp); // 释放当前节点的内存 } p->top = NULL; // 将栈顶指针设置为 NULL p->size = 0; // 重置栈的大小 }
3).入栈
//创建节点 //Node* CreateNode(DataType x) //{ // Node* newnode = (Node*)malloc(sizeof(Node)); // if (newnode == NULL) { // perror("malloc fail"); // exit(1); // } // newnode->data = x; // newnode->next = NULL; // return newnode; //} //入栈 void StackPush(ST* p,DataType x) { assert(p); Node* newnode = CreateNode(x); newnode->next = p->top->next; p->top->next = newnode; ++p->size; }
4).判空
//判断栈顶是否为空 bool StackEmpty(ST* p) { assert(p); return p->top->next==NULL;//p->top->next是栈顶元素 }
5).出栈
//出栈 void StackPop(ST* p) { assert(p); assert(!StackEmpty(p));//栈顶不为空才能删除 Node* temp = p->top->next; p->top->next = p->top->next->next; free(temp); temp = NULL; --p->size; }
6).取栈顶元素
//取栈顶元素 DataType StackTop(ST* p) { assert(p); return p->top->next->data; }
7).栈长度
//获取栈中有效元素个数 int StackSize(ST* p) { assert(p); return p->size; }
2.3 对比
顺序栈vs链栈
| 特点 | 顺序栈 | 链式栈 |
| 存储结构 | 基于数组 | 基于链表 |
| 内存管理 | 静态分配(也可动态扩容) | 动态分配 |
| 空间效率 | 容量固定(也可动态扩容) | 动态扩展 |
| 访问速度 | O(1)时间复杂度 | O(1)时间复杂度 |
| 栈溢出 | 容易发生 | 不易发生 |
三、完整代码
3.1 顺序栈
Stack.h
该部分主要包括函数的声明、以及头文件的引用
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int DataType; typedef struct Stack { DataType* arr;//数组实现 int top;//栈顶 int capacity;//记录容量 }ST; //初始化栈 void StackInit(ST* p); //销毁栈 void StackDestory(ST* p); //入栈 void StackPush(ST* p, DataType x); //出栈 void StackPop(ST* p); //取栈顶元素 DataType StackTop(ST* p); //获取栈中有效元素个数 int StackSize(ST* p);
Stack.c
该部分主要包括函数的定义
#define _CRT_SECURE_NO_WARNINGS #include"Stack.h" //初始化栈 void StackInit(ST* p) { assert(p); p->arr = NULL; p->top = p->capacity = 0; } //销毁栈 void StackDestory(ST* p) { assert(p); if (p->arr) { free(p->arr); } p->arr = NULL; p->top = p->capacity = 0; } //判断扩容 void checkcapacity(ST* p) { assert(p); if (p->capacity == p->top) { int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity; DataType* tmp = (DataType*)realloc(p->arr, NewCap * sizeof(DataType)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } p->arr = tmp; p->capacity = NewCap; } } //入栈 void StackPush(ST* p,DataType x) { assert(p); checkcapacity(p); p->arr[p->top++] = x; } //判断栈顶是否为空 bool StackEmpty(ST* p) { assert(p); return p->top == 0; } //出栈 void StackPop(ST* p) { assert(p); assert(!StackEmpty(p));//栈顶不为空才能删除 --p->top; } //取栈顶元素 DataType StackTop(ST* p) { assert(p); assert(!StackEmpty(p)); return p->arr[p->top - 1]; } //获取栈中有效元素个数 int StackSize(ST* p) { assert(p); return p->top; }
main.c
该部分用来测试，即函数的使用
#define _CRT_SECURE_NO_WARNINGS #include"Stack.h" void test01() { ST st; StackInit (&st); StackPush (&st,1); StackPush (&st,3); StackPush (&st,5); StackPush (&st,7); while (!StackEmpty(&st))//栈顶元素依次出栈 { DataType data = StackTop(&st); printf("%d ", data); StackPop(&st);//出栈 } } int main() { test01(); return 0; }
3.2 链式栈
Stack.h
该部分主要包括函数的声明、以及头文件的引用
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int DataType; //定义节点结构 typedef struct Node { DataType data;//数据域 struct Node *next;//指针域 }Node; // 定义链栈结构 typedef struct Stack{ Node* top; // 栈顶指针 int size; // 栈中有效元素个数 } ST; //初始化栈 void StackInit(ST* p); // 创建链表头节点 Node* CreateHead(); //销毁栈 void StackDestory(ST* p); //入栈 void StackPush(ST* p, DataType x); //出栈 void StackPop(ST* p); //取栈顶元素 DataType StackTop(ST* p); //获取栈中有效元素个数 int StackSize(ST* p); 的引用
Stack.c
该部分主要包括函数的定义
#pragma once #include"Stack.h" //初始化栈 void StackInit(ST* p) { assert(p); p->top = NULL; p->size = 0; } //创建节点 Node* CreateNode(DataType x) { Node* newnode = (Node*)malloc(sizeof(Node)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->data = x; newnode->next = NULL; return newnode; } // 创建链表头节点 Node* CreateHead() { Node* headnode = CreateNode(0); // 头节点值为0（或任何不使用的值） return headnode; } //入栈 void StackPush(ST* p,DataType x) { assert(p); Node* newnode = CreateNode(x); newnode->next = p->top->next; p->top->next = newnode; ++p->size; } //判断栈顶是否为空 bool StackEmpty(ST* p) { assert(p); return p->top->next==NULL;//p->top->next是栈顶元素 } //出栈 void StackPop(ST* p) { assert(p); assert(!StackEmpty(p));//栈顶不为空才能删除 Node* temp = p->top->next; p->top->next = p->top->next->next; free(temp); temp = NULL; --p->size; } //取栈顶元素 DataType StackTop(ST* p) { assert(p); return p->top->next->data; } //获取栈中有效元素个数 int StackSize(ST* p) { assert(p); return p->size; } //销毁栈 void StackDestory(ST* p) { Node* pcur = p->top; // 从栈顶开始 Node* temp; while (pcur != NULL) { temp = pcur; // 记录当前节点 pcur = pcur->next; // 移动到下一个节点 free(temp); // 释放当前节点的内存 } p->top = NULL; // 将栈顶指针设置为 NULL p->size = 0; // 重置栈的大小 }
main.c
该部分用来测试，即函数的使用
#define _CRT_SECURE_NO_WARNINGS #include"Stack.h" void test01() { ST st; StackInit(&st); st.top = CreateHead();//栈顶指针指向头节点，故头节点的next为栈顶元素 StackPush(&st,1); StackPush(&st,2); StackPush(&st,3); //StackPop(&st); //int data = StackTop(&st); //int size=StackSize(&st); //printf("%d\n", data); //printf("%d", size); //while (!StackEmpty(&st)) //{ // DataType data = StackTop(&st); // printf("%d ", data); // StackPop(&st);//出栈 //} StackDestory(&st); //st.top = NULL; } int main() { test01(); return 0; }
四、总结
栈是一种重要的基础数据结构，适用于多种计算场景。通过顺序栈和链式栈的实现，我们可以更好地理解栈的工作原理及其应用。选择哪种实现方式取决于具体需求，顺序栈在内存使用上更高效，而链式栈则提供了更大的灵活性。希望这篇博客能帮助你更好地理解栈的概念和实现！
