栈的奥秘：顺序栈与链栈的完美对决
栈是一种重要的线性数据结构，遵循“后进先出”（LIFO）的原则。栈的应用非常广泛，如表达式求值、括号匹配、递归实现等。在本文中，我们将深入探讨栈的概念，并通过顺序栈和链栈两种实现方式进行对比分析。
·
目录
栈是一种重要的线性数据结构，遵循“后进先出”（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; // 栈顶和容量均设为 0
}2).销毁栈
// 销毁栈
void StackDestroy(ST* p)
{
assert(p);
if (p->arr)
{
free(p->arr); // 释放栈内存
}
p->arr = NULL; // 指针置为空
p->top = p->capacity = 0; // 栈顶和容量重置为 0
}3).入栈
// 检查并扩容栈
void checkcapacity(ST* p)
{
assert(p);
if (p->capacity == p->top) // 如果栈已满
{
int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity; // 初次扩容为 4，否则容量加倍
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; // 将元素压入栈顶并更新栈顶索引
}4).判空
// 判断栈是否为空
bool StackEmpty(ST* p)
{
assert(p);
return p->top == 0; // 栈顶为 0 表示栈为空
}5).出栈
// 出栈操作
void StackPop(ST* p)
{
assert(p);
assert(!StackEmpty(p)); // 确保栈不为空
--p->top; // 栈顶索引减 1，表示删除栈顶元素
}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; // 栈的大小初始化为0
}2).销毁栈
// 销毁栈
void StackDestroy(ST* p)
{
assert(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 = newnode; // 更新栈顶为新节点
++p->size;
}4).判空
// 判断栈是否为空
bool StackEmpty(ST* p)
{
assert(p);
return p->top == NULL; // 如果栈顶指针为 NULL，则栈为空
}5).出栈
// 出栈操作
void StackPop(ST* p)
{
assert(p);
assert(!StackEmpty(p)); // 确保栈不为空才能进行出栈操作
Node* temp = p->top; // 记录当前栈顶
p->top = p->top->next; // 将栈顶指针移动到下一个节点
free(temp); // 释放原栈顶节点的内存
temp = NULL;
--p->size;
}6).取栈顶元素
// 获取栈顶元素
DataType StackTop(ST* p)
{
assert(p);
assert(!StackEmpty(p)); // 确保栈不为空
return p->top->data; // 返回栈顶节点的数据
}7).栈长度
// 获取栈中的元素个数
int StackSize(ST* p)
{
assert(p);
return p->size; // 返回栈的大小
}2.3 对比
| 特点 | 顺序栈 | 链式栈 |
|---|---|---|
| 存储结构 | 基于数组 | 基于链表 |
| 内存管理 | 静态分配(也可动态扩容) | 动态分配 |
| 空间效率 | 容量固定(也可动态扩容) | 动态扩展 |
| 访问速度 | 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 StackDestroy(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; // 栈顶和容量均设为 0
}
// 销毁栈
void StackDestroy(ST* p)
{
assert(p);
if (p->arr)
{
free(p->arr); // 释放栈内存
}
p->arr = NULL; // 指针置为空
p->top = p->capacity = 0; // 栈顶和容量重置为 0
}
// 检查并扩容栈
void checkcapacity(ST* p)
{
assert(p);
if (p->capacity == p->top) // 如果栈已满
{
int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity; // 初次扩容为 4，否则容量加倍
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; // 栈顶为 0 表示栈为空
}
// 出栈操作
void StackPop(ST* p)
{
assert(p);
assert(!StackEmpty(p)); // 确保栈不为空
--p->top; // 栈顶索引减 1，表示删除栈顶元素
}
// 获取栈顶元素
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);//出栈
}
StackDestroy(&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);
//销毁栈
void StackDestroy(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; // 栈的大小初始化为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;
}
// 入栈操作
void StackPush(ST* p, DataType x)
{
assert(p);
Node* newnode = CreateNode(x);
newnode->next = p->top; // 新节点的 next 指向当前栈顶
p->top = newnode; // 更新栈顶为新节点
++p->size;
}
// 判断栈是否为空
bool StackEmpty(ST* p)
{
assert(p);
return p->top == NULL; // 如果栈顶指针为 NULL，则栈为空
}
// 出栈操作
void StackPop(ST* p)
{
assert(p);
assert(!StackEmpty(p)); // 确保栈不为空才能进行出栈操作
Node* temp = p->top; // 记录当前栈顶
p->top = p->top->next; // 将栈顶指针移动到下一个节点
free(temp); // 释放原栈顶节点的内存
temp = NULL;
--p->size;
}
// 获取栈顶元素
DataType StackTop(ST* p)
{
assert(p);
assert(!StackEmpty(p)); // 确保栈不为空
return p->top->data; // 返回栈顶节点的数据
}
// 获取栈中的元素个数
int StackSize(ST* p)
{
assert(p);
return p->size; // 返回栈的大小
}
// 销毁栈
void StackDestroy(ST* p)
{
assert(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);
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);//出栈
}
StackDestroy(&st);
//st.top = NULL;
}
int main()
{
test01();
return 0;
}四、总结
栈是一种重要的基础数据结构，适用于多种计算场景。通过顺序栈和链式栈的实现，我们可以更好地理解栈的工作原理及其应用。选择哪种实现方式取决于具体需求，顺序栈在内存使用上更高效，而链式栈则提供了更大的灵活性。希望这篇博客能帮助你更好地理解栈的概念和实现！
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
86
0- 0
已为社区贡献9条内容
所有评论(0)