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

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

news 2024/9/25 8:22: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;          // 将栈顶指针设置为 NULLp->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;          // 将栈顶指针设置为 NULLp->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;
}

四、总结

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


http://www.mrgr.cn/news/35606.html

相关文章：

  • Oracle逻辑备份脚本【生产环境适用】
  • 苏轼为何要写石钟山记？时间节点是关键
  • 问：Java线程为不直接run()，而是要先Start()？
  • service 命令：管理系统服务
  • 数据结构 ——— 数组 nums 包含了从 0 到 n 的所有整数，但是其中缺失了一个，请编写代码找出缺失的整数，并且在O(N)时间内完成
  • 【C++前缀和 状态压缩】1177. 构建回文串检测|1848
  • 车辆识别数据集，图片数量20500，模型已训练200轮
  • C语言 | Leetcode C语言题解之第435题无重叠区间
  • TCP/IP 协议栈
  • 使用TensorFlow实现一个简单的神经网络：从构建到训练
  • 240924-通过服务器代理ip地址及port端口wget等下载文件
  • RT-DETR改进策略：BackBone改进|PoolFormer赋能RT-DETR，视觉检测性能显著提升的创新尝试
  • 在Java中，关于final、static关键字与方法的重写和继承【易错点】
  • 点亮城市安全：高科技助力精准定位路灯漏电‘隐形杀手
  • 2024年CSP-J认证 CCF信息学奥赛C++ 中小学初级组 第一轮真题-阅读程序题解析
  • 实战OpenCV之图像滤波
  • 构建预测睡眠质量模型_相关性分析，多变量分析和聚类分析
  • Cloudflare为网站添加AI审计 可检查AI爬虫何时抓取和抓取频次以及直接屏蔽爬虫
  • 从准备面试八股文,感悟到技术的本质
  • GNU链接器（LD）：存储命令（MEMORY）用法及实例解析