第三章线性结构b讲述.ppt

应用背景 栈在人们生活中也有屡见不鲜的事例，只是人们没有给它取名叫栈而已。建筑工地上每堆材料就类似于构造了一个栈，成堆的建筑材料只能从最上往下取出来（下面的压住没法取），而最上面的材料是最后放上去的，最下面的材料是最先放上去的。这种取物规则就与队列不同，它是先进后出。还比如我们有多个人同乘一辆汽车，假设汽车只有一扇门，那么先上车的人坐在最里面，他会最后出来。而最后上车的人坐在靠门的地方，他会最先出去。这也是栈的运算规则。 栈的定义 栈（Stack）是一种特殊的线性表，这种表只允许在一端栈顶(top)(表尾)进行插入和删除元素的操作。 表尾对于栈来说具有特殊的意义，称为栈顶。相应地，表头称为栈底(bottom)。栈的插入操作又叫做进栈或入栈，栈的删除操作又叫做出栈或退栈。 应用背景 现实生活中，处处有特殊线性表的例子。如果你到食堂吃饭，要排队；你要上公共汽车，也要排队，要买体育彩票，还是要排队，……，要排队的情形非常之多。这里排队的规则是按先后顺序，后来的在后面排队，先来的先离开队伍，不能插队，否则别人有意见。排队的规则与队列处理数据元素插入和删除的方法是一致的。在队列中插入数据元素只能在表尾，而删除数据元素只能在表头。在生产建设中也有队列的应用，如生产计划的调度就是一个任务队列。当然，在计算机应用领域同样有队列的应用。比如有多个文件同时输出到打印机，就形成一个打印任务等待队列；又如有多个优先级别相同的中断向CPU发出调用申请，就形成一个资源队列。 循环队列只是顺序队列在处理“假溢出”时的一种特殊处理方式。在链队列中就不存在“溢出”的情形。 第3章 线性结构 把数据插入称为入队列（AddQ）； 而数据删除可看作从队列中取出数据，叫做出队列（DeleteQ）。 最先入队列的数据将被最先弹出，即先来先服务; 所以队列也被称为“先进先出”表（Fist In First Out，简称FIFO） 。 ? 队列的定义 “队列(Queue)” 是具有一定操作约束的线性表，插入和删除操作有一定要求：只能在一端插入，而在另一端删除。 §3.4 队列 类型名称：队列(Queue) 数据对象集：一个有0个或多个元素的有穷线性表。 操作集：对于一个长度为正整数MaxSize的队列Q ? Queue，记队列中的任一元素item ? ElementType。 1、Queue CreatQueue( int MaxSize )：生成长度为MaxSize的空队列。 2、int IsFullQ( Queue Q, int MaxSize )： 判断队列Q是否已满，若是返回1(TRUE)；否则返回0(FALSE)。 3、void AddQ( Queue Q, ElementType item )： 若队列已经满了，返回已满信息；否则将数据元素item插入到队列Q中去。 4、int IsEmptyQ( Queue Q )： 判断队列Q是否为空，若是返回1(TRUE)；否则返回0(FALSE)。 5、ElementType DeleteQ( Queue Q )： 若队列为空信息，返回队列空信息；否则将队头数据元素从队列中删除并返回。 6、 ElementType FrontQ( Queue Q )：…… 18/23 第3章 线性结构 队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。 #define MaxSize 储存数据元素的最大个数 typedef struct { ElementType Data[ MaxSize ]; int rear; int front; } Queue; 1．队列的顺序存储实现 §3.4 队列的实现 Job 3 〖例〗 一个工作队列 AddQ Job 1 AddQ Job 2 AddQ Job 3 DeleteQ Job 1 AddQ Job 4 AddQ Job 5 AddQ Job 6 DeleteQ Job 2 AddQ Job 7 AddQ Job 8 Job 1 Job 2 Rear Job 4 Job 5 Job 6 Front Rear Job 7 0 1 2 3 4 5 6 Rear Rear Front Rear d e f g h Front=2 0 1 2 3 4 5 6 7 rear=8 “假溢出”的情形： queue.rear==maxsize 解决“假溢出”的办法一 [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] AddQ Job 1 AddQ Job 2 AddQ Job 3 Delete