chapter3：栈、队列

chapter3：栈、队列内容摘要：

现实世界中有许多问题（关系）可用队列描述，顾客服务部门的工作方式往往是排队方式，这类系统称作排队系统。 在计算机算法实现中，也经常使用队列记录需按 FIFO方式处理的数据。 • ────────────── • 出队 ← ○ ○ …… ○ ← ○进队 • ────────────── • 队头 队尾 Queue front rear enqueue dequeue A B C A queue is open at two ends. You can only add entry (enqueue) at the rear , and delete entry (dequeue) at the front. Note that you cannot add/extract entry in the middle of the queue. Firstin Firstout (FIFO) When we enqueue entries in the queue and then dequeue them one by one, we will get the entries in the same order. A B C A A B B C C The first one enqueued is the first one dequeued. (FIFO) 抽象数据类型队列 • ADT Queue{ • 数据对象 : D={ai| ai(ElemSet,i=1,2,...,n,n=0} • 数据关系 : R1={ai1,ai | ai1,ai( D,i=2,...,n} • 基本操作： • InitQueue(amp。 Q) 构造一个空队列 Q • Destroyqueue(amp。 Q) 队列 Q存在则销毁 Q • ClearQueue(amp。 Q) 队列 Q存在则将 Q清为空队列 • QueueEmpty(Q) 队列 Q存在 ,若 Q为空队列则返回 TRUE,否则返回 FALSE • QueueLenght(Q) 队列 Q存在 ,返回 Q的元素个数 ,即队列的长度 • GetHead(Q,amp。 e) Q为非空队列 ,用 e返回 Q的队头元素 • EnQueue(amp。 Q,e) 队列 Q存在 ,插入元素 e为 Q的队尾元素 • DeQueue(amp。 Q,amp。 e) Q为非空队列 ,删除 Q的队头元素 ,并用 e返回其值 • QueueTraverse(Q,vivsit()) Q存在且非空 ,从队头到队尾 ,依次对 Q的每个数据元素调用函数 visit()。 一旦 visit()失败，则操作失败 • }ADT Queue 二、链队列－队列的链式表示和实现 • 用链表表示的队列简称为链队列。 一个链队列显然需要两个分别指示队头和队尾的指针。 LinkedListItr a1 a2 a3 a4 Front of queue Back of queue 链队列表示和实现 • //存储表示 • typedef struct QNode{ • QElemType data。 • struct QNode *next。 • }QNode,*QueuePtr。 • typedef struct{ • QueuePtr front。 • QueuePtr rear。 • }LinkQueue。 • //操作说明 • Status InitQueue(LinkQueue amp。 Q) • //构造一个空队列 Q • Status Destroyqueue(LinkQueue amp。 Q) • //队列 Q存在则销毁 Q • Status ClearQueue(LinkQueue amp。 Q) • //队列 Q存在则将 Q清为空队列 • Status QueueEmpty(LinkQueue Q) • // 队列 Q存在 ,若 Q为空队列则返回 TRUE,否则返回 FALSE • Status QueueLenght(LinkQueue Q) • // 队列 Q存在 ,返回 Q的元素个数 ,即队列的长度 • Status GetHead(LinkQueue Q,QElemType amp。 e) • //Q为非空队列 ,用 e返回 Q的队头元素 • Status EnQueue(LinkQueue amp。 Q,QElemType e) • //队列 Q存在 ,插入元素 e为 Q的队尾元素 • Status DeQueue(LinkQue。