数据结构之栈(C语言实现)

2021-09-23

1.  什么是栈

    栈其实就是一种线性表。只不过它有点特殊,它的特殊性主要体现在它是一种后进先出(Last In First Out)的线性表,跟队列刚好相对应,队列刚好是先进先出(First In First Out)的在栈中只能在一端进行操作,就是说保存数据和取出数据只能从线性表的一端进行,一般地操作端我们称之为栈顶,另一端则称为栈底。

2.  栈的基本操作

栈的基本操作只有两个:
入栈(push):即将数据保存在栈顶。进行该操作前,先修改栈顶指针,使其向上移动一个元素位置,然后将数据保存在栈顶指针所指向的位置。
出栈(pop):即将栈顶的数据弹出,然后修改栈顶指针,使其指向栈中的下一个元素。
在栈中,只有栈顶元素是可以访问的。


3.  两种栈

一般地,栈使用两种存储表示方法。
顺序栈:使用一组连续的内存单元依次保存栈中的数据。一般情况下使用数组作为顺序栈,序号为0的元素就是栈底,再定义一个变量来保存栈顶的序号即可。
链式栈:使用链表形式来保存栈中个元素的值,链表尾部(指向地址NULL)为栈底,链表的首部(head指针所指向的元素)为栈顶。
两种栈的最大区别就是顺序栈是分布在一片连续的内存单元里,而链式栈一般是分布在零散的内存单元当中。


接下来我们使用顺序栈来实现一个保存学生姓名和年龄的小实例。下面我们来一步一步的缕一下整个思路。

1.要使用栈,那么我们首先应该定义一个栈结构

代码:

//定义顺序栈的结构 typedef struct stack {   student data[SIZE+1];    //数据元素   int top;              //栈顶 }SeqStack;

其中栈结构里面包含了2个元素,一个是结构体数组,数组名为data,其类型为student结构体,用来保存学生的姓名和年龄。另一个整形变量top用来表示栈顶的序号。
2.定义好了栈结构,接下来就应该初始化栈。

代码:

//初始化栈 SeqStack * SeqStackInit() {   SeqStack *p;   if (p = (SeqStack *)malloc(sizeof(SeqStack)))         //申请栈内存   {     p->top = 0;     return p;   }   return NULL;             //申请内存失败返回空值 }

顺序栈的初始化需要做2件事情:首先需要申请一片合适的内存来保存栈中的数据,然后设置栈顶指针的值为0,表示这是一个空栈。
3.  释放栈内存

代码:

 //释放栈内存 void SeqStackFree(SeqStack *s) {   if(s)     free(s); }

使用完毕,应该及时释放栈内存,否则有可能造成内存泄漏。
4.  判断栈的当前状态
  

代码:

//判断栈的状态 int SeqStackIsEmpty(SeqStack *s)                 //判断栈是否为空 {   return(s->top == 0); } void SeqStackClear(SeqStack *s)               //清空栈 {   s->top = 0; } void SeqStackIsFull(SeqStack *s)      //判断栈是否已满 {   return(s->top == SIZE); }

在对栈进行操作之前通常先要判断一下栈的当前状态,再决定如何进行操作。入栈前应该先判断栈是否已满,出栈前应该判断栈是否为空。
5.  入栈

代码:

 //入栈 int SeqStackPush(SeqStack *s, student data)     //入栈操作 {   if ((s->top+1) > SIZE)   {     printf("栈溢出!\n");     return 0;   }   s->data[++s->top] = data;         //将元素入栈   return 1; }

首先判断top是否大于等于SIZE,如果结果为真,那么给出溢出提示。
第二设置top=top+1,栈顶指针加1,指向入栈地址,在这里我们可以想一想前面栈的基本操作当中所说的入栈需要做些什么事情。
最后将入栈元素保存到top指向的位置。在这里注意++和->这两个运算符,其中++是个前缀运算符,他的优先级低于->运算符。请注意前缀++和后缀++的优先级是不一样的。

6.  出栈
 

代码:

//出栈 student SeqStackPop(SeqStack *s)     //出栈操作 {   if (s->top == 0)   {     printf("栈为空!\n");     exit(0);   }   return (s->data[s->top--]);            //弹出栈顶元素 }

首先判断top是否小于等于0.如果结果为真,则提示栈为空。
第二将栈顶指针top所指向位置的元素返回。
最后设置top=top-1,使栈顶减1,指向栈的下一个元素。
在这里同样可以参考一下上面栈的基本操作当中关于出栈的操作。

