文章目录
- 栈的概念
- 栈的使用
- 栈的模拟实现
- 栈相关面试题
- 括号匹配
- 逆波兰表达式求值
- 栈的压入弹出序列
- 最小栈
栈的概念
- 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。
- 入栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
- 出栈：栈的删除操作叫做出栈。出数据在栈顶
栈的使用
栈中的方法
栈的使用示例
public static void main(String[] args) {
Stack<Integer> s = new Stack();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
System.out.println(s.size()); // 获取栈中有效元素个数---> 4
System.out.println(s.peek()); // 获取栈顶元素---> 4
s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
if(s.empty()){
System.out.println("栈空");
}else{
System.out.println(s.size());
}
}
栈的模拟实现
//使用数组实现栈
import java.util.ArrayList;
import java.util.Arrays;public class MyStack {public int[] elem;public int usedSize;public MyStack() {elem = new int[10];//初始化容量为10}public void push(int val) {if(isFull()) {elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize] = val;usedSize++;}private boolean isFull() {return usedSize == elem.length;}public void pop() {if(isEmpty()) {return;}int oldValue = elem[usedSize-1];usedSize--;System.out.println(oldValue);}private boolean isEmpty() {if(usedSize == 0) {return true;}return false;}public void peek() {if(usedSize == 0) {return;}System.out.println(elem[usedSize-1]);}
}栈相关面试题
括号匹配
--------OJ链接
遍历字符串S，将字符串S，按照下标 i 依次转换为字符 赋值给 ch ，先判断入栈的字符是否为左括号，如果是左括号直接入栈，如果不是左括号，要判断此时栈是否为空，如果为空，则返回 false ；如果不为空，判断栈顶元素 topL 是否和 ch 相互匹配，如果匹配， pop 出栈顶元素，如果不匹配return false。最后判断栈是否为空，为空的话说明括号全部匹配，元素全部出栈，如果栈不为空，则说明有 括号没有匹配到 。（此时的括号为左括号）
【步骤】
遍历字符串
判断是左括号 还是 右括号，左括号直接入栈，不是左括号判断此时栈是否为空，为空return false；
不为空，判断与栈顶元素是否匹配，匹配弹出栈顶元素；不匹配 return false；
字符串遍历完成，栈不为空（此时栈中一定是左括号），return false；为空 return true。
public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(int i = 0; i < s.length(); i++) {Character ch = s.charAt(i);if(ch == '(' || ch == '{' || ch == '[') {stack.push(ch);}else {if(stack.empty()) {return false;}Character topL = stack.peek();if(topL == '(' && ch == ')' || topL == '{' && ch == '}' || topL == '[' && ch == ']') {stack.pop();}else return false;}}if(!stack.empty()) {return false;}return true;}逆波兰表达式求值
--------OJ链接
假设逆波兰表达式为：1+23+（45）+6，它的逆波兰表达式为：1 2 3 * + 4 5 * 6 + 7 * +
【解题思路】将逆波兰表达式按照从左往右的方向遍历，遇到数字就入栈，
遇到运算符号，取出栈中的两个元素，第一个元素放在 运算符的右边，第二个元素放在 运算符的左边，然后把运算结果再次放入栈中。
遍历完逆波兰表达式的字符串后，栈中的元素就是最终的运算结果
栈的压入弹出序列
--------OJ链接
遍历数组，先让 pushV[i] 数组元素入栈，入栈后判断栈顶元素 是否等于 popV[j] ，如果相等，出栈顶元素，j ++；这里的判断及操作，需要while()循环进行，因为可能栈顶元素 和 popV[j] 的值仍然相等，循环条件不能仅仅是 stack.peek() == popV[j]，还要要求此时栈不为空，且 j 下标不越界【因为 有 pop() 操作，和 j++ 操作，有可能出现栈为空，或者 数组下标 j 越界】
public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;for(int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while(j < pushV.length && !stack.empty() && stack.peek() == popV[j]) {stack.pop();j++;}}return stack.empty();}
最小栈
-------OJ链接
另外创建一个栈 minStack ，用来存放此时正常栈中的最小元素
minStack栈中 记录每次入正常栈时，该栈中的最小元素值。因此minStack的栈顶元素就是此时该正常栈中最小的元素
当向正常栈中 放入元素时，如果此时 minStack 栈中为空，则把该元素压入minStack栈中。此后minStack栈中不为空，当再次向正常栈中放入元素时，判断该元素 是否小于等于 minStack 中的栈顶元素 ，如果小于等于，把该元素放入 minStack 栈中，否则不入栈【注意条件是 “<=”,如果正常栈中存在两个相等的最小值，那么当把其中一个最小值pop之后，此时栈中最小值还是相同的】
当正常栈 pop() 栈顶元素时，判断pop() 出的元素 是否 等于 minStack 中的栈顶元素，如果等于，把minStack中的栈顶元素也 pop() 出去，因为此时该栈中的最小元素已经pop，对应minStack也该把该栈栈顶元素pop，此时minStack的栈顶元素，还是正常栈中的最小元素
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 topVal = minStack.peek();if(val <= topVal) {minStack.push(val);}}}public void pop() {int topVal = stack.peek();if(topVal == minStack.peek()) {minStack.pop();}stack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}
