栈的实现原理

目录介绍

• 01.栈由简单数据实现
  • 1.1 简单数组代码实现
  • 1.2 可能出现问题
  • 1.3 性能和局限性
• 02.栈由动态数组实现
  • 2.1 基于简单数组存在问题
  • 2.2 第一种解决办法
  • 2.3 第二种解决办法
  • 2.4 动态数组实现栈代码
  • 2.5 性能和局限性
• 03.栈由链表实现
  • 3.1 使用链表的优势
  • 3.2 链表实现栈代码
  • 3.3 性能和局限性
• 04.Android栈Stack源码分析
  • 4.1 源码展示
  • 4.2 为何选用数组实现栈
• 05.创建加强版自定义栈
  • 5.1 扩容和泛型

好消息

• 博客笔记大汇总【16年3月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！
• 链接地址：https://github.com/yangchong211/YCBlogs
• 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

栈系列文章

• 00.栈基础介绍
  • 什么是栈？栈的使用场景？异常？栈的效率探索？
• 01.栈的实现原理
  • 栈由简单数据实现，栈由动态数组实现，栈由链表实现，创建加强版自定义栈 ，以及几种不同实现栈的方式比较。
• 02.栈的常见操作
  • 栈的顺序存储结构及实现，栈的链式存储结构及实现，两种栈形式比较
• 03.使用栈判断括号是否匹配
  • 利用栈实现判断字符串中的括号是否都是配对的，注意：“{[()]}”类似的可以匹配，“{(}}”类似的无法匹配。
• 04.使用栈实现字符串逆序
  • 将字符串“how are you”反转
• 05.用两个栈实现队列
  • 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
• 06.栈的压入、弹出序列
  • 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
• 07.使用栈解析计算器数学公式
  • 解析一般数学算式，实现简单的带括号的加减乘除运算。

01.栈由简单数组实现

1.1 简单数组代码实现

• 首先看一下实现的代码
  • 用数组实现栈，最主要的是要在类的内部定义一个数组，并且这个数组要具有一定的大小，要在定义栈的时候定义好。

  public class ArrayStack{
      private static final String TAG = "ArrayStack";
      private Object[] contents;
      private int top = -1;
      private int bottom = -1;
      private int SIZE = 10;//有一个初始值大小
  
      public ArrayStack(){
          contents = new Object[SIZE];
          top = -1;
      }
  
      public int push(Object obj) throws Exception {
          if (top > SIZE) throw new Exception("小杨逗比，栈已经满了！");
          top++;
          contents[top] = obj;
          return top;
      }
  
      public Object pop() throws Exception{
          if (top == bottom) throw new Exception("小杨逗比，栈已经空了！");
          Object obj = contents[top];
          contents[top] = null;
          top--;
          return obj;
      }
  
      public boolean isEmpty(){
          return top == bottom;
      }
  
      public int getSize(){
          return top + 1;
      }
  
      public void display() throws Exception{
          if (getSize() == 0) throw new Exception("空栈!");
          for (int i=getSize()-1;i>=0;i--){
              System.out.print(contents[i].toString() + "->");
          }
          System.out.println("");
      }
  } 
  
  
  public void test{
      ArrayStack as = new ArrayStack();
      //as.display();
      as.push("小杨逗比");
      as.push("潇湘剑雨");
      as.push("yc");
      as.push("逗比");
      as.push("aaa");
      as.push("ertte");
      as.push("hello");
      as.display();
      as.pop();
      System.out.println(as.getSize());
      as.pop();
      as.display();
  }
  

1.2 可能出现问题

• 可能会出现的问题
  • 当数组栈存满了元素的时候，如果执行插入数据，将会抛出栈满异常。
  • 当数组栈没有元素的时候，如果执行出栈数据，将会抛出栈空异常。

1.3 性能和局限性

• 性能和局限性分析
  • 栈的最大空间必须提前声明，而且关键是大小还不能改变，这就蛋疼了。所以会出现执行入栈或者出栈操作时会出现异常。那么解决异常就是每次入栈判断栈是否存储满，每次出栈判断栈是否为空。
  • 假设栈中有m个元素，基于简单数组实现的栈。栈的出栈，入栈，判空，获取大小等时间复杂度都是O(1)。

02.栈由动态数组实现

2.1 基于简单数组存在问题

• 基于简单数组的栈实现方法中，采用一个下标变量top，它始终指向栈中最新插入元素的位置。
• 当插入元素时，会增加top值，并且会在数组该下标的位置存储新的元素。
• 当删除元素时，先获取下标变量top位置的元素，然后减小变量top的值。
• 当top下标变量为-1时，表示栈是空的。但是存在问题是：在固定大小的数组中，如何处理所有空间都已经保存栈元素这种情况？？？

2.2 第一种解决办法

• 可能首先会想到，每次将数组大小增加1或者减小1，将会怎么样？
  • 插入元素，栈的空间大小增加1
  • 删除元素，栈的空间大小减去1
