详解数据结构-栈的基本操作以及栈数组、栈链表的实现（C语言代码实现）

devtools/2024/12/22 19:44:28/

1. 栈的概念

在开始前，请牢记这句话：栈是一种先进后出的数据结构。

栈（stack）是限定仅在表的一端进行操作的数据结构，请联系我们前文所学的，设想一个单链表我们只能够对其链表的表尾结点进行操作，而操作也只能够进行插入一个新的结点与删除最末尾的这个结点两个操作，而这样强限制性的‘链表’，就是我们所说的栈。

让我们重新理顺一下定义：

💡 栈是一个线性的数据结构，规定这个数据结构只允许在其中一端进行操作，并禁止直接访问除这一端以外的数据。

2. 栈的结点设计

栈分为数组栈和链表栈，其区别是数组栈使用数组进行功能的模拟，实现较为快速和便利，而链表栈使用链表的思路去设计，实现较为麻烦，但是其稳定不易出错；在链表栈中又分为静态链表栈和动态链表栈，静态链表栈给定栈的空间大小，不允许超过存储超过给定数据大小的元素，而动态栈使用的是自动创建空间的方法进行创建，只要符合机器的硬件要求以及编译器的控制，其理论上是极大的。

说了那么多，我们以链表栈的动态链表栈为例子，进行栈的设计，在后文直接以栈一名字称呼动态链表栈，这也是各类语言标准模板中栈的实现方式。

首先是栈的结点设计，我们可以设计出两个结构体，一个结构体Node表示结点，其中包含有一个data域和next指针。

其中data表示数据，其可以是简单的类型（如int,double等等），也可以是复杂的结构体（struct类型）；

next指针表示，下一个的指针，其指向下一个结点，通过next指针将各个结点链接。

目前的设计如同单链表，接下来，为这个进行限制性的设计，我们额外添加一个结构体，其包括了一个永远指向栈头的指针top和一个计数器count记录元素个数，（也可以设计成一个指针top和一个指针bottom分别指向栈头和栈尾）其主要功效就是设定允许操作元素的指针以及确定栈何时为空（count的方法是当count为0时为空，top和bottom方法就是两者指向同一个空间时为栈为空）

这里我采用的是top和count组合的方法。其代码可以表示为：

//栈的结点设计
//单个结点设计，数据和下一个指针
typedef struct node     
{int data; struct node *next;
} Node;//利用上面的结点创建栈，分为指向头结点的top指针和计数用的count
typedef struct stack    
{Node *top;int count;
} Link_Stack;

3. 栈的基本操作—入栈

如图：

入栈(push)操作时，我们只需要找到top所指向的空间，创建一个新的结点，将新的结点的next指针指向我们的top指针指向的空间，再将top指针转移，指向新的结点，即是入栈操作

其代码可以表示为：

//入栈 push
Link_Stack *Push_stack(Link_Stack *p, int elem)
{if (p == NULL)return NULL;Node *temp;temp=(Node*)malloc(sizeof(Node));//temp = new Node;temp->data = elem;temp->next = p->top;p->top = temp;p->count++;return p;
}

4. 栈的基本操作—出栈

如图：

出栈（pop）操作，是在栈不为空的情况下（注意一定要进行判空操作），将栈顶的元素删除，同时top指针，next向下进行移动即可的操作。

其代码可以表示为：

