第3章 栈和队列 本章学习要点
1.理解掌握栈和队列的结构特征和操作特点； 2.掌握栈和队列的顺序存储结构和链式存储结构，以及如何用C语言描述它们的类型定义； 3.掌握在两种存储结构下，栈和队列的基本操作的算法；重点掌握顺序存储结构栈的基本操作的算法、循环队列的入队、出队算法，循环队列队空、队满的判别条件； 4.理解栈的后进先出的特点及在程序设计中的应用；理解队列先进先出的特点及在程序设计中的应用；理解递归算法执行过程中栈的作用及栈的状态变化； 栈和队列是两种常用的数据类型，它们是操作受限的线性表—限定插入和删除只能在表的“端点”进行。 线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列的类型定义 3.5 队列类型的实现 3.1 栈 一 什么是栈 栈是限定仅能在表尾一端进行插入、删除操作的线性表。 设（a1, a2, a3, …, an ）是一个栈,则： 1）表尾称为栈顶(top)，表头称为栈底(bottom)，即a1为栈底元素，an为栈顶元素； 2）在表尾插入元素的操作称进栈操作，在表尾删除元素的操作称为出栈操作; 3）第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶, 第一个出栈的元素为栈顶元素； 4）栈的元素具有后进先出的特点,所以栈又称为后进先出表（LIFO表） 5）由于进栈、出栈操作总是在栈顶一端进行，通常设置称为栈顶指针的变量指示栈顶的位置。 二 栈的抽象数据类型定义 出栈
进栈
栈顶 an 栈底 a2 a1 ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{
基本操作： } ADT Stack
数据结构与算法课程数据结构03
