栈的深度解析：顺序栈与链栈的实现

🕗 发布于 2024-09-25 13:32 数据结构

引言

栈是一种重要的线性数据结构，遵循“后进先出”（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;
}

四、总结

栈是一种重要的基础数据结构，适用于多种计算场景。通过顺序栈和链式栈的实现，我们可以更好地理解栈的工作原理及其应用。选择哪种实现方式取决于具体需求，顺序栈在内存使用上更高效，而链式栈则提供了更大的灵活性。希望这篇博客能帮助你更好地理解栈的概念和实现！

原文地址：https://blog.csdn.net/2302_81410974/article/details/142496474

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

支持分页的环形队列
最近我因工作需要使用环形队列，并在常规环形队列上拓展为支持分页环形队列，用于高效地管理大量数据，支持高效的元素添加、删除及分页数据的访问。通过分页的方式，它可以有效地管理大规模的数据集合。
阅读更多2024-09-27
Mybatis
MyBatis 是一款优秀的持久层框架MyBatis 避免了几乎所有的 JDBC 代码和手动设置参数以及获取结果集的过程MyBatis 可以使用简单的 XML 或注解来配置和映射原生信息，将接口和 J
阅读更多2024-09-27
pysim-4-1.1.17 eUICC ISD-R commands
pySim-trace 利用 pySim-shell 对 SIM 卡相关知识的现有了解，包括 SIM/USIM/ISIM/HPSIM 卡上各种文件的结构/编码，并将其应用于解码协议跟踪。相反，所有与卡
阅读更多2024-09-27
Vert.x，Databases
Vert.x提供了数据库相关模块(扩展包)，方便我们通过异步方式访问数据库。数据库扩展主要包括：响应式数据库客户端(vertx-xxx-client)和通用JDBC客户端(vertx-jdbc-cli
阅读更多2024-09-27
Python | 第五章节 | 进制
关键字的定义和特点(提示:不用背)定义:被Python语言赋予了特殊含义，用做专门用途的字符串(单词)–对于整数，有如下表示方式2进制: 0,1﹐满2进1. 以0b或0B开头。8进制: 0-7，满8进
阅读更多2024-09-27
【Python】The Algorithms：开源算法的宝库
The Algorithms 是一个开源项目，旨在为开发者提供各种编程语言的算法实现。该项目汇集了数千种算法的实现，涵盖了数据结构、排序算法、数学算法、机器学习、密码学等领域。通过该平台，开发者可以学
阅读更多2024-09-27
普通光耦合器和线性光耦合器之间的区别
光耦合器，也称为光隔离器，在电子电路中起着至关重要的作用，它可以隔离系统的不同部分，同时允许信号在它们之间传递。
阅读更多2024-09-27
SQL - 函数
本文讲解SQL的函数，包含操作函数类别，Aggregate函数类别，Saclar函数类别。针对SQL数据查询更自定义话，针对化。
阅读更多2024-09-27
从零开学C++：二叉搜索树
C++实现搜索二叉树！！
阅读更多2024-09-27
【JAVA 笔记】06 车辆属性抽象类
封装是面向对象编程的一个基本特性，它指的是将数据和操作数据的方法捆绑在一起，形成一个整体（即对象）。类中，我们定义了一个构造函数来初始化父类的属性和自身的属性。好的，我们将进一步拓展这篇文章的内容，深
阅读更多2024-09-27

栈的深度解析：顺序栈与链栈的实现

引言

一、基本概念

1.1 定义

1.2 基本操作

1.3 特点

二、栈的实现

2.1 顺序栈

2.1.1 基本结构

2.1.2 功能实现

1).初始化栈

2).销毁栈

3).入栈

4).判空

5).出栈

6).取栈顶元素

7).栈长度

2.2 链式栈

2.2.1 基本结构

2.2.2 功能实现

1).初始化栈

2).销毁栈

3).入栈

4).判空

5).出栈

6).取栈顶元素

7).栈长度

2.3 对比

三、完整代码

3.1 顺序栈

Stack.h

Stack.c

main.c

3.2 链式栈

Stack.h

Stack.c

main.c

四、总结

相关文章