数结_3队列j.ppt

§3.4 队列(Queue) 3.3.1 队列的定义 队列是一种特殊的线性表; 插入位置只有一个，限制在表的表尾进行； 删除位置也只有一个，限制在表头进行。 队列的基本运算 初始化空队列：InitQueue (Q) 清空队列： ClearQueue (Q) 判队空: QueueEmpty (Q) 求队长： QueueLength (Q) 读队头： GetHead(Q, e) 入队： EnQueue(Q, e) 出队： DeQueue(Q, e) 3.3.2 队列的存储结构 一、链队列 带头结点、头指针和尾指针的单链表： typedef struct QNode { QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front, rear; //队头指针和队尾指针 } LinkQueue; 二、循环队列(Circular Queue) 入队： if ( rear maxsize-1) rear ++; else rear=0; 这个if语句可等价地写成: rear = ( rear+1 ) mod maxsize 出队： if ( front maxsize-1) front ++; else front=0; 这个if语句可等价地写成: front = ( front +1 ) mod maxsize The Summerize of Circular Queue： 队列Q [0 .. maxsize-1] 初态： rear = front = 0 入队： rear = ( rear+1 ) mod maxsize 出队： front = ( front +1 ) mod maxsize 队空条件： front == rear 队满条件： front == (rear+1) mod maxsize 队列长度：(rear – fornt + maxsize) mod maxsize The Summerize of Circular Queue： 队列Q [1 .. maxsize] 初态： rear = front = 1 入队： rear = rear mod maxsize + 1 出队： front = front mod maxsize + 1 队空条件： front == rear 队满条件： front == rear mod maxsize + 1 队列长度：(rear – fornt + maxsize) mod maxsize 第三章作业 对下图所示的链式循环队列，写出入队、出队的算法 。 写出循环队列Q[ 1..maxsize ]在入队时rear指针和出队时front指针的计算公式以及队列长度的计算公式,判断队满队空的条件 写出计算Ack( m, n )的递归算法(公式见55页的式3－3)，并跟踪此算法，求Ack（2，1）的值 A, B, C, D四个元素依次进栈，写出所有可能的出栈序列(n个元素依次进栈，可能的出栈序列有C2nn/(n+1)种) 写出判断括号是否匹配的算法 * * 队头 front 队尾rear 插入 入队 删除 出队 a1 a2 a3 a4 特点：先进先出FIFO(First In First Out) 入队序列 队头端 队尾端 出队序列 队列模型 data next 队元素 front rear 队列 q1 q2 qn ∧ ... Q.front Q.rear 队头元素 队尾元素 ∧ Q.front Q.rear 队空条件： Q.front==Q.rear Q q1 ... 队头元素 队尾元素 Q.front Q.rear q2 qn ∧ 插入端 ` 删除端 qn e s s-next = NULL ∧ Q.rear-next = s Q.rear = s Q.front-next=Q.front-next-next 链队列的操作示意 q1 q2 qn ... 队头元素 队尾元素 rear 瞧，带尾指针的循环链队列也是一