栈和队列1.pptVIP

3．2 队列 3.2.1 队列 3.2.1 队列 3.2.2 队列-------顺序结构 #define MAX 50 /*数据结构定义*/ int queue[MAX]; int front=0; rear=0; int insert_queue(int x) /*入队列*/ {if(rear==MAX)return(0); queue[rear]= x; rear++; return(1); } int del_queue() /*出队列*/ { if(rear==front) return(0); front++;return(queue[front]); } 3. 2.2 队列 3. 2.2 队列 3. 2 队列 3.2 队列 3. 2 队列 3. 2 队列 3. 4 队列 3. 2 队列 3.2 队列 3. 2 队列 3. 2 队列 入列运算 Void addqlink(int x) {NODE *p; p=(NODE *)malloc(sizeof(NODE)); p-data=x; p-next=NULL; rear-next=p; rear=p; } 3. 2 队列 出列运算 NODE *deleqlink( ) { NODE *p; if (front==rear) return(NULL); p=front-next; front-next=p-next; if (p-next==NULL) rear=front; return(p); } 3. 2 队列 3.1 栈 第 * 页 * * 第三章 栈和队列 3.1 栈 3.2 队列 3.2 队列 3.2 .1 队列的概念 3.2 .2 循环队列 ——队列的顺序存储和实现 3.2 .3 队列的链式存储和实现 3.2.1 队列的概念 一 什么是队列 队列 是限定仅能在 表头进行删除， 表尾进行插入的线性表 （a1, a2, ... , ai -1, ai , ai+1, …, an ） 插入 删除 a1 a2 a3 an 入队列 队头 队尾 出队列 队 列 的 示 意 图 队列的特点 先进先出 第一个入队的元素在队头，最后一个入队的元素在队尾， 第一个出队的元素为队头元素， 最后一个出队的元素为队尾元素 1）初始化操作 2）销毁操作 3）置空操作 4）判空操作 5）取队头元素操作 6）入队操作 7）出队操作 二 队列的基本操作 rear front J1 J2 J3 front J3 （a)空队列 (b)J1,J2,J3相继入队列 (c)J1,J2出队 (d)J4,J5和J6相继入队之后,J3出队 rear front 0 1 2 3 4 5 rear front J6 J5 J4 front,rear均为整数 用箭头指示只是为了直观 又有J7入队, 怎么办？ rear 如何解决假溢出问题？ 循环队列 front rear J6 J4 J5 3 1 2 4 0 5 rear 5 4 0 3 1 2 front J6 J7 J8 J9 J4 J5 front rear 5 4 0 3 1 2 (b)队空 (c)队满 队空、队满 都有front=rear 如何判断循环队列 队空、队满？ J7 rear 有两种方法：1）另设一个标志位以区分队空、队满。2）少用一个存储单元，队满条件:front=rear+1; front 5 4 0 3 1 2 J6 J7 J8 J4 J5 （d） rear 环确定位置时：例如 时钟 13 %12 → 取余： （ 位置 ） % 周长 1）初始化操作 功能：建一个空队列Q； 算法： Int queue[MAX]; Int front, rear; int InitQueue_Sq() { //构造一个空队列Q front = 0; rear=0; Return (1)} 二 循环队列的基本操作算法 front rear 5 4 0 3 1 2 建一个空队列Q 6）入队操作 功能：将元素 x 插入队尾 front rear 5 4 0 3 1 2 J1 J3