栈

介绍

栈是一种用于存储数据的简单数据结构，有点类似链表或者顺序表（统称线性表），栈与线性表的最大区别是

数据的存取的操作，我们可以这样认为栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端

进行，一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)，同时把插入元素的操作

称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素，则称为空栈，栈的结构如下图：

由图我们可看成栈只能从栈顶存取元素，同时先进入的元素反而是后出，而栈顶永远指向栈内最顶部的元素。

到此可以给出栈的正式定义：栈(Stack)是一种有序特殊的线性表，只能在表的一端(称为栈顶，top，总是指向栈顶

元素)执行插入和删除操作，最后插入的元素将第一个被删除，因此栈也称为后进先出(Last In First Out,LIFO)或先

进后出(First In Last Out FILO)的线性表。栈的基本操作创建栈，判空，入栈，出栈，获取栈顶元素等，注意栈不

支持对指定位置进行删除，插入。

栈的设计与实现

顺序栈

接口Stack声明如下：

/**
* 栈接口抽象数据类型
*/
publicinterfaceStack<T> {

  /**
   * 栈是否为空
   * @return
   */
  booleanisEmpty();

  /**
   * data元素入栈
   * @param data
   */
  voidpush(Tdata);

  /**
   * 返回栈顶元素,未出栈
   * @return
   */
  Tpeek();

  /**
   * 出栈,返回栈顶元素,同时从栈中移除该元素
   * @return
   */
  Tpop();
}

顺序栈，顾名思义就是采用顺序表实现的的栈，顺序栈的内部以顺序表为基础，实现对元素的存取操作，当然我们

还可以采用内部数组实现顺序栈，在这里我们使用内部数据组来实现栈，至于以顺序表作为基础的栈实现，将以源

码提供。这里先声明一个顺序栈其代码如下，实现Stack和Serializable接口：

**
*顺序栈的实现
*/
publicclassSeqStack<T>implementsStack<T>, Serializable{

   // 栈顶指针， -1 为空栈
   privateinttop=-1;

   //存放元素的数组
   privateT[] array;

   //容量，默认为10
   privateintcapacity=10;

   // 当前存放的个数
   privateintsize;

   publicSeqStack(intcapacity) {
       array= (T[]) newObject[capacity];
   }

   publicSeqStack() {
       array= (T[]) newObject[capacity];
   }

   publicintgetSize() {
       returnthis.size;
   }

   @Override
   publicbooleanisEmpty() {

       returntop==-1;
   }

   @Override
   publicvoidpush(Tdata) {

       if (array.length==size){
           //扩容
           ensureCapacity(size*2+1);
       }
       //添加元素、记录存放个数
       array[++top] =data;
       size++;
   }

   @Override
   publicTpeek() {

       //判断是否为空栈
       if (isEmpty()){
           thrownewEmptyStackException();
       }

       returnarray[top];
   }

   @Override
   publicTpop() {

       //判断是否为空栈
       if (isEmpty()){
           thrownewEmptyStackException();
       }

       size--;
       returnarray[top--];
   }

   /**
    * 扩容方法
    * @param capacity
    */
   privatevoidensureCapacity(intcapacity) {

       // 如果需要拓展的容量比现在数组的容量还小,则无需扩容
       if (capacity<size){
           return;
       }

       //先将数据存起来
       T[] old=array;
       array= (T[]) newObject[capacity];
       for (inti=0; i<old.length ;i++){
           array[i] =old[i];
       }

   }

   //测试
   publicstaticvoidmain(String[] args) {

       SeqStack<Object>stack=newSeqStack<>();
       stack.push("A");
       stack.push("B");
       stack.push("C");

       // size在减少，必须记录
       intsize=stack.getSize();
       for (inti=0; i<size ;i++){
           System.out.println(stack.pop());
       }
       System.out.println(stack.getSize());
   }

}

链式栈

我们接着来看看链式栈，所谓的链式栈（Linked Stack），就是采用链式存储结构的栈，由于我们操作的是栈顶一端，因此这里采用单链表（不带头结点）作为基础，直接实现栈的添加，获取，删除等主要操作即可。其操作过程如下图：

无论是插入还是删除直接操作的是链表头部也就是栈顶元素，因此我们只需要使用不带头结点的单链表即可。

