栈的实现原理-白红宇

栈的实现原理

阅读量：5237 次

发布时间：2019-06-14

本文共 8437 字，大约阅读时间需要 28 分钟。

目录介绍

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万字，陆续搬到网上]，转载请注明出处，谢谢！

链接地址：

如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

栈系列文章

- 什么是栈？栈的使用场景？异常？栈的效率探索？

- 栈由简单数据实现，栈由动态数组实现，栈由链表实现，创建加强版自定义栈，以及几种不同实现栈的方式比较。

- 栈的顺序存储结构及实现，栈的链式存储结构及实现，两种栈形式比较

- 利用栈实现判断字符串中的括号是否都是配对的，注意：“{[()]}”类似的可以匹配，“{(}}”类似的无法匹配。

- 将字符串“how are you”反转

- 用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

- 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。

- 解析一般数学算式，实现简单的带括号的加减乘除运算。

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
      
        { private T data; private MyStack
       
         next; public MyStack(T data, MyStack
        
          next) { this.data = data; this.next = next; } public T getData() { return data; } public void setData(T data) { this.data = data; } public MyStack
         
           getNext() { return next; } public void setNext(MyStack
          
            next) { this.next = next; } } public class LinkStack
           
             { private MyStack
            
              head; private MyStack
             
               tail; private Integer size=0; public MyStack
              
                getHead() { return head; } public void setHead(MyStack
               
                 head) { this.head = head; } public MyStack
                
                  getTail() { return tail; } public void setTail(MyStack
                 
                   tail) { this.tail = tail; } public Integer getSize() { return size; } public void setSize(Integer size) { this.size = size; } public void addStack(N data){ MyStack
                  
                    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
      
        linkStack = new LinkStack<>(); linkStack.addStack(1); linkStack.addStack(2); linkStack.addStack(3); linkStack.addStack(4); linkStack.addStack(5); for(int i=0;i

3.3 性能和局限性

假设栈中有n个元素，基于链表的栈实现中，关于栈插入元素和取出元素的时间复杂度是O(1)

数据入栈和出栈的时间复杂度都为O(1)，也就是说栈操作所耗的时间不依赖栈中数据项的个数，因此操作时间很短。而且需要注意的是栈不需要比较和移动操作。

04.栈Stack源码分析

在Android中，对于activity使用栈stack进行管理的，下面看看栈源代码。

可以看到栈stack是实现vector，其实底层也是用数组来实现的。

public class Stack
      
        extends Vector
       
         {    /**     * 创建一个空的栈对象 */ 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; } } }