3.3 成员方法
3.3.1 压栈
首先得判断数组容量是否已满，如果满了则需要扩容，扩容为有效元素个数的两倍，如果没满则不需要扩容。直接在数组的 size 位置添加元素，然后 size++ 。因为 size 是有效元素的个数，数组下标是从 0 开始，size - 1 则为最后一个元素，size 则为最后一个元素后面的一个位置
public int push(int data) { // 判断是否需要增容 if (this.size == this.elem.length) { this.elem = Arrays.copyOf(this.elem, this.size * 2); } // 压栈只能往栈顶压栈 this.elem[this.size++] = data; return data; }
3.3.2 出栈
首先判断栈是否为 null，如果为空则不能出栈，直接报异常。如果不为空让 size = size - 1，因为出栈了一个元素，那么有效元素个数也就需要减少一个
// 出栈 public int pop() { // 判断栈是否为null if (this.size == 0) { throw new MyStackEmptyException("栈为空！"); } this.size = this.size - 1; return this.elem[this.size]; }
3.3.3 异常
public class MyStackEmptyException extends RuntimeException { public MyStackEmptyException() { } public MyStackEmptyException(String message) { super(message); } }
3.3.4 查看元素
首先判断栈是否为 null，如果为空则不能出栈，直接报异常。如果不为空则直接返回最后一个元素
// 查看栈顶元素 public int peek() { // 判断栈是否为null if (this.size == 0) { throw new MyStackEmptyException("栈为空！"); } return this.elem[this.size - 1]; }
3.3.5 清空栈
直接让 size = 0
public boolean empty() { return this.size == 0; }
4.关于栈的 OJ 题
4.1 有效的括号 （题目来源：力扣）
题目：给定一个只包括 '( '，')'，'{'，'}'，'['，']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
解题思路：如果字符串为空，则返回 false。否则就实例化一个栈，依次遍历字符串中的每一个字符，如果为左括号，则直接入栈。如果为右括号，则先判断栈是否为空，如果为空则说明右括号没有对应的左括号，则直接返回false。如果栈不为空，则出栈顶的元素，并且将这个元素的值用一个临时变量存储起来，然后判断这两个括号是否匹配，如果不匹配则直接返回false。如果匹配则继续执行字符串下一个字符，直到遍历完字符串中的每一个字符，才会跳出循环。跳出循环后，判断栈是否为空，如果为空，说明括号全部匹配。如果不为空，说明左括号比右括号多则返回 false。
import java.util.*; class Solution { public boolean isValid(String s) { //判断字符串是否为空 if(s == null) { return false; } //实例化一个栈 Stack<Character> stack = new Stack<>(); //遍历字符串中的每一个字符 for(int i = 0; i < s.length(); i++) { char right = s.charAt(i);//获取字符串中第i个位置的字符 //判断字符串是否为左括号 if(right == '(' || right == '{' || right == '[') { stack.push(right);//入栈 } else { //判断栈是否为空 if(stack.empty()) { return false; } else { char left = stack.pop();//出栈 //判断左括号与右括号是否匹配 if(!(left == '(' && right == ')' || left == '{' && right == '}' || left == '[' && right == ']')) { return false; } } } } if(stack.empty()) { return true; } return false; } }
4.2 逆波兰表达式求值（题目来源：力扣）
题目：根据逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
解题思路：首先判断这个字符串数组是否为空，如果为空我们就返回一个无效的值（假设这个无效的值为：-1），那我们就返回 -1。如果不为空我们就创建一个存储整型元素的栈，用来存储左操作数和右操作数。然后我们就遍历字符串数组，每一次遍历的时候我们都需要判断它是否为 + - * / 这些操作符，如果不是就将这个字符串转换为整型数入栈，如果是则需要判断栈当中是否有两个及以上的操作数，如果有则需要在栈中pop两个元素并存储在两个整型变量中当做左操作数和右操作数，然后匹配对应的操作符进行运算将运行的结果在放入栈中，如果栈中小于两个元素则返回无效值。如果在循环的时候没有返回，说明运算完成，将栈中最后一个元素pop并且返回即可。
class Solution { public int evalRPN(String[] tokens) { if (tokens == null) { return -1; } Stack<Integer> stack = new Stack<>(); for (int i = 0; i < tokens.length; i++) { if (!(tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/"))) { int tmp = Integer.parseInt(tokens[i]); stack.push(tmp); } else if (stack.size() >= 2){ int right = stack.pop(); int left = stack.pop(); int sum = 0; switch (tokens[i]) { case "+":sum = left + right;break; case "-":sum = left - right;break; case "*":sum = left * right;break; case "/":sum = left / right;break; } stack.push(sum); } else { return -1; } } return stack.pop(); } }
4.3 栈的压入、弹出序列
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
解题思路：首先判断传过来的两个整型数组是否都为空，如果都为空则返回 true。否则判断它们两个当中是否有一个为空，如果有则返回 false。否则就判断两个数组的长度是否相同，如果不相同则直接返回 false。然后上述的条件都不满足则说明数组都不为空，且长度相等。创建一个存放整型元素的栈，创建两个整型变量i，j用来存放两个数组的下标位置。然后遍历 pushA 数组，在遍历的时候判断 pushA[i] 位置的元素是否与 popA[j] 位置的元素不相等，如果不相等则把 pushA[i] 位置的元素入栈，如果相等则不让 pushA[i] 位置的元素入栈，然后 j++，循环判断栈是否为空且判断栈顶元素与此时的 popA[j] 是否相等，如果不为空且栈顶元素与此时的 popA[j] 相等，则出栈，然后j++。当遍历完 pushA 时，判断栈是否为空，如果为空则返回 true，否则返回 false。
import java.util.*; public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { if(pushA == null && popA == null) { return true; } else if(pushA == null || popA == null) { return false; } else if(pushA.length != popA.length) { return false; } Stack<Integer> stack = new Stack<>(); int i = 0; int j = 0; while(i < pushA.length) { if(pushA[i] != popA[j]) { stack.push(pushA[i]); } else { j++; while(!(stack.empty()) && stack.peek() == popA[j]) { stack.pop(); j++; } } i++; } if(stack.empty()) { return true; } return false; } }
