【java数据结构】栈
【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 here
Stack<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();
}
此篇博客的全部代码！