7.  获取栈顶元素
 

代码:

//获取栈顶的元素 student SeqStackPeek(SeqStack *s)          //读取栈顶元素 {   if (s->top == 0)         //判断栈是否为空   {     printf("栈为空!");     exit(0);   }   return (s->data[s->top]);  //返回栈顶元素 }

使用出栈函数操作后,原来栈顶的元素就被弹出了,也就是说出栈后原来栈顶的元素就不存在了。但是在有些时候我们可能会需要获取栈顶的元素,但又需要继续保留该元素在栈顶,这是就用到了这个函数,注意它与SeqStackPop函数的区别,该函数只是返回当前栈顶的元素,并不修改栈顶指针,所以获取栈顶元素后,原来的栈顶依然存在。
有了上面足够的知识,我们开始在main函数中实现一下这个小实例的具体操作。


以下是SeqStackTest.c的代码

代码:

#include <stdio.h> #include <stdlib.h> #define SIZE 50 typedef struct   {   char name[15];   int age; }student; #include "SeqStack.h"  int main() {   SeqStack *stack;   student pushstudent,popstudent;             //定义栈操作的元素   stack = SeqStackInit();      //初始化栈   printf("入栈操作!\n");   printf("输入姓名 年龄进行入栈操作:\n");   scanf("%s%d",pushstudent.name,&pushstudent.age);   SeqStackPush(stack,pushstudent);             //入栈   printf("输入姓名 年龄进行入栈操作:\n");   scanf("%s%d",pushstudent.name,&pushstudent.age);   SeqStackPush(stack,pushstudent);             //入栈    printf("\n出栈操作:\n按任意键进行出栈操作:\n");   getchar();   popstudent = SeqStackPop(stack);        //出栈   printf("出栈的数据是:\n");      printf("%10s%10s\n","姓名","年龄");   printf("%10s%10d\n",popstudent.name,popstudent.age);   printf("再按任意键进行出栈操作:");   getchar();   popstudent = SeqStackPop(stack);    //出栈   printf("出栈的数据是:\n");      printf("%10s%10s\n","姓名","年龄");   printf("%10s%10d\n",popstudent.name,popstudent.age);   SeqStackFree(stack);          //释放栈所用的内存   getchar();   return 0; }

下面是SeqStack.h的代码

代码:

//定义顺序栈的结构 typedef struct stack {   student data[SIZE+1];    //数据元素   int top;              //栈顶 }SeqStack;  //初始化栈 SeqStack * SeqStackInit() {   SeqStack *p;   if (p = (SeqStack *)malloc(sizeof(SeqStack)))         //申请栈内存   {     p->top = 0;     return p;   }   return NULL;             //申请内存失败返回空值 }  //释放栈内存 void SeqStackFree(SeqStack *s) {   if(s)     free(s); }  //判断栈的状态 int SeqStackIsEmpty(SeqStack *s)                 //判断栈是否为空 {   return(s->top == 0); } void SeqStackClear(SeqStack *s)               //清空栈 {   s->top = 0; } void SeqStackIsFull(SeqStack *s)      //判断栈是否已满 {   return(s->top == SIZE); }  //入栈 int SeqStackPush(SeqStack *s, student data)     //入栈操作 {   if ((s->top+1) > SIZE)   {     printf("栈溢出!\n");     return 0;   }   s->data[++s->top] = data;         //将元素入栈   return 1; }  //出栈 student SeqStackPop(SeqStack *s)     //出栈操作 {   if (s->top == 0)   {     printf("栈为空!\n");     exit(0);   }   return (s->data[s->top--]);            //弹出栈顶元素 }  //获取栈顶的元素 student SeqStackPeek(SeqStack *s)          //读取栈顶元素 {   if (s->top == 0)         //判断栈是否为空   {     printf("栈为空!");     exit(0);   }   return (s->data[s->top]);  //返回栈顶元素

}

相关文章

【数据结构】C语言排序方法——快速排序详解!

2021-09-23
其他的数据依次后移.这样将8小的数据移动到8的前面,比8大的数据在8后面保持不变.移动完成后如下:接下来比较的基准变为数字...

静态链表(C语言数据结构)

2021-09-23
静态链表线性存储结构的一种,兼顾顺序表和链表的优点,是顺序表和链表的升级;静态链表的数据全部存储在数组中(顺序表),但...

数据结构之栈(C语言实现)

