栈栈的应用队列优先队列.ppt
《栈栈的应用队列优先队列.ppt》由会员分享,可在线阅读,更多相关《栈栈的应用队列优先队列.ppt(101页珍藏版)》请在三一文库上搜索。
1、栈 栈的应用 队列 优先队列,第四章 栈和队列,a1,a2,a3,a4,a5,a6,栈 ( Stack ),栈和队列 都是特殊的线性表 限定性的线性表 操作受限的线性表,一、栈,限定只在表的一端访问的线性表 元素只能从栈顶插入和删除 先进后出 后进先出 例 羊肉串 子弹夹 货 栈,顺序栈的模型,顺序栈栈类的顺序表示,#ifndef STACK_CLASS #define STACK_CLASS #include #include const int MaxStackSize = 50;,template class Stack, T stacklistMaxStackSize; int top
2、; public: Stack (void); void Push (const T,/ initialize stack top.,template Stack:Stack (void) : top(-1) ,/ push item on the the stack,template void Stack:Push (const T ,/ pop the stack and return the top element,template T Stack:Pop (void) T temp; / if stack is empty, terminate the program if (top
3、= -1) cerr “Attempt to pop an empty stack!“ endl; exit(1); temp = stacklisttop; / record the top element top-; return temp; ,/ return the value at the top of the stack,template T Stack:Peek (void) const / if the stack is empty, terminate the program if (top = -1) cerr “Attempt to peek at an empty st
4、ack!“ endl; exit(1); return stacklisttop; ,/ test for an empty stack,template int Stack:StackEmpty(void) const / return the logical value top = - 1 return top = -1; ,/ test for a full stack,template int Stack:StackFull(void) const / test the position of top return top = MaxStackSize-1; ,/ clear all
5、items from the stack,template void Stack:ClearStack(void) top = -1; #endif / STACK_CLASS,链栈,栈的链式表示,线性链表类的定义,#include “node.h“,template class LinkedList Node *front, *rear, *prevPtr, *currPtr; int size; int position; Node *GetNode(const T,int ListEmpty(void) const; void Reset(int pos = 0); void Next(
6、void); int EndOfList(void) const; int CurrentPosition(void) const; void InsertFront(const T,链栈类的定义,#ifndef STACK_CLASS #define STACK_CLASS #include #include #include “link.h“,template class Stack, LinkedList stackList; public: Stack(void); / constructor void Push(const T,/ constructor,template Stack
7、:Stack(void) ,/ uses the LinkedList method / ClearList to clear the stack,template void Stack:ClearStack(void) stackList.ClearList( ); ,/ use the LinkedList method /InsertFront to push item,template void Stack:Push(const T ,/ use the LinkedList method DeleteFront to pop stack,template T Stack:Pop(vo
8、id) / check for an empty linked list if (stackList.ListEmpty( ) cerr “Popping an empty stack“ endl; exit(1); / delete first node and return its data value return stackList.DeleteFront( ); ,/ returns the data value of the first first item on the stack,template T Stack:Peek(void) / check for an empty
9、linked list if (stackList.ListEmpty( ) cerr “Calling Peek for an empty stack“ endl; exit(1); / reset to the front of linked list and return value stackList.Reset( ); return stackList.Data( ); ,/ use the LinkedList method /ListEmpty to test for empty stack,template int Stack:StackEmpty(void) const re
10、turn stackList.ListEmpty( ); #endif / STACK_CLASS,二、栈的应用,回文验证 数制转换 表达式求值 括号匹配检验 行编辑程序 递归实现,回文验证 palindrome回文的例子,dad madam sees madam im adam a man a plan a canal panama,#include #pragma hdrstop #include “astack.h“ / creates a new string with all blank characters removed void Deblank(char *s, char *t
11、) / loop through expression until NULL character is found while(*s != NULL) / if character is a non-blank, copy to new string if (*s != ) *t+ = *s; s+; / move to next character *t = NULL; / append NULL to new string ,void main(void), const int True = 1, False = 0; Stack S; / stack elements are chara
12、cters char palstring80, deblankstring80, c; int i = 0; int ispalindrome = True; / assume string is a palindrome cin.getline(palstring,80,n); / read in the full-line string / remove blanks from string and put result in deblankstring Deblank(palstring,deblankstring); / push the chars of deblanked expr
13、ession on the stack,i = 0; while(deblankstringi != 0) S.Push(deblankstringi); i+; i = 0; while (!S.StackEmpty( ) c = S.Pop( ); / get next character from stack if (c != deblankstringi) ispalindrome = False; break; i+; ,if (ispalindrome) cout “ palstring “ “ is a palindrome“ endl; else cout “ palstrin
14、g “ “ is not a palindrome“ endl; ,/* madam im adam “madam im adam“ is a palindrome a man a plan a canal panama “a man a plan a canal panama“ is a palindrome palindrome “palindrome“ is not a palindrome */,数制转换 输入十进制数, 以其他进制输出,#include #pragma hdrstop #include “astack.h“ / print integer num in base B,
15、void MultibaseOutput(long num, int B), / stack holds base B digits left to right Stack S; / extract base B digits right to left and push on stack S do S.Push(int(num % B); / convert to int and push on stack num /= B; / remove right most digit while (num != 0); / continue until all digits computed wh
16、ile (!S.StackEmpty( ) / flush the stack cout S.Pop( ); ,void main(void), long num; / decimal number int B; / base / read 3 positive numbers and the desired base 2 num B; cout num “ base “ B “ is “; MultibaseOutput(num, B); cout endl; ,/* Enter non-negative decimal number and base (2=B=9): 72 4 72 ba
17、se 4 is 1020 Enter non-negative decimal number and base (2=B=9): 53 2 53 base 2 is 110101 Enter non-negative decimal number and base (2=B=9): 3553 8 3553 base 8 is 6741 */,表达式求值,中缀表达式 a+b*c a+b*(c-d)+e/f (b*b-4*a*c)/(2*a),后缀表达式 abc*+ abcd-*+ef/+ bb*4a*c*-2a*/,/后缀表达式求值 /calc.h,#include #include #prag
18、ma hdrstop enum Boolean False, True; #include “astack.h“,class Calculator,Stack S; / holds operands void Enter(double num); Boolean GetTwoOperands(double,/ store data value on the stack,void Calculator:Enter(double num) S.Push(num); ,Boolean Calculator:GetTwoOperands( double& opnd1, double& opnd2),
19、if (S.StackEmpty( ) / check for presence of operand cerr “Missing operand!“ endl; return False; opnd1 = S.Pop( ); / fetch right-hand operand if (S.StackEmpty() cerr “Missing operand!“ endl; return False; opnd2 = S.Pop( ); / fetch left-hand operand return True; ,void Calculator:Compute(char op), Bool
20、ean result; double operand1, operand2; result = GetTwoOperands(operand1, operand2); if (result = True) switch(op) case +: S.Push(operand2+operand1); break; case -: S.Push(operand2-operand1); break; case *: S.Push(operand2*operand1); break; case /: if (operand1 = 0.0) cerr “Divide by 0!“ endl; S.Clea
21、rStack( ); else S.Push(operand2/operand1); break; case : S.Push(pow(operand2,operand1); break; else S.ClearStack( ); / error! clear calculator ,Calculator:Calculator(void),void Calculator:Run(void), char c; double newoperand; while(cin c, c != =) / read until = (Quit) switch(c) case +: case -: case
22、*: case /: case : Compute(c); break; default: / not operator, must be operand; put char back cin.putback(c);/ read the operand and store it on the stack cin newoperand; Enter(newoperand);break; if (!S.StackEmpty( ) cout S.Peek( ) endl; ,void Calculator:Clear(void), S.ClearStack( ); ,#include “calc.h
23、“,void main(void) Calculator CALC; CALC.Run( ); ,/* 8 8 * 6 6 * + .5 = 10 3 4 + * Missing operand! 3 4 + 8 * = 56 1 0 / = Divide by 0! */,中缀表达式求值,定义表达式等级 为表达式中每个元素赋一个等级 表达式的累计等级必须为0或1 整个表达式的等级为1,5+3*-6 读到负号时等级累计-1,出错 5+3- 最后等级0,出错,中缀表达式求值法,用两个栈:一个存放操作数 一个存放运算符 2+3-4*5=,定义运算符优先级,icp 栈外优先级 in coming p
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 应用 队列 优先
链接地址:https://www.31doc.com/p-2699080.html