栈

这边随笔主要是用来学习栈的相关知识

之前学习的数组主要是用来存储数据的，对于无序的数据来说，添加数据很快，但是删除、查找就很慢，我们期望的是插入、删除和查找性能都比较好。为了解决这些问题，二叉树、哈希表的数据结构是更优的选择，而栈，更像是构思算法的工具，不单单是存储数据的工具，在实际开发中有些数据结构，他们存在的周期并不长，只是在程序运行时才会被创建，程序执行结束就会被销毁，这些数据结构就是栈和队列，我们首先来了解栈。

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。

后进先出（LIFO, Last In First Out）是栈的原理运作。栈也称为后进先出表（类似于羽毛球筒）。

 

我们可以用数组来实现一个简单的栈，参考大神的文章 https://www.cnblogs.com/ysocean/p/7911910.html

正如参考文章中所说，用数组实现有一定局限性，不能自动扩容，不能存放不同类型数据，必须要初始化容量，那么我们就按照文章中的方法，来实现功能加强版的栈（可以参考jdk源码中Stack类的实现）

 

直接上代码

package discovery;import java.util.Arrays;import java.util.EmptyStackException;/** * Author :zhanghong * Date   :2019-02-16 22:18. */public class ArrayStack {    //存储元素的数组,声明为Object类型能存储任意类型的数据    private Object[] elementData;    //指向栈顶的指针    private int top;    //栈的总容量    private int size;    //默认构造一个容量为10的栈    public ArrayStack(){        this.size=10;        this.top=-1;        this.elementData=new Object[10];    }    //构造可选容量的栈    public ArrayStack(int initialCapacity){        if(initialCapacity < 0){            throw new IllegalArgumentException("栈初始容量不能小于0: "+initialCapacity);        }        this.elementData = new Object[initialCapacity];        this.top = -1;        this.size = initialCapacity;    }    //判断是否需要扩容    public Boolean isGrow(int topflag){        int oldCapacity=size;        //在栈中压入新元素后，如果现容量大于原始容量，需要扩容        if(oldCapacity<=topflag){            int newCapacity=0;            if((oldCapacity<<1)-Integer.MAX_VALUE>0){                newCapacity=Integer.MAX_VALUE;            }else {                newCapacity=oldCapacity<<1;            }            this.size=newCapacity;            elementData = Arrays.copyOf(elementData,size);            return true;        }else {            return false;        }    }    //判断栈是否为空    public boolean isEmpty(){        return (top == -1);    }    //删除栈顶元素    public void remove(int top){        //栈顶元素置为null        elementData[top] = null;        this.top--;    }    //获取栈顶元素    public Object getTop(){        if(top==-1){            throw new EmptyStackException();        }        return elementData[top];    }    //弹出栈顶元素    public Object pop(){        Object obj=getTop();        remove(top);        return  obj;    }    //压入元素    public Object push(Object item){        isGrow(top+1);        elementData[++top]=item;        return item;    }}

测试一下栈的主要功能

ArrayStack stack = new ArrayStack(3);        stack.push(1);        //System.out.println(stack.peek());        stack.push(2);        stack.push(3);        stack.push("abc");        System.out.println(stack.getTop());        stack.pop();        stack.pop();        stack.pop();        System.out.println(stack.getTop());

结果：

abc

1

接下来我们实现几个小功能

1.实现字符串的倒序排列（利用后进先出的原理）

直接上代码

ArrayStack stack = new ArrayStack();        String str = "how are you";        char[] cha = str.toCharArray();        for(char c : cha){            stack.push(c);        }        while(!stack.isEmpty()){            System.out.print(stack.pop());        }

结果：uoy era woh

 

2.（直接用大神的例子，太牛了）判断特殊字符顺序

写过xml标签或者html标签的，我们都知道<必须和最近的>进行匹配，[ 也必须和最近的 ] 进行匹配。

　　比如：<abc[123]abc>这是符号相匹配的，如果是 <abc[123>abc] 那就是不匹配的。

　　对于 12<a[b{c}]>，我们分析在栈中的数据：遇到匹配正确的就消除

代码如下：

ArrayStack stack = new ArrayStack(3);        String str = "12
     
      ";        char[] cha = str.toCharArray();        for(char c : cha){            switch (c) {                case '{':                case '[':                case '<':                    stack.push(c);                    break;                case '}':                case ']':                case '>':                    if(!stack.isEmpty()){                        char ch = stack.pop().toString().toCharArray()[0];                        if(c=='}' && ch != '{'                                || c==']' && ch != '['                                || c==')' && ch != '('){                            System.out.println("Error:"+ch+"-"+c);                        }                    }                    break;                default:                    break;            }        }
     

结果：通过校验

 

 

根据栈后进先出的特性，我们实现了单词逆序以及分隔符匹配。所以其实栈是一个概念上的工具，具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop()，使得程序不容易出错。

　　对于栈的实现，我们稍微分析就知道，数据入栈和出栈的时间复杂度都为O(1)，也就是说栈操作所耗的时间不依赖栈中数据项的个数，因此操作时间很短。而且需要注意的是栈不需要比较和移动操作，我们不要画蛇添足