关键词:
栈是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表,简称LIFO结构。
栈的插入操作,叫作进栈,也称压栈、入栈。
栈的删除操作,叫作出栈,也有的叫作弹栈。
栈的抽象数据类型
ADT 栈(stack) Data 同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。 Operation InitStack(*S): 初始化操作,建立一个空栈S。 DestroyStack(*S): 若栈存在,则销毁它。 ClearStack(*S): 将栈清空。 StackEmpty(S): 若栈为空,返回True,否则返回False。 GetTop(S,*e): 若栈存在且非空,用e返回S的栈顶元素。 Push(*S,e): 若栈S存在,插入新元素e到栈S中并成为栈顶元素。 Pop(*S,*e): 删除栈S中栈顶元素,并用e返回其值。 StackLength(S): 返回栈S的元素个数。 endADT
栈的顺序存储结构:以首元素作为栈底。两栈共享空间可以提高空间利用率。
栈的链式存储结构:把栈顶放在单链表的头部,用栈顶作为头结点。
如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一点。
栈的应用——递归
我们把一个直接调用自己或通过一些列的调用语句间接地调用自己的函数,称为递归函数。
每个递归函数定义必须至少有一个条件,满足时递归不再进行,即不再引用自身而是返回值输出。(避免无穷递归)
例子:斐波拉契数列。
栈的应用——四则运算表达式求值
1)将中缀表达式转化为后缀表达式(栈用来进出运算的符号);
规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级不高于栈顶符号则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。
2)将后缀表达式进行运算得出结果(栈用来进出运算的数字)。
规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。
大话数据结构4之栈与队列
1. 栈是限定仅在表尾进行插入和删除操作的线性表。 队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。2.我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈... 查看详情
数据结构之栈与队列(代码片段)
...列 栈与队列是程序设计中广泛使用的两种重要的线性数据结构。 栈是LIFO(LastInFirstOut),先存进去的数据只能最后被取出来,进出顺序逆序,即先进后出,后进先出。 队列是FIFO(FirstInFirstOut... 查看详情
数据结构栈与队列的实现(代码片段)
基础结构typedefintSTDataType;typedefstructStackSTDataType*_a;inttop;//栈顶intcapacity;//容量Stack;申请空间voidListCapacity(Stack*ps)if(ps->top==ps->capacity)intnewcapacity=ps->capacity 查看详情
栈与队列(代码片段)
最近一直在看数据结构与算法,下面是对有线性结构的栈与队列的总结:栈相关的内容定义:栈是限定仅在表尾进行插入和删除操作的线性表。(后进先出的线性表)操作:在可以插入与删除的一端称为栈顶,另外一端称为栈底... 查看详情
栈与队列专题(代码片段)
1.定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。 方法:1.使用两个栈stackData,stackMin,一个记录数据,另一个栈确保栈顶是当前数据栈的最小元素 2.入栈:若stackMin空,则直接入,否则如... 查看详情
数据结构习题--栈与队列(代码片段)
双栈模拟队列基本思路:队列是先进先出,栈是先进后出。用一个输入栈存进队元素,用一个输出栈将输出栈中的元素倒置,再出栈。这就实现了队列的先进先出。注意:队满的条件为输入栈S1满且输出栈S2非空。并非输入栈满... 查看详情
3)数据结构之线性表(栈与队列)(代码片段)
目录栈与队列的本质栈的基本概念栈的物理结构栈的顺序存储结构(用数组实现)静态栈的实现: Stack.h中Test/c中Stack.c中输出结果动态栈的实现 Stac.h中Test.c中Stack.c中栈的链式存储结构(使用链表实现) Stack... 查看详情
数据结构与算法栈与队列c语言版(代码片段)
目录3.1栈和队列的定义和特点3.2栈、队列与一般线性表的区别3.3栈的表示和操作的实现顺序栈与顺序表=================顺序栈的表示顺序栈初始化判断顺序栈是否为空求顺序栈的... 查看详情
单调栈与队列的概念与练习!建议收藏(代码片段)
本期文章,小编给大家介绍一下数据结构中很重要的两个角色,那就是栈与队列两兄弟。文中若有欠妥之处,还望指正!感谢!文章目录一、栈与队列的概念1、栈2、队列二、栈的运用题目:逆波兰表达式... 查看详情
sdut2449数据结构实验之栈与队列十:走迷宫(代码片段)
数据结构实验之栈与队列十:走迷宫TimeLimit: 1000ms MemoryLimit: 65536KiBProblemDescription一个由n*m个格子组成的迷宫,起点是(1,1),终点是(n,m),每次可以向上下左右四个方向任意走一步,并且有些格子是不能走动,求从... 查看详情
sdut-2131_数据结构实验之栈与队列一:进制转换(代码片段)
...要求,栈和队列这一章我会用线性和非线性两种方式写。数据结构实验之栈与队列一:进制转换TimeLimit:1000msMemoryLimit:65536KiBProblemDescription输入一个十进制非负整数,将其转换成对应的R(2<=R<=9)进制数,并输出。Input第一行输入... 查看详情
javascript实现栈与队列的操作(代码片段)
目录栈队列栈栈是一种非常常见的数据结构,在程序中应用广泛。我们知道数组是一种线性结构虽然麻烦,但可以在数组的任意位置插入和删除数据。但为了实现某些功能,必须对这种任意性加以限制,而栈和队... 查看详情
sdut3332数据结构实验之栈与队列五:下一较大值(代码片段)
数据结构实验之栈与队列五:下一较大值(一)TimeLimit: 1000ms MemoryLimit: 65536KiBProblemDescription对于包含n(1<=n<=1000)个整数的序列,对于序列中的每一元素,在序列中查找其位置之后第一个大于它的值,如果找... 查看详情
重学数据结构栈与队列(代码片段)
...是浮动的。堆这个存储区存入的数据,是一种特殊的数据结构。所有的数据存入或取出,只能在浮动的一端(称栈顶 查看详情
sdut-2449_数据结构实验之栈与队列十:走迷宫(代码片段)
数据结构实验之栈与队列十:走迷宫TimeLimit:1000msMemoryLimit:65536KiBProblemDescription一个由n*m个格子组成的迷宫,起点是(1,1),终点是(n,m),每次可以向上下左右四个方向任意走一步,并且有些格子是不能走动,求从起点到终点经过每... 查看详情
顺序表栈与队列(代码片段)
一、顺序表引入1什么是线性表1在程序中,经常需要将一组数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等。2一组数据中包含的元素个数可能发生变化(增加或删除元素)。3对于这种需... 查看详情
数据结构栈与队列---栈的应用(递归和分治思想)(代码片段)
(一)递归定义我们把一个直接调用自己活着通过一系列的调用语句间接的调用自己的函数,称做递归函数。一般,若是我们知道循环的次数,就不要使用递归,使用迭代同样可以实现。而且递归效率太低。使用不多。另外:递... 查看详情
第四章栈与队列2(对列)(代码片段)
4.2队列4.2.1队列的定义队列简称队,它通栈一样,也是一种运算受限的线性表,其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。在队列中把插入数据元素的一端称为队尾(rear),删除元素的一端称为队首(front)。向... 查看详情