数据结构（八）——栈

数据结构（八）——栈

一、栈的简介

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。
栈的特性：后进先出

栈的基本操作包括创建栈、销毁栈、出栈、入栈、获取栈顶元素、获取栈的大小、清空栈。

二、栈的实现

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