數據結構(06)_棧

1.棧的設計和實現

1.1.棧的概念

概念：棧是一種特殊的線性表，僅能在線性表的一端（棧頂）進行操作。
棧的特性：后進先出（last in first out）

棧的基本操作：
創建棧（stack()）; 銷毀棧（~stack()）; 清空棧（clear()）
進棧（push()）; 出棧（pop()）;
獲取棧頂元素（top()）; 獲取棧的大小（size()）

1.2.棧的實現

棧的繼承關系：

棧的聲明：(接口)

template < typename T >
class stack : public Object
{
Public:
    virtual void push(const T& e) = 0;
    virtule void pop() = 0;
    virtual T top() const = 0;
    virtual void clear() = 0;
    virtual int size() const = 0; 
};

1.3.StaticStack

棧的順序實現,(棧是一種特殊的線性表)。

設計要點：
類模板，使用原生數組作為棧的存儲空間，使用模板參數決定棧的最大容量

template < typename T, int N>
class StaticStack : public stack<T>
{
protected:
    T m_space[N];
    int m_size;
    int m_top;
public:
    StaticStack()
    int capacity() const
    void push(const T& e)
    void pop()
    T top() const
    int size() const
    void clear()
};

順序存儲結構棧最終實現：

template < typename T, int N >
class StaticStack : public Stack<T>
{
protected:
    T m_space[N];
    int m_size;
    int m_top;
public:
    StaticStack()   //O(1)
    {
        m_top = -1;
        m_size = 0;
    }

    void push(const T& e)   //O(1)
    {
        if(m_size < N)
        {
            m_space[m_top + 1] = e; //為了異常安全
            m_size++;
            m_top++;
        }
        else
        {
            THROW_EXCEPTION(InvaildParemeterException, "no space in current stack...");
        }
    }

    void pop()      //O(1)
    {
        if(m_size > 0)
        {
            m_size--;
            m_top--;
        }
        else
        {
            THROW_EXCEPTION(InvaildParemeterException, "no element in current stack...");
        }
    }

    T top() const   //O(1)
    {
        if(m_size > 0)
        {
            return m_space[m_top];
        }
        else
        {
            THROW_EXCEPTION(InvaildParemeterException, "no element in current stack...");
        }
    }

    int size() const    //O(1)
    {
        return m_size;
    }

    int capacity() const    //O(1)
    {
        return N;
    }

    void clear()    //O(1)
    {
        m_size = 0;
        m_top = -1;
    }
};

順序存儲結構棧的優勢：所有操作的時間復雜度都為常量O(1)

2.LinkStack

順序棧的缺陷：當存儲元素為類類型時，StaticStack的對象在創建時，會多次調用元素類型的構造函數，影響效率。
為了解決這個問題，我們使用鏈式存儲結構來實現棧。

2.1.設計要點

1.類模板，繼承自抽象父類Stack;
2.在內部組合使用LinkList類，實現棧的鏈式存儲；
3.在當鏈表成員對象的頭部進行操作。

鏈式存儲結構棧的聲明：

template <typename T>
class LinkStack: public Stack<T>
{
protected:
    LinkList<T> m_list;
public:
    void push(const T& e)
    void pop()
    T top() const
    void clear()
    int size() const
};

鏈式存儲結構棧的最終實現：

template < typename T >
class LinkStack : public Stack<T>
{
protected:
    LinkList<T> m_list;
public:
    void push(const T& e)   // 頭插法 O(1)
    {
        m_list.insert(0, e);
    }

    void pop()      //O(1)
    {
        if(m_list.length() > 0)
        {
            m_list.remove(0);
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "no elememt in current linkstack...");
        }
    }

    T top() const   ///O(1)
    {
        if(m_list.length() > 0)
        {
            return m_list.get(0);
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "no elememt in current linkstack...");
        }
    }

    int size() const    //O(1)
    {
        return m_list.length();
    }

    void clear()    //O(n)
    {
        m_list.clear();
    }
};

2.2.棧的應用

符號匹配問題：
在C語言中有一些成對匹配出現的符號，(), {}, [], <>, ‘’, “”，如何實現編譯器中的符號成對檢測？
算法思路：
1.從一個字符開始掃描，當遇見普通字符時忽略，當遇見左符號時入棧，當遇見有符號時彈出棧頂符號，進行匹配。
2.當所有字符掃描完成，且棧為空則成功；匹配失敗或最終棧非空則失敗。
算法實現：

#include <iostream>
#include "Exception.h"
#include "LinkStack.h"

using namespace std;
using namespace DTLib;

bool is_left(char c)
{
    return (c == '(') || (c == '{') || (c == '<') || (c == '[');
}

bool is_right(char c)
{
    return (c == ')') || (c == '}') || (c == '>') || (c == ']');
}

bool is_quot(char c)
{
    return (c == '\'') || (c == '\"');
}

bool is_mathch(char l, char r)
{
    return ((l=='(') && (r==')')) ||
           ((l=='<') && (r=='>')) ||
           ((l=='{') && (r=='}')) ||
           ((l=='[') && (r==']')) ||
           ((l=='\'') && (r=='\'')) ||
           ((l=='\"') && (r=='\"'));
}

bool scan(const char* code)
{
    LinkStack<char> ls;
    int i = 0;
    bool ret = true;
    code = ((code == NULL) ? "" : code);

    while(ret && (code[i] != '\0'))
    {
        if(is_left(code[i]))
        {
            ls.push(code[i]);
        }
        else if(is_right(code[i]))
        {
            if((ls.size() > 0) && is_mathch(ls.top(), code[i]))
            {
                ls.pop();
            }
            else
            {
                ret = false;
            }
        }
        else if(is_quot(code[i]))
        {
            if((ls.size() == 0) || !is_mathch(ls.top(), code[i]))
            {
                ls.push(code[i]);
            }
            else if(is_mathch(ls.top(), code[i]))
            {
                ls.pop();
            }
        }

        i++;
    }

    return (ret && (ls.size() == 0));
}

int main()
{
    cout << scan("[\"<a{b(\'x\')c}d>\"]")<< endl;
    cout << scan("else if(is_quot(code[i])){if((stack.size() == 0) || !is_match(stack.top(),code[i])){stack.push(code[i]);}else if(is_match(stack.top(),code[i])){stack.pop();}}")<< endl;

   return 0;
}

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