目录介绍
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/yangchong2…
如果觉得好，可以 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
*/
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/…
简书：http://www.jianshu.com/u/b7b2…
csdn：http://my.csdn.net/m0_37700275
喜马拉雅听书：http://www.ximalaya.com/zhubo…
开源中国：https://my.oschina.net/zbj161…
泡在网上的日子：http://www.jcodecraeer.com/me…
邮箱：yangchong211@163.com
阿里云博客：https://yq.aliyun.com/users/a… 239.headeruserinfo.3.dT4bcV
segmentfault 头条：https://segmentfault.com/u/xi…
掘金：https://juejin.im/user/593943…