文章目錄

• • 1 LinkStack的實現
  • • 1.1 StaticStack的缺陷
    • 1.2 鏈式棧的存儲實現
    • 1.3 鏈式棧的設計要點
    • 1.4 繼承關系圖
  • 2 代碼實現
  • 3 棧的應用實踐
  • 4 小結

1 LinkStack的實現

1.1 StaticStack的缺陷

由于StaticStack內部使用了原聲數組，當存儲的元素為類類型時，StaticStack的對象在創建時，會多次調用元素類型的構造函數，影響效率。因此，我們需要鏈式棧來避免這種缺陷。

1.2 鏈式棧的存儲實現

1.3 鏈式棧的設計要點

• 類模板，抽象父類Stack的直接子類。
• 在內部組合使用LinkList類，實現棧的鏈式存儲。
• 只在單鏈表成員對象的頭部進行操作。

1.4 繼承關系圖

---

2 代碼實現

#ifndef LINKSTACK_H #define LINKSTACK_H#include "Stack.h" #include "LinkList.h" #include "Exception.h"namespace LemonLib { template <typename T> class LinkStack : Stack<T> { protected:LinkList<T> m_list;public:void push(const T& e){m_list.insert(0, e);}void pop(){if (m_list.length() > 0){m_list.remove(0);}else{THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");}}T top() const{if (m_list.length() > 0){return m_list.get(0);}else{THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");}}void clear(){m_list.clear();}int size() const{return m_list.length();} }; }#endif // LINKSTACK_H

---

3 棧的應用實踐

符號匹配問題：
在C語言中有一些成對匹配出現的符號：

• 括號：()，[]，{}，<>
• 引號：’’，""

那么我們如何實現編譯器中的符號成對檢測呢？
算法思路：

• 從第一個字符開始掃描

  • 當遇見普通字符時忽略
  • 當遇見左符號時壓入棧中
  • 當遇見右符號時彈出棧頂符號，并進行匹配

• 結束

  • 成功：所有字符掃描完畢，并且棧為空
  • 失敗：匹配失敗或所有字符掃描完畢但棧非空

#include <iostream> #include "LinkStack.h"using namespace std; using namespace LemonLib;bool is_left(char c) {return ((c == '{') || (c == '(') || (c == '[') || (c == '<')); }bool is_right(char c) {return ((c == '}') || (c == ')') || (c == ']') || (c == '>')); }bool is_quote(char c) {return ((c == '\'') || (c == '\"')); }bool is_match(char l, char r) {return ((l == '{') && (r == '}')) ||((l == '(') && (r == ')')) ||((l == '[') && (r == ']')) ||((l == '<') && (r == '>')) ||((l == '\'') && (r == '\'')) ||((l == '\"') && (r == '\"')); }bool scan(const char* str) {bool ret = true;LinkStack<char> stack;int i = 0;str = (str == NULL) ? "" : str;while (ret && (str[i] != '\0')){if (is_left(str[i])){stack.push(str[i]);}else if (is_right(str[i])){if ((stack.size() > 0) && is_match(stack.top(), str[i])){stack.pop();}else{ret = false;}}else if (is_quote(str[i])){if ((stack.size() > 0) && (is_match(stack.top(), str[i]))){stack.pop();}else{stack.push(str[i]);}}i++;}return (ret && (stack.size() == 0)); }int main() {cout << scan("<a{b(\'x\')c}d>") << endl;return 0; }

---

4 小結

• 鏈式棧的實現組合使用了單鏈表對象。
• 在單鏈表的頭部進行操作能夠實現高效的入棧和出棧操作。
• 棧“后近先出”的特性適用于檢測成對出現的符號。
• 棧非常適合于需要“就近匹配”的場合。

總結

以上是生活随笔為你收集整理的LinkStack的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。