數(shù)據(jù)結(jié)構(gòu)（八）——棧

一、棧的簡介

棧是一種特殊的線性表，僅能在線性表的一端操作，棧頂允許操作，棧底不允許操作。
棧的特性：后進(jìn)先出
數(shù)據(jù)結(jié)構(gòu)（八）——棧
棧的基本操作包括創(chuàng)建棧、銷毀棧、出棧、入棧、獲取棧頂元素、獲取棧的大小、清空棧。

成都創(chuàng)新互聯(lián)主要從事網(wǎng)站制作、成都做網(wǎng)站、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)三臺,10余年網(wǎng)站建設(shè)經(jīng)驗(yàn),價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18980820575

二、棧的實(shí)現(xiàn)

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、棧的順序存儲結(jié)構(gòu)實(shí)現(xiàn)

棧可以使用順序存儲結(jié)構(gòu)的內(nèi)存空間實(shí)現(xiàn)，其內(nèi)存空間分布如下：
數(shù)據(jù)結(jié)構(gòu)（八）——棧
根據(jù)存儲空間的分配方式可以分為使用原生數(shù)組實(shí)現(xiàn)的靜態(tài)棧和使用動態(tài)分配的堆空間實(shí)現(xiàn)的動態(tài)棧。
靜態(tài)棧的實(shí)現(xiàn)要點(diǎn)如下：
A、類模板實(shí)現(xiàn)
B、使用原生數(shù)組作為棧的存儲空間
C、使用模板參數(shù)決定棧的容量大小
靜態(tài)棧的實(shí)現(xiàn)如下：

template<typename T, int N>
  class StaticStack:public Stack<T>
  {
  protected:
    T m_space[N];//棧存儲空間
    int m_top;//棧頂標(biāo)識
    int m_size;//當(dāng)前棧的大小
  public:
    StaticStack()//構(gòu)造函數(shù)初始化成員
    {
      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//當(dāng)前棧的大小
    {
      return m_size;
    }

  };

靜態(tài)棧的缺陷：
當(dāng)存儲的元素類型為類類型時，創(chuàng)建靜態(tài)棧時會多次調(diào)用元素類型的類構(gòu)造函數(shù)，影響效率。

3、棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)

棧使用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的內(nèi)容空間分布如下：
數(shù)據(jù)結(jié)構(gòu)（八）——棧
鏈?zhǔn)綏５膶?shí)現(xiàn)要點(diǎn)：
A、類模板實(shí)現(xiàn)，繼承自抽象父類Stack
B、內(nèi)部組合使用LinkList類，實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?br/>C、只在單鏈表成員對象的頭部進(jìn)行操作
鏈?zhǔn)綏５膶?shí)現(xiàn)：

 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();
    }
  };

三、棧的應(yīng)用

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

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]))//右符號
        {
            //當(dāng)前字符是右符號，與棧頂元素匹配
            if((stack.size() > 0) && isMatch(stack.top(), code[i]))
            {
                stack.pop();//彈出
            }
            else
            {
                ret = false;
            }
        }
        else if(isQuot(code[i]))//引號、雙引號
        {
            //棧為空或當(dāng)前符號與棧頂元素不匹配
            if((stack.size() == 0) || !isMatch(stack.top(), code[i]))
            {
                stack.push(code[i]);//壓棧
            }
            //當(dāng)前元素與棧頂元素匹配
            else if(isMatch(stack.top(), code[i]))
            {
                stack.pop();//彈棧
            }
        }
        i++;
    }
    return ret && (stack.size() == 0);
}

網(wǎng)站名稱：數(shù)據(jù)結(jié)構(gòu)（八）——棧
文章出自：http://muchs.cn/article38/jpcesp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、網(wǎng)站導(dǎo)航、服務(wù)器托管、標(biāo)簽優(yōu)化、自適應(yīng)網(wǎng)站、外貿(mào)建站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

數(shù)據(jù)結(jié)構(gòu)（八）——棧