【正文】 b 進棧 a a b a b c d e e 進棧 a b c d e f 進棧溢出 a b d e e 退棧 c 四川大學計算機學院，主講教師：游洪躍 top c 退棧 b 退棧 a b a a 退棧 空 棧 top a b d d 退棧 c top a b c top top 四川大學計算機學院，主講教師：游洪躍 雙棧共享一個棧空間 b[0] t[0] t[1] b[1] 0 maxSize1 V 四川大學計算機學院，主講教師：游洪躍 棧的鏈接表示 — 鏈式棧 ? 鏈式棧無棧滿問題，空間可擴充 ? 插入與刪除僅在棧頂處執(zhí)行 ? 鏈式棧的棧頂在鏈頭 top 四川大學計算機學院，主講教師：游洪躍 鏈式棧 (Linked Stack) 類的定義 四川大學計算機學院，主講教師：游洪躍 // 鏈棧類 templateclass ElemType class LinkStack { protected: // 鏈棧實現(xiàn)的數(shù)據(jù)成員 : NodeElemType *top。 // 棧頂指針 // 輔助函數(shù) void Init()。 // 初始化棧 public: // 抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認方法聲明 : LinkStack()。 // 無參數(shù)的構(gòu)造函數(shù) virtual ~LinkStack()。 // 析構(gòu)函數(shù) int Length() const。 // 求棧長度 四川大學計算機學院，主講教師：游洪躍 bool Empty() const。 // 判斷棧是否為空 void Clear()。 // 將棧清空 void Traverse(void (*Visit)(const ElemType amp。)) const。 // 遍歷棧 StatusCode Push(const ElemType amp。e)。 // 入棧 StatusCode Top(ElemType amp。e) const。 // 返回棧頂元素 StatusCode Pop(ElemType amp。e)。 // 出棧 LinkStack(const LinkStackElemType amp。copy)。 // 復制構(gòu)造函數(shù) LinkStackElemType amp。operator =(const LinkStackElemType amp。copy)。 //重載賦值 }。 四川大學計算機學院，主講教師：游洪躍 templateclass ElemType LinkStackElemType::LinkStack() // 操作結(jié)果：構(gòu)造一個空棧表 { Init()。 } templateclass ElemType LinkStackElemType::~LinkStack() // 操作結(jié)果：銷毀棧 { Clear()。 } 四川大學計算機學院，主講教師：游洪躍 templateclass ElemType StatusCode LinkStackElemType::Push( const ElemType amp。e) // 操作結(jié)果：將元素 e追加到棧頂 ,如成功則返加 SUCCESS, // 否則如動態(tài)內(nèi)存已耗盡將返回 OVER_FLOW { NodeElemType *new_top = new NodeElemType(e, top)。 if (new_top == NULL) { // 動態(tài)內(nèi)存耗盡 return OVER_FLOW。 } else { // 操作成功 top = new_top。 return SUCCESS。 } } 四川大學計算機學院，主講教師：游洪躍 templateclass ElemType StatusCode LinkStackElemType::Pop(ElemType amp。e) // 操作結(jié)果：如棧非空 ,刪除棧頂元素 ,并用 e返回棧頂元素 , // 函數(shù)返回 SUCCESS,否則函數(shù)返回 UNDER_FLOW { if (Empty()) { // ?？? return UNDER_FLOW。 } else { // 操作成功 NodeElemType *old_top = top。 // 舊棧頂 e = old_topdata。 // 用 e返回棧頂元素 top = old_topnext。 // top指向新棧頂 delete old_top。 // 刪除舊棧頂 return SUCCESS。 } } 四川大學計算機學院，主講教師：游洪躍 templateclass ElemType StatusCode LinkStackElemType::Top(ElemType amp。e) const // 操作結(jié)果：如棧非空 ,用 e返回棧頂元素 ,函數(shù)返回 \ // SUCCESS,否則函數(shù)返回 UNDER_FLOW { if(Empty()) { // ?？? return UNDER_FLOW。 } else { // 棧非空 ,操作成功 e = topdata。 // 用 e返回棧頂元素 return SUCCESS。 } } 四川大學計算機學院，主講教師：游洪躍 template class ElemType void LinkStackElemType::Traverse(void (*Visit)( const ElemType amp。)) const // 操作結(jié)果：從棧底到棧頂依次對棧的每個元素調(diào)用函 // 數(shù) (*visit) { NodeElemType *tmpPtr。 LinkStackElemType tmpS。 // 臨時棧 for (tmpPtr = top。 tmpPtr != NULL。 tmpPtr = tmpPtrnext) { // 用 tmpPtr依次指向當前棧的每個元素 (tmpPtrdata)。 // 每個元素入棧 } for (tmpPtr = 。 tmpPtr != NULL。 tmpPtr = tmpPtrnext) { // 從棧頂?shù)綏５滓来沃赶驐?tmpS的每個元素 (*Visit)(tmpPtrdata)。 } } 四川大學計算機學院，主講教師：游洪躍 表達式求值 ? 一個表達式由 操作數(shù) (亦稱運算對象 )、 操作符 (亦稱運算符 ) 和 分界符 組成 。 ? 算術(shù)表達式有三種表示： ? 中綴 (infix)表示 操作數(shù) 操作符 操作數(shù) ， 如 A+B； ? 前綴 (prefix)表示 操作符 操作數(shù) 操作數(shù) ， 如 +AB； ? 后綴 (postfix)表示 操作數(shù) 操作數(shù) 操作符 ， 如 AB+； 四川大學計算機學院，主講教師：游洪躍 表達式的中綴表示 ? 表達式中相鄰兩個操作符的計算次序為： ? 優(yōu)先級高的先計算 ； ? 優(yōu)先級相同的自左向右計算 ； ? 當使用括號時從最內(nèi)層括號開始計算 。 四川大學計算機學院，主講教師：游洪躍 C++中操作符的優(yōu)先級 優(yōu)先級 操作符 1 單目 + 、 、！ 2 *、 /、 % 3 +、 4 、 =、 、 = 5 ==、 != 6 amp。amp。 7 || 四川大學計算機學院，主講教師：游洪躍 ? 一般表達式的操作符有 4種類型 ： 1 算術(shù)操作符 如雙目操作符（ +、 、 *、/ 和 %）以及單目操作符（ +、 ）。 2 關(guān)系操作符 包括 、 =、 ==、 !=、 =、。這些操作符主要用于比較。 3 邏輯操作符 如與 (amp。amp。)、或 (||)、非 (!)。 4 括號‘ (‘和‘ )‘ 它們的作用是改變運算順序。 四川大學計算機學院，主講教師：游洪躍 中綴表達式中各個算術(shù)操作符的優(yōu)先級 ? isp叫做棧內(nèi) (in stack priority)優(yōu)先數(shù) ? icp叫做棧外 (in ing priority)優(yōu)先數(shù) 。 ? 操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在 括號配對 或 棧底的 ‘ =‘號與輸入流最后的 ‘ =‘號配對 時 。 ? 上面討論的 +、 為雙目運算符 ， 如為單目運算符 ，編程實現(xiàn)時 ， 可在前面加上 0而轉(zhuǎn)化為雙目運算符 。 ? 如在 +、 的前一個字符 (跳過空格 ,當前一個字符不是運算符時用 ‘ 0‘表示 )為 ‘ =‘或 ‘ (‘， 則為單目運算符 。 操作符 ch = ( ^ *, /, % +, )is p ( 棧內(nèi) ) 0 1 7 5 3 8icp ( 棧外 ) 0 8 6 4 2 1中綴算術(shù)表達式求值 四川大學計算機學院，主講教師：游洪躍 中綴算術(shù)表達式求值 ? 使用兩個棧 ， 操作符棧 OPTR (operator)，操作數(shù)棧 OPND(operand)， ? 對中綴表達式求值的一般規(guī)則： (1) 在 OPTR棧中壓入一個 ‘ =‘ 。 (2) 從輸入流獲取一字符 ch。 (3)取出 OPTR的棧頂 OPTR_top 。 (4) 當 OPTR_top!=?=‘或 ch != ?=‘ 時 , 循環(huán)執(zhí)行以下工作 , 否則結(jié)束算法 。 此時在 OPND棧 的棧頂?shù)玫竭\算結(jié)果 。 四川大學計算機學院，主講教師：游洪躍 while(OPTR_top!=?=‘ ||ch != ?=‘ ){ ① 若 ch不 是 操作符 ， 則 將字符放回輸入流 ()，讀操作數(shù) newoperand并進 OPND棧 ， 并讀入下一字符送入 ch； ② 若 ch是 操作符 ， 比較 icp(ch)的優(yōu)先級和 isp(OPTR_top)的優(yōu)先級： ? 若 isp(OPTR _top)icp(ch)， 則 ch進 OPTR棧 ， 從中綴表達式取下一字符送入 ch； ? 若 isp(OPTR _top)icp(ch)， 則從 OPND棧 退出 a2和 a1，從 OPTR棧 退出 θ, 形成運算指令 (a1)θ(a2)， 結(jié)果進OPND棧 ； ? 若 isp(OPTR _top)==icp(ch)且 ch == ―)‖， 則從 OPTR棧 退出棧頂?shù)?“ (‖， 對消括號 ， 然后從中綴表達式取下一字符送入 ch 。 ③ 取出 OPTR的棧頂 OPTR_top。 } 四川大學計算機學院，主講教師：游洪躍 隊列 四川大學計算機學院，主講教師：游洪躍 隊列 ( Queue ) 定義 ?隊列是只允許在一端刪除，在另一端插入的順序表 ?允許刪除的一端叫做隊頭 (front)，允許插入的一端叫做隊尾 (rear)。 特性 ?先進先出 (FIFO, First In First Out) a1 a2 a3 an front rear ?? 四川大學計算機學院，主講教師：游洪躍 1． int Length() const 初始條件：隊列已存在。 操作結(jié)果：返回隊列長度 2． bool Empty() const 初始條件：隊列已存在。 操作結(jié)果：如隊列為空，則返回 true，否則返回 false 3． void Clear() 初始條件：隊列已存在。 操作結(jié)果：清空隊列 四川大學計算機學院，主講教師：游洪躍 4． void Traverse(void (*Visit)(const ElemType amp。)) const 初始條件：隊列已存在。 操作結(jié)果：依次對隊列的每個元素調(diào)用函數(shù) (*visit) 5． StatusCode OutQueue(ElemType amp。e) 初始條件：隊列非空。 操作結(jié)果：刪除隊頭元素，并用 e返回其值。 a1 a2 an … … 四川大學計算機學院，主講教師：游洪躍 6． StatusCode GetHead(E