第3章 栈和队列n2.ppt

如何从后缀式求值？ 先找运算符， 再找操作数 如何解决顺序队列的假溢出问题？ 　　可采取四种方法： 　1)采用循环队列； 2)按最大可能的进队操作次数设置顺序队列的最大元素个数； 3)修改出队算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置； 　４)修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向对头移动，然后方完成入队操作。 顺序循环队列的表示和实现 １、顺序循环队列的基本原理 把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后，再前进一个位置就自动到０。 　　　 附加:顺序循环队列的实现(使用一个计数器) 采用对顺序循环队列的分析，其结构体定义为： typedef struct { DataType queue[MaxQueueSize]; int rear; /*队尾指针*/ int front; /*队头指针*/ int count; /*计数器*/ } SeqCQueue; 编程:栈和队列的应用 a1 ∧ an … Q.front Q.rear Q.front Q.rear ∧ 空队列 typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue; Status InitQueue (LinkQueue Q) { // 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); //存储分配失败 Q.front-next = NULL; return OK; } Status EnQueue (LinkQueue Q, QElemType e) { // 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); //存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; } ∧ rear … front ∧ e ∧ e2 p p Status DeQueue (LinkQueue Q, QElemType e) { // 若队列不空，则删除Q的队头元素， //用 e 返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear == p) Q.rear = Q.front; free (p); return OK; } ∧ front rear y e p p ∧ 循环队列——顺序映象 队列的顺序存储结构： 存储方式：同一般的顺序存储结构完全相同，但是由于在两端操作，设两个指示器（rear和front）分别指示队列的尾和首。 a1 a2 a3 . . . an front rear 空队列：rear=front=0 入队：rear=rear+1 出队：front=front+1 队列空：front=rear 约定：队头指针始终 指向队列头元素，队 尾始终指向队尾元素 的下一个位置 在顺序队列中，当尾指针已经指向了队列的最后一个 位置的下一位置时，若再有元素入队，就会发生“溢出”。 “假溢出”——队列的存储空间未满，却发生了溢出。 rear front J1 J2 J3 J4 rear front J3 J4 顺序队列 a3 a2 a1 front rear 0 1 2 3 . . N-1 a3 a2 a1 0 1 2 3 N