• 这样做存在极大问题
  • 频繁增加数组大小的方法开销很大。为什么这样说呢？
  • 当n=3时，执行push插入元素操作，当插入第四条元素时，会新建一个大小为4的数组，然后复制原数组中所有的元素到新的数组中，然后在新的数组中的末尾添加插入元素。以此类推，每次插入数据，都会重新创建一个新的数组对象，然后拷贝旧的数组数据到新的数组中来，然后在末尾添加新元素，这样做实在不好。

2.3 第二种解决办法

• 在第一种解决办法中改造。比如我们经常听到ArrayList集合动态扩容，先指定数组的长度，如果数组空间已满，则新建一个比原数据大一倍[或者n倍]的新数组，再然后复制元素。
• 采用这种方式，插入元素操作，开销相对来说要小很多。

2.4 动态数组实现栈代码

• 基于动态数据实现栈的代码如下所示

  class DynArrayStack{
      private int top;
      private int capacity;
      private int[] array;
   
      private void doubleStack(){
          int[] newArray=new int[capacity*2];
          System.arraycopy(array,0,newArray,0,capacity);
          capacity=capacity*2;
          array=newArray;
      }
   
      public DynArrayStack(){
          top=-1;
          capacity=1;
          array=new int[capacity];
      }
   
      public boolean isEmpty(){
          return (top==-1);
      }
   
      public boolean isStackFull(){
          return (top==capacity-1);
      }
   
      public void push(int date){
          if(isStackFull()){
              doubleStack();
          }
          array[++top]=date;
      }
   
      public int pop(){
          if(isEmpty()){
              System.out.println("Stack Empty");
              return 0;
          }else {
              return array[top--];
          }
      }
   
      public void deleteStack(){
          top=-1;
      }
  }
   
  public class Main {
   
      public static void main(String[] args) {
          // write your code here
          DynArrayStack dynArrayStack=new DynArrayStack();
          dynArrayStack.push(1);
          dynArrayStack.push(2);
          dynArrayStack.push(3);
          System.out.println(dynArrayStack.pop());
          System.out.println(dynArrayStack.pop());
          System.out.println(dynArrayStack.pop());
      }
  }
  

2.5 性能和局限性

• 性能
  • 假设有n个元素的栈，基于动态数组的栈实现中，关于栈插入数据，取出数据的时间复杂度都是O(1)。
  • 可能导致的性能问题：倍增太多可能导致内存溢出。
• 存在局限性
  • 是用数组实现栈，在定义数组类型的时候，也就规定了存储在栈中的数据类型，那么同一个栈能不能存储不同类型的数据呢？（声明为Object）？
  • 栈需要初始化容量，而且数组实现的栈元素都是连续存储的，那么能不能不初始化容量呢？（改为由链表实现）？

03.栈由链表实现

3.1 使用链表的优势

• 栈规模的增加和减小都很简洁，而且每个操作都是常数时间开销，每个操作都要使用额外的空间和时间开销来处理指针。

3.2 链表实现栈代码

• 入栈的顺序是：1 2 3 4 5，那么保证出栈的顺序是5 4 3 2 1，以此类推让head节点指向栈顶节点保证让其倒序输出。

  public class MyStack<T> {
      private T data;
      private MyStack<T> next;
   
      public MyStack(T data, MyStack<T> next) {
          this.data = data;
          this.next = next;
      }
   
      public T getData() {
          return data;
      }
   
      public void setData(T data) {
          this.data = data;
      }
   
      public MyStack<T> getNext() {
          return next;
      }
   
      public void setNext(MyStack<T> next) {
          this.next = next;
      }
  }
  
  public class LinkStack<N> {
   
      private MyStack<N> head;
      private MyStack<N> tail;
      private Integer size=0;
   
      public MyStack<N> getHead() {
          return head;
      }
   
      public void setHead(MyStack<N> head) {
          this.head = head;
      }
   
      public MyStack<N> getTail() {
          return tail;
      }
   
      public void setTail(MyStack<N> tail) {
          this.tail = tail;
      }
   
      public Integer getSize() {
          return size;
      }
   
      public void setSize(Integer size) {
          this.size = size;
      }
   
      public void addStack(N data){
          MyStack<N> node = new MyStack<>(data,null);
          if(headIsNull()){
              head = node;
              tail = node;
              size++;
          }else{
              //新加入的node是:(data,null) 让这个新的node的next指向初始的head节点 head变为(data,head))
              node.setNext(head);
              head = node;
              size++;
          }
      }
   
      public N outStack(){
          if(size>0){
              N outData = head.getData();
              head = head.getNext();
              return outData;
          }else{
              throw new RuntimeException("栈里无元素!");
          }
      }
   
      public boolean headIsNull(){
          if(head == null){
              return true;
          }
          return false;
      }
  }
  

