1、栈及其实现 2、栈的应用 3、队列及其实现 4、优先级队列 5、链式队列 6、队列应用

Presentation on theme: "1、栈及其实现 2、栈的应用 3、队列及其实现 4、优先级队列 5、链式队列 6、队列应用"— Presentation transcript:

1 1、栈及其实现 2、栈的应用 3、队列及其实现 4、优先级队列 5、链式队列 6、队列应用
六、 栈和队列 1、栈及其实现 2、栈的应用 3、队列及其实现 4、优先级队列 5、链式队列 6、队列应用

2 1、栈及其实现 栈的抽象数据类型 ADT Stack is Data 数据项的列表，并含有栈顶的位置信息。 Operations Constructor // 初始化栈顶 StackEmpty // 检查堆栈为空，空返回True，否则False Pop // 对非空堆栈，返回栈顶元素 Push // 将数据项压入栈顶 Peek // 对非空堆栈，检索栈顶元素的值 ClearStack // 删除堆栈中所有的数据项并重置栈顶 End ADT Stack 栈满的检测要视具体的存储方式而定。

3 类栈的的声明与实现 类Stack定义 class Stack { private： DataType stacklist[MaxStackSize]； // 顺序存储的栈 int top； // 用于栈顶指针 public： Stack(void)； void Push(const DataType& item)； DataType Pop(void); void ClearStack(void); DataType Peek(void) const; int StackEmpty(void) const; // 检测栈为空 int StackFull(void) const; // 用数组实现 }

4 栈的实现 顺序存储的栈 链式栈 top 初始化栈 top
顺序存储的栈 链式栈 top 初始化栈 top Stack∷Stack(void)：top(-1) 利用结点类Node，及其有关操作 {} top = NULL 压栈操作 void Stack ∷Push(const DataType& item) 压栈操作相当于 { InsertFront if (top = = MaxStackSize - 1) { cerr<< “Stack overflow!”<< endl; 出栈操作相当于 exit(1); DeleteFront }; top + +; stacklist[top] = item; } ∧

5 栈的实现(续) 出栈操作 DataType Stack∷Pop(void) { DataType temp; if (top = = -1) cerr<<“Attemp to pop an empty stack!”<< endl; exit(1); }; temp = stacklist[top]; top - -; return temp; }

6 栈的实现(续) 检索栈顶元素 DataType Stack∷Peek(void) const { if (top = = -1) cerr<<“Attemp to peek an empty stack!”<< endl; exit(1); }; return stacklist[top]; }

