关键词:
小猪的数据结构辅助教程——3.1 栈与队列中的顺序栈
标签(空格分隔): 数据结构
本节学习路线图与学习要点
学习要点
1.栈与队列的介绍。栈顶,栈底,入栈,出栈的概念
2.熟悉顺序栈的特点以及存储结构
3.掌握顺序栈的基本操作的实现逻辑
4.掌握顺序栈的经典样例:进制变换的实现逻辑
1.栈与队列的概念:
嗯,本节要进行解说的就是栈 + 顺序结构 = 顺序栈!
可能大家对栈的概念还是非常模糊。我们找个常见的东西来拟物化~
不知道大家喜欢吃零食不——”桶装薯片“就能够用来演示栈。
生产的时候,往桶里放一片片薯片的过程,能够看成往栈里放元素(进栈),
吃薯片的时候,一片片取出薯片的过程,能够看成取出栈里的元素(出栈)
这里我们如果
我们以下来通过模拟往桶里放入薯片以及取出薯片的流程。来体会下栈的后进先出的特点!
如果薯片桶的容量是5,每次仅仅放或取一块薯片!
放薯片:
…
好的,薯片桶已经装满了!接着等吃货们开吃~
取薯片:
嗯。薯片就这样吃完了~
流程非常easy,如果还是认为不能理解。直接到超市买一桶薯片吧,自己实物
模拟模拟就知道了!又有借口买垃圾食品了~
吃货小贴士:
市面上非常多的桶装薯片都不是马铃薯切片,而是马铃薯粉 + 有用淀粉,而袋装的基本
都是切片,买的时候能够自己看下配料表哦~
2.栈中的名词以及概念解析:
有了上面的桶装薯片的样例,相信再讲栈的一些名词,大家就不会一头雾水了~
入栈(Push):又叫压栈,栈的插入操作;
出栈(Pop):又叫弹栈,栈的删除操作。
我们上面也说了,栈和队列都是操作受限的线性表,操作受限表如今:
我们仅能够在表尾进行插入和删除操作!
而线性表的表头和表尾分别相应的栈底(Bottom)和栈顶(Top)
栈顶始终指向新元素的存放位置!栈底指向表头元素!
另一点:栈在使用过程中所需的最大空间大小非常难预计。所以一般
是先为栈分配一个基本容量,在使用过程中,当栈的空间不够试用再
逐段扩大!名词术语差点儿相同,接下来就到顺序栈的存储结构了!
3.顺序栈的存储结构
typedef struct
{
ElemType *base; //栈底指针,始终指向栈底,如果为null说明栈不存在
ElemType *top; //栈顶指针。当top == base时。为空栈;
int stackSize; //当前已分配的存储空间。以元素为单位
}SqStack;
另外,top - base等于当前栈中的元素个数!
非空栈的栈顶指针始终在栈顶元素的下一个位置上!
4.顺序栈的基本操作的代码实现
代码都非常easy,就只是多的解释了~
1)构造空栈
void InitStack(SqStack S)
{
S ->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S->base)exit(ERROR);
S ->top = S ->base; //栈顶指向栈底
S ->stacksize = STACK_INIT_SIZE;
}
2)将栈置空
void ClearStack(SqStack S)
{
S ->top = S ->base; //栈顶指向栈底
}
3)推断是否为空栈
Status StackEmpty(SqStack S)
{
return S ->top == S ->base?TRUE:FALSE;
}
4)销毁栈
void DestoryStack(SqStack S)
{
free(S ->base); //释放栈空间
S ->top = S ->base = NULL; //将栈顶和栈底设置为NULL
S ->stacksize = 0; //存储空间设置为0
}
5)获得栈中的元素个数
int StackLength(SqStack S)
{
return S ->top - S ->base;
}
6)获得栈顶元素
Status GetTop(SqStack S,SElemType *e)
{
if(S ->top > S ->base)
{
e = S ->top - 1;
return OK;
}else{
return ERROR;
}
}
7)往栈中插入元素(压栈)
void PushStack(SqStack S,SElemType e)
{
//推断当前栈容量是否满了,满了须要添加空间
if(S ->top - S ->base == S ->stacksize)
{
S ->base = (SElemType *)realloc(S ->base,
(S ->stacksize + STACK_INCREMENT)*sizeof(SElemType));
if(!S->base)exit(ERROR);
S ->top = S ->base + S ->stacksize; //改动栈顶指针指向新的栈顶
S ->stacksize += STACK_INCREMENT; //更新容量
}
*(S ->top ++) = e;
}
8)弹出栈中的元素
Status PopStack(SqStack S,SElemType e)
{
if(S ->top == S ->base)return ERROR; //栈为空
e = *(--S ->top); //栈顶元素值付给e,栈顶指针下移
return OK;
}
9)遍历栈中的元素
void StackTraverse(SqStack S,void *visit(SElemType))
{
//从栈底開始到栈顶
while(S ->top > S ->base)
visit(*(S ->base ++));
printf("
");
}
5.顺序栈应用实例:进制转换
进制转换相信大家肯定不会陌生,应该也写过这种程序~
而本节猪脚是栈,所以我们肯定要用栈来解决这个进制转换的问题。
以下我们利用顺序栈来写下十进制转各种进制的简单样例~
执行结果:
代码实现:
#include <stdio.h>
#define STACK_INIT_SIZE 10 //存储空间的初始分配量
#define STACK_INCREMENT 2 //分配增量
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int SElemType;
typedef int Status;
typedef struct SqStack
{
SElemType *base; //栈底指针变量
SElemType *top; //栈顶指针变量
int stacksize; //当前可试用的最大容量
}SqStack;
//初始化栈
void InitStack(SqStack *S)
{
S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if( !S->base )exit(0);
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
}
//获取栈的当前长度
int StackLength(SqStack S)
{
return (S.top - S.base);
}
//入栈
void PushStack(SqStack *S, SElemType e)
{
if(S->top - S->base >= S->stacksize )
{
S->base = (SElemType *)realloc(S->base, (S->stacksize + STACK_INCREMENT) * sizeof(SElemType));
if( !S->base )exit(0);
S->top = S->base + S->stacksize;
S->stacksize = S->stacksize + STACK_INCREMENT;
}
*(S->top) = e;
S->top++;
}
//出栈
void PopStack(SqStack *S, SElemType *e)
{
if(S->top == S->base )return;
*e = *--(S->top);
}
int main()
{
SqStack s;
SElemType n,m,e;
InitStack(&s);
printf("请输入要转换的进制:n >= 0
");
scanf("%d",&n);
printf("请输入要进行转换的十进制数:
");
scanf("%d",&m);
while(m)
{
PushStack(&s,m % n);
m = m / n;
}
printf("输出十进制转%d进制后的值:
",n);
while(StackLength(s))
{
PopStack(&s,&e);
if(n == 16)
{
printf("%X ",e); //输出十六进制的结果
}
else printf("%d ",e);
}
printf("
");
return 0;
}
代码非常easy。无非是求余,然后把求余结果入栈;急着除以进制数,继续求余,直到等于0。
然后是元素出栈~
6.本节实例代码下载:
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/Stack/Stack1.c
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/Stack/Stack2.c
数据结构与算法栈与队列c语言版(代码片段)
目录3.1栈和队列的定义和特点3.2栈、队列与一般线性表的区别3.3栈的表示和操作的实现顺序栈与顺序表=================顺序栈的表示顺序栈初始化判断顺序栈是否为空求顺序栈的... 查看详情
小猪的数据结构辅助教程——1.数据结构与算法绪论
小猪的数据结构辅助教程——1.数据结构与算法绪论标签(空格分隔):数据结构本节学习路线图与学习要点学习要点:1.了解数据结构的相关概念2.了解算法的相关概念3.熟悉时间复杂度的计算4.了解空间复杂度的概念,闰年表... 查看详情
顺序结构栈与队列之货物货架管理
#include<iostream>#include<string.h>usingnamespacestd;staticintn; //货架(栈)的最大容量 //信息结构体typedefstruct/*Inform*/ //可以去掉Inform,在需要在结构体中定义结构体对 查看详情
数据结构系列栈与队列
栈定义栈是一种特殊的线性表 操作 存储结构从存储结构来看,分为顺序栈和链栈,同线性表的划分 应用递归-菲波那切数列后缀表达式-逆波兰表示 队列定义队列也是一种特殊的线性表 操作队列... 查看详情
3.栈与队列
点击使用幕布网页版查看(含思维导图)[栈]点击使用幕布网页版查看(含思维导图)[队列]栈(stack)特点:操作受限的线性表,只允许在一端插入和删除数据,后进先出顺序栈,入栈操作有两种情况:栈空间足够,那么直接入... 查看详情
栈与队列(代码片段)
最近一直在看数据结构与算法,下面是对有线性结构的栈与队列的总结:栈相关的内容定义:栈是限定仅在表尾进行插入和删除操作的线性表。(后进先出的线性表)操作:在可以插入与删除的一端称为栈顶,另外一端称为栈底... 查看详情
数据结构习题--栈与队列(代码片段)
双栈模拟队列基本思路:队列是先进先出,栈是先进后出。用一个输入栈存进队元素,用一个输出栈将输出栈中的元素倒置,再出栈。这就实现了队列的先进先出。注意:队满的条件为输入栈S1满且输出栈S2非空。并非输入栈满... 查看详情
栈与队列
...数据元素,在表头删除数据元素,满足“FirstInFirstOut”。栈与队列的相同点:1.都是线性结构。2.插入操作都是限定在表尾进行。3.都可以通过顺序结构和链式结构实现。、4.插入与删 查看详情
数据结构第八章:栈与队列
一、栈 1、概念 数据的插入和删除都是在同一端,不能在其他任何位置,这种逻辑结构称之为栈。 2、特性 后进先出。或者说先进后出 3、分类 ... 查看详情
栈与队列:栈的顺序储存结构(代码片段)
1.栈的元素必须后进先出2.栈的操作只能在线性表的表尾进行3.对于栈,栈的表尾称为栈顶(top),相应的表头称为栈底(bottom)。栈的插入操作(push)叫进栈,也叫压栈,入栈。栈的删除操作(Pop),叫出栈,也叫弹栈。//栈基... 查看详情
3)数据结构之线性表(栈与队列)(代码片段)
目录栈与队列的本质栈的基本概念栈的物理结构栈的顺序存储结构(用数组实现)静态栈的实现: Stack.h中Test/c中Stack.c中输出结果动态栈的实现 Stac.h中Test.c中Stack.c中栈的链式存储结构(使用链表实现) Stack... 查看详情
栈与队列小结
存在问题:1.对于简单的问题,因为思维惯性,常常更愿意用旧的方法去解决,从而导致无法熟悉站与队列的实现。2.拿到题目时,常常会急着下手,而没有一个十分明确的算法,导致代码看起来思路十分混乱。3.编程习惯不够好... 查看详情
数据结构栈与队列(代码片段)
...码队列概念及结构队列的实现结构的选择相关操作的实现数据结构的定义队列的初始化销毁队列判断队列是否为空入队操作出队操作获取队头元素获取队尾元素获取有效元素个数测试代码获取原码:栈概念及结构一种特殊的... 查看详情
数据结构栈与队列(代码片段)
...码队列概念及结构队列的实现结构的选择相关操作的实现数据结构的定义队列的初始化销毁队列判断队列是否为空入队操作出队操作获取队头元素获取队尾元素获取有效元素个数测试代码获取原码:栈概念及结构一种特殊的... 查看详情
数据结构与算法知识点总结队列栈与散列表
1.队列队列是一种FIFO的数据结构,它有两个出口,限定只能在表的一端进行插入(队尾插入)和在另一端进行删除(队头删除)操作,同样的它也没有遍历行为。由于在队列的顺序存储中无法判断队列满的条件,一般地如果用数组实... 查看详情
栈与队列
栈是一种只能在一端进行插入或者删除操作的线性表,其中允许进行插入或删除的一端称为栈顶。顺序栈typedefstruct{intdata[MaxSize];inttop;}SqStack;对于一个顺序栈st,一共有4个要素,包括两个特殊的状态和两个操作:两个状态栈空状态st... 查看详情
栈与队列
栈是一种只能在一端进行插入或者删除操作的线性表,其中允许进行插入或删除的一端称为栈顶。顺序栈typedefstruct{intdata[MaxSize];inttop;}SqStack;对于一个顺序栈st,一共有4个要素,包括两个特殊的状态和两个操作:两个状态栈空状态st... 查看详情
数据结构学习笔记(特殊的线性表:栈与队列)
栈与队列栈是限定仅在表尾(栈顶)进行插入和删除操作的线性表(后进先出)。队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表(先进先出... 查看详情