宁夏育才中学第二届NOiP辅导—公共知识
公共基础知识 算 法 与 数 据 结 构 第二讲 学益学区 令莉
目录 Contents
算法
数据结构的基本概念 线性表及其顺序存储结构
栈和队列 线性链表 树与二叉树 查找技术和排序技术
学益学区 令莉 栈 ? 栈和队列的定义
和 队 列 栈和队列是两种特殊的线性表，它们是运算时要受到
某些限制的线性表，故也称为限定性的数据结构。
（1）栈的定义
栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种 结构称为后进先出。设栈s=（a1，a2，…ai，… ，an）,
进栈 出栈 其中a1是栈底元素， an是栈顶元素。
an 栈顶（top)：允许插入和删除的一端； 栈顶 约定top始终指向新数据元素将存放的位置。 …. 栈底（bottom):不允许插入和删除的一端。 a2 栈底 a1 3 学益学区 令莉 栈 和 队 列 ?top=0：栈空 top=m：栈满 ?栈的基本运算
?入栈运算 ?退栈运算 ?读栈顶元素
V(1..10)1098765432bottomtop1(a)空栈bottomtop10987654321FEDCBAbottomtopV(1..10)（2）栈的顺序存储及其运算
V(1..10)10987654321YXFEDCBAbottomtop10987654321V(1..10)XFEDCBA(b)有6个元素的栈(c)插入X和Y后的栈(d)退出Y元素后的栈学益学区 令莉 栈 和 队 列 队列：一种特殊的线性结构，限定只能在表的一端进行插入， 在表的另一端进行删除的线性表 。此种结构称为先进 先出（FIFO）表。
a1 , a2 , a3 , a4 , ………… an-1 , an 队
rear 尾
队front 头队 列 示 意 图 ? 队列的主要运算 （1）设置一个空队列；
（2）插入一个新的队尾元素，称为进队； （3）删除队头元素，称为出队； （4）读取队头元素；
5
学益学区 令莉
信息技术奥赛辅导栈队列线性表(高一高二合上第二部分)
