目录
栈的概念
栈的方法
栈的实现
数组实现
push方法 压栈
pop方法 出栈
peek方法 获取栈顶元素
size方法 获取有效元素个数
链表实现
结尾
完整代码
数组实现栈代码
双向链表实现栈代码
栈的概念
栈是一种特殊的线性表,只允许在 固定的一段 进行插入和删除数据,配合下面图能有更清楚的认识。
压栈:栈的插入顺序叫做进栈/压栈/入栈,入数据在栈底
出栈:栈的删除操作叫做出栈,出数据在栈顶
栈里面放数据的顺序是 12 23 34,取出数据的顺序是34 23 12
更形象一点的例子,是枪子弹的打出顺序,最后的放进去的子弹会先被打出,
栈从虚拟机的角度有个特点:先进的后出
栈的方法
栈的方法有一下六种
栈的实现
栈可以从数组方面实现,也可以从链表方面实现,下面会有对应的演示。
数组实现的栈叫做 顺序栈,链表实现的栈叫做 链式栈。
数组实现
先定义基本变量,因为是数组实现栈,所以定义数组elem以及useSize记录数组中有效元素个数。
public class MyStack {public int[] elem;public int useSize;public MyStack(){this.elem = new int[10];}
}
push方法 压栈
public void push(int val){elem[useSize] = val;useSize++;}
这部分代码看起来是符合我们要求的,是要把 val值 放入到 elem数组中,但这是一般情况,如果我们放 val值 时数组满了,是不是需要给数组扩容,这时候我们可以写一个判断数组是否为满的方法(isFull方法)。因为这个方法只有push方法才用得到,所以用private。
private boolean isFull(){return useSize == elem.length;}
push方法完整为以下代码:
public void push(int val){if(isFull()){elem = Arrays.copyOf(elem,2*elem.length);}elem[useSize] = val;useSize++;}private boolean isFull(){return useSize == elem.length;}
pop方法 出栈
pop方法的功能是把栈顶的元素移出栈,同时打印一遍。在移除元素之前,要考虑到栈里有没有元素,没有元素就无法移除。所以需要写一个方法来判断(isEmpty方法)。
private boolean isEmpty(){return useSize == 0;}
对于移除栈顶的元素,也就是最后加入的元素,我们可以采用useSize-1来实现,这样就能在打印数组的时候不去打印出栈顶的元素。
public int pop(){if(isEmpty()){System.out.println("栈为空");//这里也可以写个异常来提醒}int cur = elem[useSize-1];useSize--;return cur;}
如果要写一个异常来提醒的话,需要再写一个异常类
对应的pop方法为
public int pop(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];useSize--;return cur;}
peek方法 获取栈顶元素
获取栈顶元素在上面的出栈方法中也提到了,不过上面是要把栈顶元素删除,这里只需要返回即可。
public int peek(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];return cur;}
size方法 获取有效元素个数
这里其实在定义初始变量的时候也有提到,便是其中 useSize 所代表的意思。
public int size(){return useSize;}
链表实现
用链表实现栈,推荐使用双向链表来实现
因为 入栈 不管是头插法还是尾插法都可以是心啊,时间复杂度都是O(1)。
public class CheckEmptyExpetion extends RuntimeException{public CheckEmptyExpetion() {}public CheckEmptyExpetion(String message) {super(message);}
}
结尾
区分三种不同的概念
栈:是一种数据结构
虚拟机栈:是JVM中一类内存
栈帧:是运行一个函数/方法,给这个函数开辟的一个内存
完整代码
数组实现栈代码
CheckEmptyException类
public class CheckEmptyExpetion extends RuntimeException{public CheckEmptyExpetion() {}public CheckEmptyExpetion(String message) {super(message);}
}
MyStack类
import java.util.Arrays;public class MyStack {public int[] elem;public int useSize;public MyStack(){this.elem = new int[10];}public void push(int val){if(isFull()){elem = Arrays.copyOf(elem,2*elem.length);}elem[useSize] = val;useSize++;}private boolean isFull(){return useSize == elem.length;}public int pop(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];useSize--;return cur;}public int peek(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];return cur;}private boolean isEmpty(){return useSize == 0;}public int size(){return useSize;}
}
双向链表实现栈代码
public static void main(String[] args) {LinkedList<Integer> stack = new LinkedList<>();stack.push(12);stack.push(23);stack.push(34);stack.push(45);System.out.println(stack);}