PPT精品文档---栈和队列.ppt

文档介绍：第三章栈和队列
插入和删除操作受限的线性表
栈(stack)
后进先出(LIFO:Last In First Out)的线性表
表头端称为栈底(bottom)
表尾端称为栈顶(top)
插入和删除都在栈顶进行
队列(queue)
先进先出(FIFO:First In First Out)的线性表
表头端称为队头(front)
表尾端称为队尾(rear)
插入在队尾进行,而删除则在队头进行
栈的类型定义和基本操作
栈的基本操作
InitStack(&s)
初始化堆栈
StackEmpty(S)
判断堆栈是否空
Push(S, &e)
将元素e压入堆栈
Pop(s, &e)
弹出栈顶元素
GetTop(s, &e);
读取栈顶元素
栈的存储结构
两种方式
顺序表方式(常用)
链表方式
顺序表方式的堆栈类型定义
#define STACK_SIZE 128
ElemType stack[STACK_SIZE];
int top;
堆栈容量的设计:根据算法需要,分析算法的空间复杂度
堆栈存储空间的动态扩张和缩小
受限的扩张提早发现死循环
编号系统 0~(n-1),top记载下个空位位置,或者说,元素个数
栈满和栈空
顺序表方式的堆栈操作
#define InitStack() top = 0
#define StackEmpty() (top==0)
Status push(elemType e)
{
if (top == STACK_SIZE) return ERROR;
stack[top++] = e;
return OK;
}
顺序表方式的堆栈操作
Status pop(elemType &e)
{
if (top == 0) return ERROR;
e = stack[--top];
return OK;
}
Status GetTop(elemType &e)
{
if (top == 0) return ERROR;
e = stack[top-1];
return OK;
}
栈的链式存储结构以及操作
存储结构设计
不带头的单链表
类型定义
struct NODE {
ElemType data;
struct NODE *next;
};
struct NODE *stack;
操作算法
InitStack
ClearStack: 释放所有节点
其他操作:Push, Pop,GetTop, StackEmpty
栈的应用举例
栈的应用:简单例子