【java数据结构】栈

此篇博客希望对你有所帮助（帮助你了解栈），不懂的或有错误的也可在评论区留言，错误必改评论必回！！！持续关注，下一篇博客是java数集合框架中的队列！！！整篇博客的代码都在Gitee中（代码链接放下文章结尾）。

一、栈的概念

栈：是一种特殊的线性表，其只允许固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守先进后出的原则。

压栈：栈的插入操作叫做进栈\压栈\入栈。入栈数据在栈顶。

出栈：栈的删除操作叫做出栈。出栈数据在栈顶。

二、 栈的使用

从上图可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表。不同的是Vector是线程安全的。

三、 栈的模拟实现(数组)

栈是一个特殊的顺序表,所以采用链表和数组的方式都可实现,但是,一般采用数组的方式实现.

    public MyStack(){}public int push(int e){}public int pop(){}public int peek(){}public int size(){}public boolean empty(){}

构造方法

public class MyStack {int[] array;int size;public MyStack() {array = new int[5];//默认栈容量为5}
} 

size()

获取栈中元素个数

    public int size(){return size;}

empty()

判断栈中元素个数是否为空

    public boolean empty(){return size==0;}

push()

首先先判断栈是否为满，如果满则进行扩容，返回要入栈的val值

    public int push(int val){if(size== array.length){array= Arrays.copyOf(array,2*array.length);}array[size]=val;size++;return val;}

pop()

先判断栈是否为空，为空则抛出异常；不为空，则输出栈顶元素，并且移除栈顶元素（栈顶元素发生变化），size–；

自定义为空异常：

public class EmptyException extends RuntimeException{public EmptyException() {}public EmptyException(String message) {super(message);}
}

    public int pop(){if(empty()){throw new EmptyException();}else{int val = array[size-1];size--;return val;}}

peek()

peek()方法是输出栈顶元素，但不移除栈顶元素（栈顶元素不发生变化）。

    public int peek(){if(empty()){throw new EmptyException();}else{return array[size-1];}}

四、 栈的模拟实现(链表)

栈中元素的入栈和出栈的时间复杂度为O(1),因此用链表实现栈就需要考虑插入和输出元素的时间复杂度是否为O(1)。
双链表实现栈：不管头插，头输出和尾插，尾输出，都满足栈的要求，因为我们知道头节点和尾节点的位置。
单链表实现栈：单链表实现栈，我们只能用头插入和头输出，因为我们不知道尾节点的位置，我们只能通过遍历得到尾节点的位置，那么时间复杂度将不是O(1)而是O(n)。

这里我们给大家演示一下用单链表模拟实现栈！

    public int push(int e){}public int pop(){}public int peek(){}public int size(){}public boolean empty(){}

构造方法

    static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;

size()

    public int size() {ListNode cur = head;int size = 0;while (cur != null) {size++;cur = cur.next;}return size;}

empty()

    public boolean empty() {return head==null;}

push()

    public int push(int val) {ListNode cur=new ListNode(val);if(head==null){head=cur;}else{cur.next=head;head=cur;}return head.val;}

pop()

先判空，pop()方法需要删除栈顶元素(这里相当于是头节点)，所以定义一个节点来标记头节点，然后将头节向后移动。

    public int pop() {if(head==null){throw new EmptyException();}ListNode cur=head;head=head.next;return cur.val;}

peek()

因为peek()方法不删除栈顶元素(这里相当于是头节点)，所以这里不需要将头节点向后移动。

    public int peek() {if(head==null){throw new EmptyException();}return head.val;}

五、 栈的例题

有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。

    public boolean isValid(String str) {Stack<Character> stack = new Stack<>();for (int i = 0; i < str.length() ; i++) {char s = str.charAt(i);if (s == '(' || s == '[' || s == '{') {stack.push(s);} else {if (stack.isEmpty()) {return false;}char s2 = stack.peek();if (s == ')' && s2 == '('|| s == '}' && s2 == '{'|| s == ']' && s2 == '[') {stack.pop();} else {return false;}}}if(!stack.isEmpty()){return false;}return true;}

逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。

注意：

1.有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
2.每个操作数（运算对象）都可以是一个整数或者另一个表达式。
3.两个整数之间的除法总是 向零截断 。
4.表达式中不含除零运算。
5.输入是一个根据逆波兰表示法表示的算术表达式。
6.答案及所有中间计算结果可以用 32 位 整数表示。

    public int evalRPN(String[] tokens) {Stack<Integer> stack=new Stack<>();for (int i=0;i<tokens.length;i++) {if(calculation(tokens[i])){int val1=stack.pop();int val2=stack.pop();switch(tokens[i]){case "+":stack.push(val2+val1);break;case "-":stack.push(val2-val1);break;case "*":stack.push(val2*val1);break;case "/":stack.push(val2/val1);break;}}else{stack.push(Integer.valueOf(tokens[i]));}}return stack.pop();}private boolean calculation(String s){if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){return true;}return false;}

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

    public static boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> stack=new Stack<>();int j=0;for(int i=0;i<pushV.length;i++){stack.push(pushV[i]);while(j< popV.length&&!stack.isEmpty()&&stack.peek()==popV[j]){stack.pop();j++;}}if(!stack.isEmpty()){return false;}return true;}

最小栈

public Stack<Integer> stack;public  Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if(minStack.empty()) {minStack.push(val);}else {int peekVal = minStack.peek();if(val <= peekVal) {minStack.push(val);}}}public void pop() {if(stack.empty()) {return;}int popVal = stack.pop();if(popVal == minStack.peek()) {minStack.pop();}}public int top() {if(stack.empty()) {return -1;}return stack.peek();}public int getMin() {if(minStack.empty()) {return -1;}return minStack.peek();}

此篇博客的全部代码！