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

一、棧的簡(jiǎn)介

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

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

閬中ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場(chǎng)景，ssl證書未來(lái)市場(chǎng)廣闊！成為創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場(chǎng)價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：028-86922220（備注：SSL證書合作）期待與您的合作！

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

?？梢允褂庙樞虼鎯?chǔ)結(jié)構(gòu)的內(nèi)存空間實(shí)現(xiàn)，其內(nèi)存空間分布如下：

根據(jù)存儲(chǔ)空間的分配方式可以分為使用原生數(shù)組實(shí)現(xiàn)的靜態(tài)棧和使用動(dòng)態(tài)分配的堆空間實(shí)現(xiàn)的動(dòng)態(tài)棧。
靜態(tài)棧的實(shí)現(xiàn)要點(diǎn)如下：
A、類模板實(shí)現(xiàn)
B、使用原生數(shù)組作為棧的存儲(chǔ)空間
C、使用模板參數(shù)決定棧的容量大小
靜態(tài)棧的實(shí)現(xiàn)如下：

template<typename T, int N>
  class StaticStack:public Stack<T>
  {
  protected:
    T m_space[N];//棧存儲(chǔ)空間
    int m_top;//棧頂標(biāo)識(shí)
    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)存儲(chǔ)的元素類型為類類型時(shí)，創(chuàng)建靜態(tài)棧時(shí)會(huì)多次調(diào)用元素類型的類構(gòu)造函數(shù)，影響效率。

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

棧使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的內(nèi)容空間分布如下：

鏈?zhǔn)綏５膶?shí)現(xiàn)要點(diǎn)：
A、類模板實(shí)現(xiàn)，繼承自抽象父類Stack
B、內(nèi)部組合使用LinkList類，實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)
C、只在單鏈表成員對(duì)象的頭部進(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)后出的特性，適用于檢測(cè)就近匹配的成對(duì)出現(xiàn)的符號(hào)。
符號(hào)匹配問(wèn)題
從第一個(gè)字符開(kāi)始掃描，遇到普通字符時(shí)忽略，遇到左符號(hào)時(shí)壓入棧，遇到右符號(hào)時(shí)彈出棧頂元素進(jìn)行匹配。如果匹配成功，所有字符掃描完畢并且棧為空；如果匹配失敗，所有字符掃描完成但棧非空。

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

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

bool isQuot(char c)//引號(hào)、雙引號(hào)
{
  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]))//左符號(hào)
        {
            stack.push(code[i]);//壓棧
        }
        else if(isRight(code[i]))//右符號(hào)
        {
            //當(dāng)前字符是右符號(hào)，與棧頂元素匹配
            if((stack.size() > 0) && isMatch(stack.top(), code[i]))
            {
                stack.pop();//彈出
            }
            else
            {
                ret = false;
            }
        }
        else if(isQuot(code[i]))//引號(hào)、雙引號(hào)
        {
            //棧為空或當(dāng)前符號(hào)與棧頂元素不匹配
            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ù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享文章：數(shù)據(jù)結(jié)構(gòu)（八）——棧-創(chuàng)新互聯(lián)
當(dāng)前URL：http://www.rwnh.cn/article38/doposp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、網(wǎng)站改版、響應(yīng)式網(wǎng)站、微信公眾號(hào)、云服務(wù)器、軟件開(kāi)發(fā)

廣告

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