7 栈的实现(续) 顺序存储的栈 链式栈 栈空函数 int Stack∷StackEmpty(void) const int StackEmpty( ) const { { ruturn top = = -1; return top = = NULL; } } 栈满函数 int Stack∷StackFull(void) const 一般情况下不用考虑。 { return top = = MaxstackSize - 1; } 清空栈 Stack<T> ∷ClearStack ( ) void Stack∷ClearStack (void) { { while( top ! = NULL) top = -1; { p = top; top = top->next; } delete p; }

8 2、栈的应用 表达式的求值 中缀表达式：A＋B ×(C －D) － E÷F 后缀表达式：ABCD － × ＋EF ÷ － 后缀表达式计算表达式的值的思想： 顺序扫描表达式的每一项x，根据x的类型做以下的相应的操作：如果x是操作数，将其压入栈中；如果x是操作符<op>，则连续从栈中退出两各操作数a和b，形成运算指令a <op> b，并将结果再压入栈中。当表达式所有的项扫描后并处理完后，栈顶元素就是最后的计算结果。

9 后缀表达式求值的流程 A B C D － × ＋ E F ÷ － R1 R4 R2 Y R3 R5 N N Y b=Pop(S)
输入x x=<op> b=Pop(S) Push(x/R) 输入结束 a=Pop(S) R=a<op>b Pop(top) 结束

10 关键是按照操作符的优先数确定进栈或出栈。 输入：中缀表达式的序列 输出：后缀表达式的序列 优先数表
中缀表达式转化为后缀表达式 关键是按照操作符的优先数确定进栈或出栈。 输入：中缀表达式的序列 输出：后缀表达式的序列 优先数表 说明：isp(x)是x栈内优先数， icp(x)是x栈外优先数。为保证运算 顺序，当icp小于当前栈顶元素的isp时，就要出栈并输出，否则就 要入栈。其次，为使同一优先级的运算符能确保从左到右的顺序， 在构造优先数表时，采用了同一操作符的isp比icp加1的做法，括 号与分界符例外。 操作符 # ( ^,√ *, / +, － ) isp 1 7 5 3 8 icp 6 4 2

11 中缀表达式转化为后缀表达式流程 流程图 Y N N N Push(#) 读取ch 继续 输入 输出 ch是<op>
icp(ch) ≤isp(top) Push(ch) 输出 结束 icp(ch) ＝isp(top) Pop( ) 出栈

12 3、队列及其实现 队列的抽象数据类型 ADT Queue is Data 数据项列表 front：队列中第一个数据项的位置 rear： 队列中最后一个数据项的位置 count：队列中元素的个数 Operations Constructor // 初始化队头和队尾 Qlength // 返回队列中元素项的个数 QEmpty // 检测队列是否为空 QDelete // 出队列 QInsert // 入队列 QFront // 返回队列头部的元素的值 ClearQueue // 删除队列中全部数据项，并重置初始状态 end ADT Queue

13 类队列的声明与实现 类Queue的定义 class Queue { private: int front, rear, count; DataType qlist[MaxQSize]; public: Queue(void); void QInsert(const DataType& item); DataType QDelete(void); void ClearQueue(void); DataType QFront(void) const; int QLength(void) const; int QEmpty(void) const; int QFull(void) const; }

14 队列的例 顺序队列的操作示意 front rear 队列空 front rear front rear front rear
B C · · · A A B B

15 循环队列 指针移动用求余运算达到“循环”的目的。 B 用 (rear+1)%MaxQSize = = front 判断队列满！ rear
H A A B G B C F rear rear D E A front G B F C D E

16 循环队列的实现 Queue的构造函数 Queue∷Queue(void): front(0), rear(0), count(0) { }
入队列操作 首先要判断队列是否满? Void Queue ∷QueueInsert(const DataType& item) { if ((rear+1)%MaxQSize = = front) // 判断队列是否满 cerr<<“Queue overflow!”<<endl; exit(1); }; count + +; qlist[rear] = item; // 直接从队尾插入数据项 rear = (rear+1)%MaxQSize; // 插入后，修改队尾指针 }

17 循环队列的实现(续) 出队列操作 DataType Queue∷Qdelete(void) { DataType temp; if (rear = = front) // 判断队列是否为空 cerr<<“Deleting from an empty queue!”<<endl; exit(1); }; temp = qlist[front]; count - -; front = (front+1)%MaxQSize; // 修改队头指针 return temp; }

18 与一般队列的区别 ：出队列不是按入队列的先后次序，而是按数 据项本身的优先级，优先级高的先出队列。
4、优先级队列 与一般队列的区别 ：出队列不是按入队列的先后次序，而是按数 据项本身的优先级，优先级高的先出队列。 count count有多重作用：计数器，队尾指针 假定优先级最高的元素是值最小的元素，如 按优先级从高到低，上述任务次序为： 任务#2、任务#5、任务#1、任务#4、任务#3。 若没有新的任务加入，执行的次序(出队列的次序)应为 首先任务#2，其次任务#5、任务#1、任务#4，最后任务#3。 任务#1 20 任务#2 任务#3 40 任务#4 30 任务#5 10

19 优先级队列的声明与实现 优先级队列的抽象数据类型 ADT Priority Queue is Data 元素组成的表 Operations Constructor PQLength // 返回队列中元素的个数 PQEmpty // 检测队列是否为空，空返回True，否则False PQInsert // 元素入队列，元素个数加1 PQDelete // 优先级最高的元素出队列，元素个数减1 ClearPQ // 清空队列，并恢复到初始状态 end ADT Priority Queue

20 优先级队列的实现 PQueue 类的定义 class PQueue { private: int count; DataType pqlist[MaxPQSize]; public: // 构造函数 PQueue(void); // 修改优先级队列的操作 void PQInsert(const DataType& item); DataType PQDelete(void); void ClearPQ(void); // 检测优先级队列状态的操作 int PQEmpty(void) const; int PQFull(void) const; int PQLength(void) const; };

21 void PQueue ∷PQInsert(const DataType& item) {
优先级队列的实现(续) 入队列操作 插入前 插入后 count = count = 5 PQInsert // void PQueue ∷PQInsert(const DataType& item) { if (count = = MaxPQSize) // 队列满，退出 cerr<<“Priority queue overflow!”<<endl; exit(1); }; pqlist[count] = item; // 入队列，计数器加1 count + +; } 20 40 10 30 20 40 10 30 50

22 在队列非空的前提下，遍历队列以确定有最小值(即优先级最高) 的元素，删除之；并用队列尾元素代替这个元素(位置)，最后一 个元素除外。
优先级队列的实现(续) 出队列操作 删除10 删除20 在队列非空的前提下，遍历队列以确定有最小值(即优先级最高) 的元素，删除之；并用队列尾元素代替这个元素(位置)，最后一 个元素除外。 30 40 10 20 50 30 40 50 20 30 40 50 20 30 40 50

23 优先级队列的实现(续) 出优先级队列函数 DataType PQueue∷ PQDelete(void) { DataType min; //将尾元素移入最小元素 int i, minindex = 0; // 处并将count减1 if (count＞0) pqlist[minindex] = { pqlist[count－1]; // 在pqlist中寻找最小值及其下标 count － －; min = pqlist[0]; //假设pqlist[0]最小 } // 遍历队列，修改最小值及下标 // 若pqlist为空，则退出 for (i = 1; i＜count; i + +) else if (pqlist[I] ＜min) { { // 新的最小值及其下标 出错，退出 min = pqlist[i]; }; minindex = i; return min; }; }

24 队列的另一种存储表示是用单链表的方式存储队列元素。
5、链式队列 队列的另一种存储表示是用单链表的方式存储队列元素。 front rear ∧

25 从左到右，把十个队列中得数据元素收集起来，得： 1，2，3，4，5，5，5，6，8，9 对与两位数的数据项，如何处理？
6、队列的应用 基数排序 例：3，9，5，1，2，5，8，5，4，6 尾 头 从左到右，把十个队列中得数据元素收集起来，得： 1，2，3，4，5，5，5，6，8，9 对与两位数的数据项，如何处理？ 1 2 3 4 5 6 8 9

26 按个位数分布到相应队列中的结果如上示意图 30，63，83，84，34，05，78，09，89，69
基数排序的例 例：78，09，63，30，89，84，05，69，34，83 尾 头 按个位数分布到相应队列中的结果如上示意图 30，63，83，84，34，05，78，09，89，69 再收集起来得： 05，09，30，34，63，69，78，83，84，89 30 83 63 34 84 05 78 69 89 09 09 05 34 30 69 63 78 89 84 83

27 作 业 书面题 ▲9.22 ▲已知两个栈S1和S2， Empty (S),Push(S)Pop(S), 用上述条件模拟出队列和入队列操作。
作 业 书面题 ▲9.22 ▲已知两个栈S1和S2， Empty (S),Push(S)Pop(S), 用上述条件模拟出队列和入队列操作。 上机题 ▲ 5.5