文档介绍：栈
栈的定义及特点
栈的存储及运算
栈的应用
2021/1/15
1
数据结构 栈和队列
栈的定义及特点
栈的定义
限定仅在表尾进行插入或删除操作的线性表
通常将允许进行插入或删除操作的一端称为栈顶(top)，另一端称为栈底(bottom)
不含元素的空表称空栈
特点
先进后出（FILO）
后进先出（LIFO）
2021/1/15
2
数据结构 栈和队列
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
2021/1/15
3
数据结构 栈和队列
栈的存储及运算
栈的顺序存储
栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。
栈的链式存储
2021/1/15
4
数据结构 栈和队列
栈的顺序存储
栈的存储结构
构造空栈
取栈顶元素
元素入栈
元素出栈
判断栈是否为空
2021/1/15
5
数据结构 栈和队列
typedef struct
{ ElemType data[MaxSize]；
int top； /*栈指针*/
} SqStack；
类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。
栈的顺序存储
2021/1/15
6
数据结构 栈和队列
顺序栈进栈和出栈示意图
2021/1/15
7
数据结构 栈和队列
建立一个新的空栈s,实际上是将栈顶指针指向-1即可。对应算法如下:
void InitStack(SqStack *&s)
{
s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1;
}
构造空栈
2021/1/15
8
数据结构 栈和队列
在栈不为空的条件下,将栈顶元素赋给e。对应算法如下:
int GetTop(SqStack *s,ElemType &e)
{
if (s->top==-1) return 0;
/*栈为空的情况,即栈下溢出*/
e=s->data[s->top];
return 1;
}
取栈顶元素
2021/1/15
9
数据结构 栈和队列
(4) 判断栈是否为空StackEmpty(s)
栈S为空的条件是s->top==-1。对应算法如下:
int StackEmpty(SqStack *s)
{
return(s->top==-1);
}
2021/1/15
10
数据结构 栈和队列