/**
* 链式栈实现类
* @param <T>
*/
publicclassLinkedStack<T>  implementsStack<T>, Serializable{

   privateintsize;

   privateNode<T>top;

   publicintgetSize() {
       returnsize;
   }

   @Override
   publicbooleanisEmpty() {
       returntop==null||top.data==null;
   }

   @Override
   publicvoidpush(Tdata) {

       if (data==null){
           thrownewNullPointerException();
       }

       //调用pop()后top可能为null
       if (top==null){
           top=newNode<>(data, null);

       }elseif(top.data==null){
           //有头节点，但是内容为空
           top.data=data;

       }else{
           //加入子节点
           Node<T>p=newNode<T>(data, top);
           //更新栈顶
           top=p;
       }
       size++;

   }

   @Override
   publicTpeek() {

       if (isEmpty()){
           thrownewEmptyStackException();
       }

       returntop.data;
   }

   @Override
   publicTpop() {

       if (isEmpty()){
           thrownewEmptyStackException();
       }

       Tdata=top.data;
       //获取上一个节点
       top=top.top;
       size--;
       returndata;
   }

   publicstaticvoidmain(String[] args) {

       LinkedStack<Object>stack=newLinkedStack<>();
       stack.push("A");
       stack.push("B");
       stack.push("C");

       // size在减少，必须记录
       intsize=stack.getSize();
       for (inti=0; i<size ;i++){
           System.out.println(stack.peek());
           stack.pop();
       }
       System.out.println(stack.getSize());

   }

}

节点类

/**
* 节点类
* @param <T>
*/
publicclassNode<T> {

   publicTdata;

   publicNode<T>top;

   publicNode(Tdata, Node<T>top) {
       this.data=data;
       this.top=top;
   }
}

栈的应用

栈是一种很重要的数据结构，在计算机中有着很广泛的应用，如下一些操作都应用到了栈。

• 符号匹配
• 中缀表达式转换为后缀表达式
• 计算后缀表达式
• 实现函数的嵌套调用
• HTML和XML文件中的标签匹配
• 网页浏览器中已访问页面的历史记录

接下来我们分别对符合匹配进行简单的分析，以加深我们对栈的理解。

符号匹配

在编写程序的过程中，我们经常会遇到诸如圆括号“()”与花括号“{}”，这些符号都必须是左右匹配的，这就是我们所说的符合匹配类型，当然符合不仅需要个数相等，而且需要先左后右的依次出现，否则就不符合匹配规则，如“)(”，明显是错误的匹配，而“()”才是正确的匹配。有时候符合如括号还会嵌套出现，如“9-(5+(5+1))”,而嵌套的匹配原则是一个右括号与其前面最近的一个括号匹配，事实上编译器帮我检查语法错误是也是执行一样的匹配原理，而这一系列操作都需要借助栈来完成，接下来我们使用栈来实现括号”()”是否匹配的检测。

判断原则如下（str=”((5-3)*8-2)”）：

1. 设置str是一个表达式字符串，从左到右依次对字符串str中的每个字符char进行语法检测，如果char是，左括号则入栈，如果char是右括号则出栈(有一对匹配就可以去匹配一个左括号，因此可以出栈)，若此时出栈的字符char为左括号，则说明这一对括号匹配正常，如果此时栈为空或者出栈字符不为左括号，则表示缺少与char匹配的左括号，即目前不完整。
2. 重复执行a操作，直到str检测结束，如果此时栈为空，则全部括号匹配，如果栈中还有左括号，是说明缺少右括号。

整个检测算法的执行流程如下图：

接着我们用栈作为存储容器通过代码来实现这个过程

/**
* 表达式校验
*/
publicclassCheckExpression  {

   publicstaticStringisValid(Stringexpstr){

       LinkedStack<String>stack=newLinkedStack<String>();
       inti=0;
       
       while (i<expstr.length()){

           charc=expstr.charAt(i);
           i++;

           switch (c){
               case'(':
                   //入栈
                   stack.push(String.valueOf(c));
                   break;
               case')':
                   //出栈
                   stack.pop();
                   break;
           }
       }

       //最后检测是否为空,为空则检测通过
       if(stack.isEmpty()){
           return"check pass!";
       }
       else{
           return"check exception!";
       }

   }

   publicstaticvoidmain(String[] args) {

       Stringstr="(((5-3)*8-2)";
       System.out.println(isValid(str));

   }

}