【Java数据结构】---List（Stack）

乐观学习，乐观生活，才能不断前进啊！！！

我的主页：optimistic_chen

我的专栏：c语言 ，Java

欢迎大家访问~
创作不易，大佬们点赞鼓励下吧~

前言

截至目前在集合框架中，我们学完了List接口下的ArrayList和LinkedList，今天要学的是栈（Stack）,数据结构中最让人“开心”的部分，期待一下吧~ ~ ~

栈Stack

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

栈顶 :进行数据插入和删除操作的一端，另一端称为栈底。栈中的数据元素遵守后进先出的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶

栈的模拟实现

根据Stack的源码，它只有简单的几个方法，并不像之前ArrayList、LinkedList那么多的方法。因此，我们学起来一定会轻松很多。

首先，实现整个栈，我们要清楚，这个栈要拿数组表示或者链表表示？

其实两者都行，只是对于我们初学者来说，数组更好接受，也更容易接收。把栈中的元素以下标的形式体现出来，是不是更好理解了呢？

压栈操作

public void push(int val){if(isFull()){this.array= Arrays.copyOf(array,2*array.length);}array[usedSize++]=val;}public boolean isFull(){return usedSize==array.length;}

出栈操作

public int pop(){if(isEmpty()){throw new EmptyStackExpection();}int val=array[usedSize-1];usedSize--;return val;}
public boolean isEmpty(){if(usedSize==0){return true;}return false;}

获取栈顶元素

public int peek(){if(isEmpty()){throw new EmptyStackExpection();}return array[usedSize-1];}

测试代码：

public static void main(String[] args) {MyStack stack=new MyStack();stack.push(10);stack.push(11);stack.push(12);stack.push(13);stack.push(14);System.out.println(stack.pop());System.out.println(stack.peek());}

使用数组来模拟的栈叫做顺序栈，它的入栈、出栈的时间复杂度都是O(1)；
那么用链表来模拟的栈称链式栈，单链表的可以采用头插法入栈或者尾插法入栈。

既然单链表可以，那么双向链表当然也是OK的，并且，入栈时，不管是头插法还是尾插法，时间复杂度可以达到O(1)

public static void main(String[] args) {LinkedList<Integer> stack=new LinkedList<>();stack.push(10);stack.push(11);stack.push(12);stack.push(13);stack.push(14);System.out.println(stack.pop());System.out.println(stack.peek());}

所以，LinkedList不仅是链表也可以当做栈来使用。

从下图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的，这个以后再说。

栈的练习

有效的括号 - - -力扣

public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(int i=0;i<s.length();i++){char ch=s.charAt(i);if(ch=='('||ch=='['||ch=='{'){stack.push(ch);}else{if(stack.isEmpty()){return false; }//此时开始判断是否匹配char ch2=stack.peek();if(ch==')'&&ch2=='('||ch==']'&&ch2=='['||ch=='}'&&ch2=='{'){stack.pop();}else{return false;}}}if(!stack.isEmpty()){return false;}return true;}

逆波兰表达式求值

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(String str : tokens){if(!isOperator(str)){int x=Integer.parseInt(str);stack.push(x);}else{int val2=stack.pop();int val1=stack.pop();switch(str){case "+":stack.push(val1+val2);break;case "-":stack.push(val1-val2);break;case "*":stack.push(val1*val2);break;case "/":stack.push(val1/val2);break;}}}return stack.pop();}private boolean isOperator(String ch){if(ch.equals("+")||ch.equals("-")||ch.equals("*")||ch.equals("/")){return true;}return false;}
}

完结

好了，到这里Java语法部分就已经结束了~
如果这个系列博客对你有帮助的话，可以点一个免费的赞并收藏起来哟~
可以点点关注，避免找不到我~ ，我的主页：optimistic_chen
我们下期不见不散~~Java

下期预告: **【Java数据结构】- - -Queue **