目录介绍
-
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一下,谢谢!当然也欢迎提出建议,万事起于忽微,量变引起质变!
栈系列文章
-
- 什么是栈?栈的使用场景?异常?栈的效率探索?
-
- 栈由简单数据实现,栈由动态数组实现,栈由链表实现,创建加强版自定义栈 ,以及几种不同实现栈的方式比较。
-
- 栈的顺序存储结构及实现,栈的链式存储结构及实现,两种栈形式比较
-
- 利用栈实现判断字符串中的括号是否都是配对的,注意:“{[()]}”类似的可以匹配,“{(}}”类似的无法匹配。
-
- 将字符串“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<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.关于博客汇总链接
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