• 测试一下

  public void test() {
      LinkStack<Integer> linkStack = new LinkStack<>();
      linkStack.addStack(1);
      linkStack.addStack(2);
      linkStack.addStack(3);
      linkStack.addStack(4);
      linkStack.addStack(5);
  
      for(int i=0;i<linkStack.getSize();i++){
          System.out.println(linkStack.outStack());
      }
  }
  

3.3 性能和局限性

• 假设栈中有n个元素，基于链表的栈实现中，关于栈插入元素和取出元素的时间复杂度是O(1)
• 数据入栈和出栈的时间复杂度都为O(1)，也就是说栈操作所耗的时间不依赖栈中数据项的个数，因此操作时间很短。而且需要注意的是栈不需要比较和移动操作。

04.栈Stack源码分析

• 在Android中，对于activity使用栈stack进行管理的，下面看看栈源代码。
  • 可以看到栈stack是实现vector，其实底层也是用数组来实现的。

  public class Stack<E> extends Vector<E> {
      /**
       * 创建一个空的栈对象
       */
      public Stack() {
      }
  
      /**
       * 将对象推送到此堆栈的顶部。
       */
      public E push(E item) {
          addElement(item);
  
          return item;
      }
  
      /**
       * 移除此堆栈顶部的对象，并将该对象作为此函数的值返回。
       */
      public synchronized E pop() {
          E       obj;
          int     len = size();
          obj = peek();
          removeElementAt(len - 1);
  
          return obj;
      }
  
      /**
       * 查看此堆栈顶部的对象，而不将其从堆栈中移除。
       */
      public synchronized E peek() {
          int     len = size();
  
          if (len == 0)
              throw new EmptyStackException();
          return elementAt(len - 1);
      }
  
      /**
       * 判断是否是空栈
       */
      public boolean empty() {
          return size() == 0;
      }
  
      /**
       * 返回对象位于此堆栈上的基于1的位置。
       */
      public synchronized int search(Object o) {
          int i = lastIndexOf(o);
  
          if (i >= 0) {
              return size() - i;
          }
          return -1;
      }
  
      private static final long serialVersionUID = 1224463164541339165L;
  }
  

05.创建加强版自定义栈

• 一个能自动扩容，第二个能存储各种不同类型的数据，解决办法如下：

  public class ArrayStack {
      //存储元素的数组,声明为Object类型能存储任意类型的数据
      private Object[] elementData;
      //指向栈顶的指针
      private int top;
      //栈的总容量
      private int size;
       
       
      //默认构造一个容量为10的栈
      public ArrayStack(){
          this.elementData = new Object[10];
          this.top = -1;
          this.size = 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 Object push(Object item){
          //是否需要扩容
          isGrow(top+1);
          elementData[++top] = item;
          return item;
      }
       
      //弹出栈顶元素
      public Object pop(){
          Object obj = peek();
          remove(top);
          return obj;
      }
       
      //获取栈顶元素
      public Object peek(){
          if(top == -1){
              throw new EmptyStackException();
          }
          return elementData[top];
      }
      //判断栈是否为空
      public boolean isEmpty(){
          return (top == -1);
      }
       
      //删除栈顶元素
      public void remove(int top){
          //栈顶元素置为null
          elementData[top] = null;
          this.top--;
      }
       
      /**
       * 是否需要扩容，如果需要，则扩大一倍并返回true，不需要则返回false
       * @param minCapacity
       * @return
       */
      public boolean isGrow(int minCapacity){
          int oldCapacity = size;
          //如果当前元素压入栈之后总容量大于前面定义的容量，则需要扩容
          if(minCapacity >= oldCapacity){
              //定义扩大之后栈的总容量
              int newCapacity = 0;
              //栈容量扩大两倍(左移一位)看是否超过int类型所表示的最大范围
              if((oldCapacity<<1) - Integer.MAX_VALUE >0){
                  newCapacity = Integer.MAX_VALUE;
              }else{
                  newCapacity = (oldCapacity<<1);//左移一位，相当于*2
              }
              this.size = newCapacity;
              int[] newArray = new int[size];
              elementData = Arrays.copyOf(elementData, size);
              return true;
          }else{
              return false;
          }
      }
  }
  

其他介绍

01.关于博客汇总链接

• 1.技术博客汇总
• 2.开源项目汇总
• 3.生活博客汇总
• 4.喜马拉雅音频汇总
• 5.其他汇总

02.关于我的博客

• github：https://github.com/yangchong211
• 知乎：https://www.zhihu.com/people/yczbj/activities
• 简书：http://www.jianshu.com/u/b7b2c6ed9284
• csdn：http://my.csdn.net/m0_37700275
• 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
• 开源中国：https://my.oschina.net/zbj1618/blog
• 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
• 邮箱：yangchong211@163.com
• 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
• segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
• 掘金：https://juejin.im/user/5939433efe88c2006afa0c6e