第三章栈和队列 3.1栈 栈的定义、栈的存储结构、栈的应用。 3.2队列 队列的定义、队列存储结构、队列的应用。 栈和队列的逻辑结构和物理结构,以及它们之 间的相互关系 定义与之相适应的运算 设计相应的算法 分析算法的效率 1
1 第三章 栈和队列 3.1 栈 栈的定义、栈的存储结构、栈的应用。 队列的定义、队列存储结构、队列的应用。 3.2 队列 栈和队列的逻辑结构和物理结构，以及它们之 间的相互关系 定义与之相适应的运算 设计相应的算法 分析算法的效率
3.1栈(堆栈) 3.1.1栈的定义 栈的概念 (stac)是插入和删除操作限定在一端进行的线性表 多栈的逻辑表示为:S=(a1,a2,,an 栈页tp):表中允许进行插入、删除操作的一端。 栈顶的当前位置是动态变化的)的栈顶的当前位 置由一个称为栈顶指针的位置指示器来指示。 栈底 bottom):表的另一固定端非变化的) 多不含元素的栈称为空 2
2 3.1.1 栈的定义 一. 栈的概念 栈(stack)是插入和删除操作限定在一端进行的线性表。 栈的逻辑表示为：S=(a1 ,a2 ,…an ) 栈顶(top) :表中允许进行插入、删除操作的一端。 栈顶的当前位置是动态(变化的)的,栈顶的当前位 置由一个称为栈顶指针的位置指示器来指示。 栈底(bottom):表的另一固定端(非变化的) 不含元素的栈称为空栈. 3.1 栈（堆栈）
3.1栈(堆栈) 3.1.1栈的定义 栈的概念 多栈的运算特性是后进先出( Last in first out--LIFO) 或先进后出( First in last out--FILO 1234 进栈顺序 出栈顺序 栈顶→ 栈底(固定端) 3N
3 3.1.1 栈的定义 一. 栈的概念 栈的运算特性是后进先出(Last In First Out—LIFO) 或先进后出(First In Last Out—FILO) 3.1 栈（堆栈） 栈底(固定端) 1 2 3 4 栈顶 进栈顺序 出栈顺序
3.1栈(堆栈) 31一个栈的输入序列为abcd,则下列序列中不可 能是栈的输出序列的是( A. bcda B dacb C bcad D. adcb 二.栈的基本运算 多初始化线 nitstack③:构造一个空栈s 多销℃ barTack③)释放栈s占用的存储空间。 求的长度 tackling(.返回栈s中的元素个数。 多判断是否为多cEmp③:若栈s为空,则返回真; 否则返回假。 4
4 例3.1 一个栈的输入序列为abcd ，则下列序列中不可 能是栈的输出序列的是( ) 3.1 栈（堆栈） A. bcda B. dacb C. bcad D. adcb 二. 栈的基本运算 初始化栈InitStack(s):构造一个空栈s。 销毁栈ClearStack(s):释放栈s占用的存储空间。 求栈的长度StackLength(s):返回栈s中的元素个数。 判断栈是否为空StackEmpty(s):若栈s为空,则返回真； 否则返回假
3.1栈(堆栈) 二.栈的基本运算 多进Push③):入栈操作,在栈s顶部插入元素e。 多出Pop(e:出栈函数,若s不空,则返回栈顶元 素并将其值赋给e,然后删除该栈顶元素;否则返 回空元素NULL。 多线页元素Geop(s,)返回当前的栈顶元素,并将 其值赋给与Pop(s,e)函数的差别在不删除栈顶元 素 多显示线中元素 isp Stack(s):从栈顶到栈底顺序显示 栈中所有元素
5 进栈Push(s,e):入栈操作，在栈s顶部插入元素e。 出栈Pop(s,e):出栈函数，若s不空，则返回栈顶元 素并将其值赋给e，然后删除该栈顶元素；否则返 回空元素NULL。 取栈顶元素GetTop(s,e):返回当前的栈顶元素,并将 其值赋给e,与Pop(s,e)函数的差别在不删除栈顶元 素。 显示栈中元素DispStack(s):从栈顶到栈底顺序显示 栈中所有元素。 3.1 栈（堆栈） 二. 栈的基本运算