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
    
     {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
    
     {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 
    
     class LinkStack: public Stack
     
      {protected:    LinkList
      
        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
    
     {protected:    LinkList
     
       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 
    
     #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
     
       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("[\"
      
       \"]")<< 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.栈“先入后出”的特性适用于检测成对出现的符号，非常适合就近匹配的场合。