数据结构章队列.pptx

大外软件学院(刘)队列

主要内容队列的基本概念顺序队列循环队列链队列

队列的基本概念队列：是插入操作限定在表的尾部，而删除操作限定在表的头部进行的线性表。队尾rear：插入端，线性表的表尾。队头front：删除端，线性表的表头。a1a2a3an-1出队列入队列队头队尾……

a1a2a3……an入队出队frontrear队列Q=(a1,a2,……,an)队列示意图操作原则：先进先出（FirstInFirstOut）,FIFO 后进后出（LastInLastOut）,LILO

顺序队列front指向队列第一个元素之前；rear指向队列最后一个元素自身；初始值均为-1。顺序队列定义

顺序队列为空front==rear为满rear==MAXSIZE-1非空非满-1≤front＜rear＜MAXSIZE-1

顺序队列队列中元素的个数队列中元素的个数（队列的长度）为rear?front。若front=rear，空队，长度为0。若rear?front=MAXSIZE，满队，长度为MAXSIZE。

初始化操作：InitStack()判断栈是否为空：IsEmpty()入栈操作：Push()出栈操作：Pop()显示ShowStack()链栈的基本操作P47

1.顺序队列的初始化#将顺序队列设置为空队设置front和rear等于-1。sequeue*InitQueue(){sequeue*sq=(sequeue*)malloc(sizeof(sequeue));sq-front=-1; sq-rear=-1; returnsq;}

2.顺序队列的入队运算在顺序队列未满的情况下，先使队尾指针rear加1，然后在队尾添加一个新元素。intEnQueue(sequeue*sq，datatypex) { if(sq-rear==MAXSIZE-1) { printf(队列已满!\n); return0;/*入队失败函数返回0*/}else{ sq-rear++;/*将队尾指针加1*/ sq-data[sq-rear]=x;/*数据送给队尾指针*/ return1;/*入队成功函数返回1*/}}

顺序队列的出队操作是指在顺序队不为空的情况下，使队头指针front加1。datatypeDeQueue(sequeue*sq) { if(sq-rear==sq-front){ printf(队列已空,不能执行出队运算!\n); return0;/*出队失败，函数返回0*/}else{ q-front++;/*将队头指针加1*/ /*出队成功，返回队头元素值*/ return(sq-data[sq-front]);}}3.顺序队列出队

4.顺序队列的显示操作#按顺序输出队列中元素，注意空队情况。voidShowQueue(sequeue*sq){ inti; if(sq-rear==sq-front){ printf(队列已空,不能执行出队运算!\n); return; } for(i=sq-front+1;i=sq-rear;i++) printf(%d,sq-data[i]); printf(\n);}

链队列typedefstructnode{ datatypedata; structnode*next;}linkqueue;linkqueue*front，*rear;

4.3链队列1.链队列的初始化运算初始化操作是清除链队列中的结点，使链队列为空。队头指针front等于NULL。voidInitQueue(){//建立头结点front=(structnode*) malloc(sizeof(linkqueue)); /*将头结点的数据域赋值，用-999或H表示表头结点*/ front-data=-999; front-next=NULL; /*将头结点的指针域置空*/ rear=front; /*队尾指针和队头指针相同*/}

4.3链队列2.判链队列是否为空队运算如果链队列的队头指针front等于队尾指针rear，