实习二栈及队列的应用.ppt

【实习二实习二】 栈和队列的应用栈和队列的应用 实习二实习二 （1 1）栈的应用）栈的应用 vv【实习题目实习题目】 （1 1）数制转换问题）数制转换问题 （2 2）火烧连营）火烧连营 （3 3）算术表达式求值）算术表达式求值 （2 2）火烧连营）火烧连营 【问题描述问题描述】 “ “火烧连营火烧连营” ”是三国演义中的著名典故之一广为流传，是三国演义中的著名典故之一广为流传， 假定文本文件假定文本文件c1.txtc1.txt是火烧连营中的军营分布图，每个字是火烧连营中的军营分布图，每个字 符符A A代表一个营帐，营帐是可燃物，其他字符代表不可燃代表一个营帐，营帐是可燃物，其他字符代表不可燃 的空白地段，文件共有的空白地段，文件共有4040行行7070列。列。 【基本要求基本要求】 请你编写程序，读入文本文件的内容。提供请你编写程序，读入文本文件的内容。提供MFCMFC界面界面 ，输入任意点的，输入任意点的x x和和y y值（值（xstack 另一个栈另一个栈OPNDOPND：存放操作数；：存放操作数；stackstack vv2 2、运算符之间的优先关系、运算符之间的优先关系 可用二维数组可用二维数组 算符优先顺序算符优先顺序 + + - - * * / / ( ( ) ) # # + + - - * * / / ( ( # # ;case 1:return ; case 2:return B-tAdAtAdA （2 2）A-A-saesae 【测试数据测试数据】 B B(ehnxgz)(ehnxgz)B B将解释成将解释成tsaedsaetsaedsaeezegexeneheezegexenehetsaedsaetsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说若将小写字母与汉字建立下表所示的对应关系，则魔王说 的话是：的话是：“ “天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天 上一只鹅地上一只鹅上一只鹅地上一只鹅” ”。 t t d d s s a a e e z z g g x x n n h h 天天地地上上 一一 只只 鹅鹅追追赶赶下下蛋蛋恨恨 【实现提示实现提示】 将魔王的语言将魔王的语言自右至左进栈自右至左进栈，总是，总是处理栈顶字符处理栈顶字符。若是开。若是开 括号，则逐一出栈，括号，则逐一出栈，将字母顺序入队列将字母顺序入队列，直至括号出栈，并按，直至括号出栈，并按 规则要求逐一出队列再处理后入栈。规则要求逐一出队列再处理后入栈。 3 3、用栈模拟队列、用栈模拟队列 【问题描述问题描述】 请用两个栈请用两个栈s1s1和和s2s2来模拟一个队列。已知栈的三个来模拟一个队列。已知栈的三个 运算定义如下：运算定义如下： Push(S,xPush(S,x) )：元素：元素x x入入S S栈栈; ; PopPop（S S，x x）：）：S S栈顶元素出栈；栈顶元素出栈； S_IsEmptyS_IsEmpty（S S）：判断栈空，）：判断栈空，truetrue为空，为空，falsefalse不为空。不为空。 toptop为栈顶指针为栈顶指针 试用栈的运算实现队列的三个运算：试用栈的运算实现队列的三个运算： （1 1）EnQueueEnQueue：入队列，在队列中插入一个元素；：入队列，在队列中插入一个元素； （2 2）DeQueueDeQueue：出队列，从队列中删除一个元素；：出队列，从队列中删除一个元素； （3 3）Q_IsEmptyQ_IsEmpty：判断队列为空。：判断队列为空。 【实现提示实现提示】利用两个栈模拟一个队列运算的思想：利用两个栈模拟一个队列运算的思想： 用一个栈作为输入，另一个栈作为输出。用一个栈作为输入，另一个栈作为输出。 当进队列时，总是将数据进入到作为输入的栈中；当进队列时，总是将数据进入到作为输入的栈中； 在输出时，如果作为输出的栈已空，则从输入栈将已输入在输出时，如果作为输出的栈已空，则从输入栈将已输入 到输入栈的所有数据输入到输出栈中，然后由输出栈输出数据到输入栈的所有数据输入到输出栈中，然后由输出栈输出数据 ；如果作为输出的栈不空，则从输出栈输出数据。；如果作为输出的栈不空，则从输出栈输出数据。 【题目分析题目分析】栈的特点是后进先出，队列的特点是先进先出。栈的特点是后进先出，队列的特点是先进先出。 所以，用两个栈所以，用两个栈s1s1和和s2s2模拟一个队列时，模拟一个队列时， s1s1作输入栈作输入栈，逐个元素压栈，以此模拟队列元素的入队。，逐个元素压栈，以此模拟队列元素的入队。 当需要出队时，将栈当需要出队时，将栈s1s1退栈并逐个压入栈退栈并逐个压入栈s2s2中，中，s1s1中最先入栈中最先入栈 的元素，在的元素，在s2s2中处于栈顶。中处于栈顶。 s2s2退栈退栈，相当于，相当于队列的出队队列的出队，实现了先进先出。，实现了先进先出。 显然，只有栈显然，只有栈s2s2为空且为空且s1s1也为空，才算是也为空，才算是队列空队列空。 【算法讨论算法讨论】算法中假定栈算法中假定栈s1s1和栈和栈s2s2容量相同。容量相同。 出队出队：从栈：从栈s2s2出，当出，当s2s2为空时，若为空时，若s1s1不空，则将不空，则将s1s1倒入倒入s2s2再出再出 栈。栈。 入队入队：在：在s1s1，当，当s1s1满后，若满后，若s2s2空，则将空，则将s1s1倒入倒入s2s2，之后再入队，之后再入队 。 因此，因此，队列的容量队列的容量为两栈容量之和。为两栈容量之和。 元素从栈元素从栈s1s1倒入倒入s2s2，必须在，必须在s2s2空的情况下才能进行，即在要求空的情况下才能进行，即在要求 出队操作时，若出队操作时，若s2s2空，则不论空，则不论s1s1元素多少（只要不空），就要元素多少（只要不空），就要 全部倒入全部倒入s2s2中。中。 算法思想算法思想 栈栈s1s1和和s2s2，s1s1用作入队，用作入队，s2s2出队出队 1 1、判队满判队满：如果：如果s1s1满且满且s2s2不为空，则队满；不为空，则队满； 2 2、判队空判队空：如果：如果s1s1和和s2s2都为空，则队空；都为空，则队空； 3 3、入队入队：首先判队满，：首先判队满， 若队不满：若队不满：(1)(1)栈栈s1s1若不满，则直接压入栈若不满，则直接压入栈s1s1； (2)(2)若若s1s1满，则将满，则将s1s1中的所有元素弹出到栈中的所有元素弹出到栈s2s2 中，然后再将元素入栈中，然后再将元素入栈s1s1。 4 4、出队出队： (1) (1)若若s2s2空就将空就将s1s1中的所有元素弹出到栈中的所有元素弹出到栈s2s2中，然后出栈中，然后出栈 ； (2)s2(2)s2不空就直接从不空就直接从s2s2中弹出元素。