《数据结构域算法设计-第3章 堆栈与队列(II) 课件》由会员分享,可在线阅读,更多相关《数据结构域算法设计-第3章 堆栈与队列(II) 课件(25页珍藏版)》请在金锄头文库上搜索。
1、第三章 堆栈与队列 (II)西安电子科技大学理学院 Data Structure1Chapter 3: Stack struct QueueNode ElemType data; QueueNode *next; ; struct ListQueue QueueNode *front; QueueNode *rear; int count; ;4frontrearcountData Structure6Chapter 3: Stack struct SqQueue QElemType baseMAXQSIZE; int front, rear; ; void InitQueue(SqQueue
2、 *q) q-front = q-rear = 0; Status QueueFull(SqQueue *q) return (q-rear+1)%MAXQSIZE = q-front); Status QueueEmpty(SqQueue *q) return (q-front = q-rear); int QueueLength(SqQueue *q) return (q-rear - q-front + MAXQSIZE)%MAXQSIZE; Status EnQueue(SqQueue *q, QElemType e) if (QueueFull(q) return FALSE; el
3、se q-baseq-rear = e; q-rear = (q-rear+1)%MAXQSIZE; return TRUE; Status DeQueue(SqQueue *q, QElemType *e) if (QueueEmpty(q) return FALSE; else *e = q-baseq-front; q-front = (q-front+1)%MAXQSIZE; return TRUE; Data Structure15Chapter 3: Stack P(h); Data Structure23Chapter 3: Stack P(q-mutex); QueueNode
4、 *qn = (QueueNode *) malloc(sizeof(QueueNode); qn-m = c; qn-next = NULL; q-count +; if (q-front = NULL) q-front = q-rear = qn; else q-rear-next = qn; q-rear = qn; V(q-mutex); V(q-sem); return 1; int DeQueue(Queue *q, Client *c) P(q-sem); if (q-front = NULL) return 0;P(q-mutex); *c = q-front-m; Queue
5、Node *t = q-front; q-front = q-front-next; q-count -; if (q-count = 0) q-rear = NULL; free(t); V(q-mutex); return 1; void InitQueue(Queue *q) q-front = q-rear = NULL; q-count = 0; q-sem = CreateSemaphore(0, 0, 100, 0); q-mutex = CreateSemaphore(0, 1, 1, 0); Data Structure24Chapter 3: Stack & QueueCl
6、ient: 0 is arrival, wait at queue 2Server2: client 0. Client: 1 is arrival, wait at queue 2 Client: 2 is arrival, wait at queue 0Server0: client 2.Server2: client 0 leaveServer2: client 1. Client: 3 is arrival, wait at queue 2 Client: 4 is arrival, wait at queue 0 Client: 5 is arrival, wait at queue
7、 1Server1: client 5. Client: 6 is arrival, wait at queue 0Server2: client 1 leaveServer2: client 3. Client: 7 is arrival, wait at queue 2 Client: 8 is arrival, wait at queue 1 Client: 9 is arrival, wait at queue 2Server0: client 2 leaveServer0: client 4. Client: 10 is arrival, wait at queue 0Server2
8、: client 3 leaveServer2: client 7. Client: 11 is arrival, wait at queue 0Server1: client 5 leaveServer1: client 8. Client: 12 is arrival, wait at queue 1Server2: client 7 leaveServer2: client 9.Server0: client 4 leaveServer0: client 6. Client: 13 is arrival, wait at queue 2 Client: 14 is arrival, wait at queue 0 Client: 15 is arrival, wait at queue 0 Client: 16 is arrival, wait at queue 1 Client: 17 is arrival, wait at queue 1Data Structure25Chapter 3: Stack & Queue