2021-09-23
什么是栈 栈其实就是一种线性表.只不过它有点特殊,它的特殊性主要体现在它是一种后进先出(Last In First Out)的线性表...栈的基本操作 栈的基本操作只有两个: 入栈(push):即将数据保存在栈顶.进行该操作前,先修改栈顶指针,使其向上移动一个元素位置...两种栈 一般地,栈使用两种存储表示方法. 顺序栈:使用一组连续的内存单元依次保存栈中的数据.一般情况下使用数组作为顺序栈...

C 语言数据结构的封装方法

2021-09-23
本文介绍C语言中如何封装数据结构,让调用者可以引用这个数据结构,但无法获知这个数据结构的内部构成,也无法读写这个数据结...

C语言数据结构之队列

2021-09-23
顺序队列,采用顺序存储,当长度确定时使用. 顺序队列又有两种情况: ①使用数组存储队列的称为静态顺序队列...链式队列,采用链式存储,长度不确定时使用(由链表实现). 由于链式队列跟链表差不多,所以在这里只针对循环(环形)队列来说明并实践...队列的操作 入队(尾部入队) ①将值存入rear所代表的位置. ②rear = (rear+1)%数组的长度...

低价好课:经典数据结构合集(C语言版)(七日成蝶)_CC++开发培训课程百度云高清完整

2021-09-23
经典数据结构合集(C语言版)(七日成蝶)_CC++开发培训课程高清完整百度云网课资源 认准QQ:1679184397 有能...

低价好课:经典数据结构合集(C语言版)(七日成蝶)_CC++开发培训课程百度云高清完整

2021-09-23
经典数据结构合集(C语言版)(七日成蝶)_CC++开发培训课程高清完整百度云网课资源 生活如酒,或芳香,或浓烈它变得醇厚...

严蔚敏《数据结构》(C语言版)精讲班【教材精讲+考研真题串讲】

2021-09-23
官 网 地 址:http://fangcai.100xuexi.com/本文观看地址:http://fangcai.100xuexi.com/Ebook/998852.html内容简介长按上方二维码识别...

C语言 | 什么叫做数据结构

2021-09-23

数据结构与算法(C语言) | 图的基本定义及存储结构

2021-09-23
–线性表中,相邻的数据元素之间具有线性关系,树结构中,相邻两层的结点具有层次关系,而图结构中,任意两个顶点之间都可能有...

随机推荐

市场波动加剧:动量策略参数是否应该更敏感?

2021-09-29
if any(np.isnan(values)): return np.nan vol_point = values.pop(-1) group = 0 # lowest group for comparision in values[1:]: if vol_point

这是什么神仙素材!看了控制不住...【268期】

2021-05-31
高级素材格式:PSD+样式 数量:72个 含使用教程太多了就不一一展示了以上所有的资源均来自于网络教程,只限学习交流,如果侵...

黑马程序员史上最强JavaEE学习路线图震撼发布!!!

2021-05-03
JavaEE 中级程序员学习路线图,共有12大板块,涉及100多个技术,由黑马程序员技术专家和课程研究员精心打造,课程涉及服务中...

手机圈儿冷知识 品牌slogan你都知道吗?

2021-02-28
“Quietly Brilliant”,而这句slogan的官方翻译似乎是“谦和之中见卓越”. 然而随着时代的发展,同样想要在全球市场争得领军位置...

用 Keepalived+HAProxy 实现高可用负载均衡的配置方法

2018-05-20
HAProxy特别适用于那些负载压力大的web站点,这些站点通常需要会话保持或七层处理.HAProxy运行在时下的服务器上,可以支持...

招生咨询 | 新华中学2020年招生现场咨询会欢迎您

2018-04-02
咨询时间:6月25日(本周四)上午8:00—12:00咨询地点:新华大厦一楼(从新华中学南门进入)注意事项1.提前预约:请需要到现场...

Python 最强 IDE 详细使用指南!

2017-09-26
Python IDE,可以帮助程序员节约时间,提高生产效率.那么具体如何使用呢?本文从 PyCharm 安装到插件、外部工具、专业版功能...

【高二】算法的概念和程序框图(视频)

2016-09-22
编辑:王超

数据库密码配置项都不加密?心也太大了!

2016-01-14
(ID:CodeSheep)如若转载请联系原公众号先看一份典型的配置文件... 省略 ...## 配置MySQL数据库连接spring.datasource.driver-class-...

Java 9 怎么就更有才华了?

2015-11-13
继 Java 8 发布三年半之后,Java 9 终于在大家的殷殷期盼下,于 2017 年 9 月 21 日正式发布了 .Java 9 在许多方面带来了非常重大...