前言
什么是栈(Stack)
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。遵循先进后出的原则。
类似于：一串羊肉串，后串进去的肉最先被吃到。
底层是数组
栈方法
栈的模拟实现
//接口 public interface IStack { //放元素 void push(int x); //取元素 int pop(); //查看元素 int peek(); //栈大小 int size(); //判断满没满 boolean empty(); //判断空没空 boolean full(); } package stackdemo; import java.util.Arrays; //类实现接口 public class MyStack implements IStack{ private int[] elem;//栈的底层是一个数组 private int usedSize;//有效数据的个数 private static final int DEFAULT_CAPACITY = 10;//自定义数组长度 //构造方法 public MyStack(){ elem = new int[DEFAULT_CAPACITY]; } //放栈顶元素 @Override public void push(int x) { //先检查满没满 if (full()){ //满了，调用数组拷贝扩容空间 elem = Arrays.copyOf(elem,elem.length*2); } //没满就放x elem[usedSize] = x; usedSize++; } //取出栈顶元素 @Override public int pop() { if (empty()){ //抛异常 throw new EmptyException("栈空了！"); } int old = elem[usedSize-1];//usedSize往栈底移动一格 usedSize--;//相当于删除 //如果是引用类型 //elem[usedSize] = null; return old; } //查找栈顶的元素，跟pop不一样的是，peek不用删除噢，只是返回栈顶那个元素噢 @Override public int peek() { if (empty()){ //抛异常 throw new EmptyException("栈空了！"); } return elem[usedSize-1];// } /算栈的大小 @Override public int size() { return usedSize; } //判断栈空没空 @Override public boolean empty() { return usedSize == 0; } //判断栈满没满 @Override public boolean full() { if (usedSize == elem.length){ return true; } return false; } } //抛异常 public class EmptyException extends RuntimeException { //构造方法 public EmptyException(String msg){ super(msg); } }
链表也可以实现栈
单链表
双向链表
从头入 从头出都可以
1.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1
答案：C
2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。
A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA
答案：B
逆波兰表达式
下面举的例子是后缀表达式，就是把符号移到括号右边。
怎么转换成逆波兰表达式
逆波兰表达式在栈中怎么使用
1.把式子转换成逆波兰表达式后
2.遇到数字就放栈里面
2.当遇到非数字字符，取出栈里面最顶上的两个元素，第一个元素放在字符右边，第二个放左边。
3.得到的结果又放进栈里面
4.再继续上面步骤
class Solution { public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for(String s : tokens) { //不是操作符就是数字 if (!isOperation(s)) { stack.push(Integer.parseInt(s)); } else { int num2 = stack.pop(); int num1 = stack.pop(); switch (s) { case "+": stack.push(num1 + num2); break; case "-": stack.push(num1 - num2); break; case "*": stack.push(num1 * num2); break; case "/": stack.push(num1 / num2); break; } } } return stack.pop(); } private boolean isOperation(String s) { if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) { return true; //是返回true } //不是返回false return false; } }
最小栈
class MinStack { //实例化两个栈 private Stack<Integer> stack ; private 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(){ int val = stack.pop(); if (!minStack.empty()){ if (val == minStack.peek()){ minStack.pop(); } } } //获取普通栈栈顶元素值 public int top(){ return stack.peek(); } //查看最小栈 public int getMin(){ if (!minStack.empty()){ return minStack.peek(); } return -1; } }
括号匹配
class Solution { 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.empty()){ //1.如果右括号为空 return false; } //栈不为空，peek一下是哪个左括号 char ch2 = stack.peek();//ch2是左括号，ch是右括号 if( (ch2 == '{' && ch == '}') ||(ch2 == '(' && ch == ')') || (ch2 == '[' && ch == ']')){ //匹配的话取出栈顶的左括号 stack.pop(); }else{ return false; } } } if(!stack.empty()){ return false; } return true; } }
