【java数据结构】栈
- 一、栈的概念
- 二、 栈的使用
- 三、 栈的模拟实现(数组)
- 构造方法
- size()
- empty()
- push()
- pop()
- peek()
- 四、 栈的模拟实现(链表)
- 构造方法
- size()
- empty()
- push()
- pop()
- peek()
- 五、 栈的例题
此篇博客希望对你有所帮助(帮助你了解栈),不懂的或有错误的也可在评论区留言,错误必改评论必回!!!持续关注,下一篇博客是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();}
此篇博客的全部代码!