//出栈 pop
Link_Stack *Pop_stack(Link_Stack *p)
{Node *temp;temp = p->top;if (p->top == NULL){printf("错误：栈为空");return p;}else{p->top = p->top->next;free(temp);//delete temp;p->count--;return p;}
}

5. 栈的基本操作—遍历

栈的遍历相对而言比较复杂，由于栈的特殊性质，其只允许在一端进行操作，所以我们的遍历操作永远都是逆序的，其过程为，在栈不为空的情况下，一次从栈顶元素向下访问，直到指针指向空（即到栈尾）为结束。

其代码可以表示为：

//遍历栈：输出栈中所有元素
int show_stack(Link_Stack *p)
{Node *temp;temp = p->top;if (p->top == NULL){printf("");printf("错误：栈为空");return 0;}while (temp != NULL){printf("%d\t", temp->data);temp = temp->next;}printf("\n");return 0;
}

6. 快速栈实现--数组栈

数组栈是一种更为快速的模拟实现栈的方法，所谓模拟，就是不采用真实的链表设计，转而采用数组的方式进行“模拟操作”，这是一种仿真类型的操作，其可以快速的帮助我们构建代码，分析过程，相应的实现起来也更加的便捷。

其代码如下（请参考上文进行自主分析）：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 10000//结点设计
typedef struct stack{int data[maxn];int top;
}stack;//创建
stack *init(){stack *s=(stack *)malloc(sizeof(stack));if(s==NULL){printf("分配内存空间失败");exit(0);}memset(s->data,0,sizeof(s->data));//memset操作来自于库文件string.h，其表示将整个空间进行初始化//不理解可以查阅百度百科https://baike.baidu.com/item/memset/4747579?fr=aladdins->top=0;     //栈的top和bottom均为0（表示为空）return s;
}//入栈push
void push(stack *s,int data){s->data[s->top]=data;s->top++;
}//出栈pop
void pop(stack *s){if(s->top!=0){s->data[s->top]=0;  //让其回归0模拟表示未初始化即可s->top--;}
}//模拟打印栈中元素
void print_stack(stack *s){for(int n=s->top-1;n>=0;n--){printf("%d\t",s->data[n]);}printf("\n");   //习惯性换行
}int main(){stack *s=init();int input[5]={11,22,33,44,55};  //模拟五个输入数据for(int i=0;i<5;i++){push(s,input[i]);}print_stack(s);/pop(s);print_stack(s);return 0;
}

7.栈数组的C语言代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 10000//结点设计
typedef struct stack{int data[maxn];int top;
}stack;//创建
stack *init(){stack *s=(stack *)malloc(sizeof(stack));if(s==NULL){printf("分配内存空间失败");exit(0);}memset(s->data,0,sizeof(s->data));//memset操作来自于库文件string.h，其表示将整个空间进行初始化//不理解可以查阅百度百科https://baike.baidu.com/item/memset/4747579?fr=aladdins->top=0;     //栈的top和bottom均为0（表示为空）return s;
}//入栈push
void push(stack *s,int data){s->data[s->top]=data;s->top++;
}//出栈pop
void pop(stack *s){if(s->top!=0){s->data[s->top]=0;  //让其回归0模拟表示未初始化即可s->top--;}
}//模拟打印栈中元素
void print_stack(stack *s){for(int n=s->top-1;n>=0;n--){printf("%d\t",s->data[n]);}printf("\n");   //习惯性换行
}int main(){stack *s=init();int input[5]={11,22,33,44,55};  //模拟五个输入数据for(int i=0;i<5;i++){push(s,input[i]);}print_stack(s);/pop(s);print_stack(s);return 0;
}

8.栈链表的C语言代码实现

#include <stdio.h>
#include <stdlib.h>
//栈的结点设计
//单个结点设计，数据和下一个指针
typedef struct node     
{int data; struct node *next;
} Node;
//利用上面的结点创建栈，分为指向头结点的top指针和计数用的count
typedef struct stack    
{Node *top;int count;
} Link_Stack;//创建栈
Link_Stack *Creat_stack()
{Link_Stack *p;//p = new Link_Stack;p=(Link_Stack*)malloc(sizeof(Link_Stack));if(p==NULL){printf("创建失败，即将退出程序");exit(0);}p->count = 0;p->top = NULL;return p;
}//入栈 push
Link_Stack *Push_stack(Link_Stack *p, int elem)
{if (p == NULL)return NULL;Node *temp;temp=(Node*)malloc(sizeof(Node));//temp = new Node;temp->data = elem;temp->next = p->top;p->top = temp;p->count++;return p;
}//出栈 pop
Link_Stack *Pop_stack(Link_Stack *p)
{Node *temp;temp = p->top;if (p->top == NULL){printf("错误：栈为空");return p;}else{p->top = p->top->next;free(temp);//delete temp;p->count--;return p;}
}//遍历栈：输出栈中所有元素
int show_stack(Link_Stack *p)
{Node *temp;temp = p->top;if (p->top == NULL){printf("");printf("错误：栈为空");return 0;}while (temp != NULL){printf("%d\t", temp->data);temp = temp->next;}printf("\n");return 0;
}int main()
{ //用主函数测试一下功能Link_Stack *p;p = Creat_stack();int n = 5;int input[6] = {10,20,30,40,50,60};/以依次入栈的方式创建整个栈//for(int i=0;i<n;i++){Push_stack(p, input[i]);}show_stack(p);出栈///Pop_stack(p);show_stack(p);return 0;
}

PS：栈的概念被极大量的运用于各种程序设计之中，作为一种数据结构，其先进后出的特殊性质为很多算法的设计埋下伏笔，为之开通快车道。


http://www.ppmy.cn/devtools/103264.html

相关文章

GraphQL：API开发的未来，重塑数据交互的艺术

GraphQL：API开发的未来，重塑数据交互的艺术

标题&#xff1a;GraphQL&#xff1a;API开发的未来&#xff0c;重塑数据交互的艺术 在当今快速发展的Web应用世界中&#xff0c;API&#xff08;应用程序编程接口&#xff09;已成为前后端分离架构的核心。然而&#xff0c;传统的RESTful API存在诸多限制&#xff0c;如过度获…
阅读更多...
LeetCode_sql_day17（1843.可疑银行账户）

LeetCode_sql_day17（1843.可疑银行账户）

描述&#xff1a; 表&#xff1a;Accounts ---------------------- | Column Name | Type | ---------------------- | account_id | int | | max_income | int | ---------------------- account_id 是这张表具有唯一值的列。 每行包含一个银行账户每月最大收入的…
阅读更多...
【离线查询 滑动窗口】2747. 统计没有收到请求的服务器数目

【离线查询 滑动窗口】2747. 统计没有收到请求的服务器数目

本文涉及知识点 离线查询 C算法&#xff1a;滑动窗口总结 LeetCode2747. 统计没有收到请求的服务器数目 给你一个整数 n &#xff0c;表示服务器的总数目&#xff0c;再给你一个下标从 0 开始的 二维 整数数组 logs &#xff0c;其中 logs[i] [server_id, time] 表示 id 为…
阅读更多...
【ceph学习】ceph如何进行数据的读写（1）

【ceph学习】ceph如何进行数据的读写（1）

版本 ceph版本为17. ceph如何进行读写接口的实现 Ceph的客户端通过librados的接口进行集群的访问&#xff0c;这里的访问包括&#xff1a; 1&#xff09;对集群的整体访问 2&#xff09;对象的访问 两类接口&#xff0c;这套接口&#xff08;API&#xff09;包括C、C和Pytho…
阅读更多...
Ruby 多线程

Ruby 多线程

Ruby 多线程 在当今的软件开发领域，多线程已经成为提高程序性能和响应速度的关键技术之一。Ruby，作为一种现代的编程语言，提供了丰富的多线程支持，使得开发者能够轻松地构建高效、并发的应用程序。本文将深入探讨Ruby中的多线程概念、用法以及最佳实践。 什么是多线程？ …
阅读更多...
图像搜索引擎DIY【CLIP+FAISS】

图像搜索引擎DIY【CLIP+FAISS】

你是否曾经想在无穷无尽的图像数据集中查找图像&#xff0c;但发现这太过繁琐&#xff1f;在本教程中&#xff0c;我们将构建一个图像相似性搜索引擎&#xff0c;以便使用文本查询或参考图像轻松查找图像。为方便起见&#xff0c;本文底部以 Colab 笔记本的形式提供了本教程的完…
阅读更多...
PyAutoGui的使用

PyAutoGui的使用

文章目录 一、屏幕1.获取屏幕分辨率2.查看指定位置的像素点是否在屏幕上 二、鼠标1.获取鼠标位置2.控制鼠标运动3.鼠标拖动4.鼠标点击5.鼠标的按压与释放6.鼠标滚动 三、键盘1.控制键盘2.按下后释放一个键3.按顺序按下键&#xff0c;然后反向顺序释放 四、图像1.截图2.获取图像…
阅读更多...
【TPAMI 2024】Occlusion-Aware Self-Supervised Monocular 6D Object Pose Estimation

【TPAMI 2024】Occlusion-Aware Self-Supervised Monocular 6D Object Pose Estimation

TPAMI 2024 | 我3D都没搞明白&#xff0c;这都开始6D了&#xff01;&#xff1f;而且这个单目6D物体姿态估计技术&#xff0c;让机器视觉无需人类教导&#xff01; Occlusion-Aware Self-Supervised Monocular 6D Object Pose Estimation 题目&#xff1a;遮挡感知的自监督单…
阅读更多...
最新文章

Copyright @ 2022~2023