数据结构-栈和队列的.pdfVIP

3.1 栈 3.2 栈的应用举例 3.3 栈与递归 3.4 队列 第 2 页 3.1 栈 3.1.1 栈的概念 一、什么是栈 栈是限定仅能在表尾一端进行插入、删除操作的线性表 （a , a , ... , a , a , a , …, a ） 1 2 i -1 i i+1 n 删除 插入 能进行插入和删除的一端称为栈顶，另一 端称为栈底。 称插入操作为进栈，删除操作为出栈。进 栈出栈操作只能在栈顶进行。 第 3 页 3.1 栈 出栈 进栈 栈的特点 后进先出 栈顶 an 第一个进栈的元素在栈底 最后一个进栈的元素在栈顶 a 2 栈底 a1 第一个出栈的元素为栈顶元素 最后一个出栈的元素为栈底元素 栈的示意图 第 4 页 3.1 栈 二、栈的基本操作 1）初始化操作InitStack(S) 功能：构造一个空栈S。 2 ）销毁栈操作DestroyStack(S) 功能：销毁一个已存在的栈。 3 ）置空栈操作ClearStack(S) 功能：将栈S置为空栈。 4 ）取栈顶元素操作GetTop(S, e) 功能：取栈顶元素，并用e 返回。 第 5 页 3.1 栈 二、栈的基本操作 5 ）进栈操作Push(S, e) 功能：元素e进栈。 6 ）退栈操作Pop(S, e) 功能：栈顶元素退栈，并用e返回。 7 ）判空操作 StackEmpty(S) 功能：若栈S为空，则返回True，否则，栈 不空返回False 。 第 6 页 3.1 栈 3.1.2 栈的顺序存储和实现 一、栈的顺序存储结构 #define STACK_INIT_SIZE 100 // 栈存储空间的初始分配量 #define STACKINCREMENT 10 // 空间的分配增量 typedef struct { ElemType *base; //栈空间基址 ElemType *top; //栈顶指针 int stacksize; //当前分配的栈空间大小 }SqStack;