數據結構（八）——棧

數據結構（八）——棧

一、棧的簡介

棧是一種特殊的線性表，僅能在線性表的一端操作，棧頂允許操作，棧底不允許操作。
棧的特性：后進先出

棧的基本操作包括創建棧、銷毀棧、出棧、入棧、獲取棧頂元素、獲取棧的大小、清空棧。

二、棧的實現

1、棧的抽象類

template <typename T>
  class Stack:public Object
  {
  public:
    virtual void push(const T& value) = 0;//入棧
    virtual void pop() = 0;//出棧
    virtual void clear() = 0;//清空棧
    virtual T top()const = 0;//獲取棧頂元素
    virtual int size()const = 0;//獲取棧的大小
  };

2、棧的順序存儲結構實現

棧可以使用順序存儲結構的內存空間實現，其內存空間分布如下：

根據存儲空間的分配方式可以分為使用原生數組實現的靜態棧和使用動態分配的堆空間實現的動態棧。
靜態棧的實現要點如下：
A、類模板實現
B、使用原生數組作為棧的存儲空間
C、使用模板參數決定棧的容量大小
靜態棧的實現如下：

template<typename T, int N>
  class StaticStack:public Stack<T>
  {
  protected:
    T m_space[N];//棧存儲空間
    int m_top;//棧頂標識
    int m_size;//當前棧的大小
  public:
    StaticStack()//構造函數初始化成員
    {
      m_top = -1;
      m_size = 0;
    }
    int capacity()const//棧的容量
    {
      return N;
    }
    void push(const T& value)//壓棧
    {
      if(m_size < N)
      {
          m_space[m_top + 1] = value;
          m_size++;
          m_top++;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No enough memory...");
      }
    }

    void pop()//出棧
    {
      if(m_size > 0)
      {
          m_top--;
          m_size--;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No element...");
      }
    }

    T top() const//獲取棧頂元素
    {
      if(m_size > 0)
      {
          return m_space[m_top];
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No element...");
      }
    }

    void clear()//清空棧
    {
      m_top = -1;
      m_size = 0;
    }

    int size()const//當前棧的大小
    {
      return m_size;
    }

  };

靜態棧的缺陷：
當存儲的元素類型為類類型時，創建靜態棧時會多次調用元素類型的類構造函數，影響效率。

3、棧的鏈式存儲結構實現

棧使用鏈式存儲結構實現的內容空間分布如下：

鏈式棧的實現要點：
A、類模板實現，繼承自抽象父類Stack
B、內部組合使用LinkList類，實現棧的鏈式存儲
C、只在單鏈表成員對象的頭部進行操作
鏈式棧的實現：

 template <typename T>
  class LinkedStack:public LinkedList<T>
  {
  protected:
    LinkedList<T> m_list;
  public:
    void push(const T& value)//壓棧
    {
        m_list.insert(0, value);
    }
    void pop()//出棧
    {
        if(m_list.length() > 0)
        {
            m_list.remove(0);
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No element...");
        }
    }

    T top()const//獲取棧頂元素
    {
        if(m_list.length() > 0)
        {
            return m_list.get(0);
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No element...");
        }
    }
    void clear()//清空棧
    {
        m_list.clear();
    }
    int size()const//獲取棧大小
    {
        m_list.length();
    }
  };

三、棧的應用

棧具有先進后出的特性，適用于檢測就近匹配的成對出現的符號。
符號匹配問題
從第一個字符開始掃描，遇到普通字符時忽略，遇到左符號時壓入棧，遇到右符號時彈出棧頂元素進行匹配。如果匹配成功，所有字符掃描完畢并且棧為空；如果匹配失敗，所有字符掃描完成但棧非空。

bool isLeft(char c)//左符號
{
  return (c == '(') || (c == '[') || (c == '{') || (c == '<');
}

bool isRight(char c)//右符號
{
  return (c == ')') || (c == ']') || (c == '}') || (c == '>');
}

bool isQuot(char c)//引號、雙引號
{
  return (c == '\'') || (c == '\"');
}

bool isMatch(char left, char right)//是否匹配
{
  return ((left == '(')&&(right == ')')) ||
         ((left == '[')&&(right == ']')) ||
         ((left == '{')&&(right == '}')) ||
         ((left == '<')&&(right == '>')) ||
         ((left == '\'')&&(right == '\'')) ||
         ((left == '\"')&&(right == '\"'));
}

bool parse(const char* code)//解析字符串
{
    LinkedStack<char> stack;
    int i = 0;
    bool ret = true;
    code = (code == NULL)?"":code;
    while(ret && (code[i] != '\0'))
    {
        if(isLeft(code[i]))//左符號
        {
            stack.push(code[i]);//壓棧
        }
        else if(isRight(code[i]))//右符號
        {
            //當前字符是右符號，與棧頂元素匹配
            if((stack.size() > 0) && isMatch(stack.top(), code[i]))
            {
                stack.pop();//彈出
            }
            else
            {
                ret = false;
            }
        }
        else if(isQuot(code[i]))//引號、雙引號
        {
            //棧為空或當前符號與棧頂元素不匹配
            if((stack.size() == 0) || !isMatch(stack.top(), code[i]))
            {
                stack.push(code[i]);//壓棧
            }
            //當前元素與棧頂元素匹配
            else if(isMatch(stack.top(), code[i]))
            {
                stack.pop();//彈棧
            }
        }
        i++;
    }
    return ret && (stack.size() == 0);
}