系列文章目录
目录
前言
本文介绍了栈的常用方法，栈的模拟实现以及栈的典型应用场景。
一、栈的常用方法
栈是一种特殊的线性表，只允许在固定的一端进行插入和删除操作。先进栈的元素后出栈，后进栈的元素先出栈。常用方法如下：
Stack(): 构造方法；
push(E): E 在栈顶新增一个元素；
pop(): E 取出栈顶元素；
peek(): E 看一下栈顶元素；
empty() 判断栈是否为空；
size(): int 返回栈中元素的个数；
二、栈的模拟实现
栈的底层是一个数组，与顺序表的实现方法类似。
import java.util.Arrays;
public class MyStack {
private int[] elem;
private int usedSize;
private static final int DEFAULT_CAPACITY = 10;
public MyStack(){
this.elem = new int[DEFAULT_CAPACITY];
}
public void push(int val){
if(isFull()){
this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
}
this.elem[usedSize++] = val;
}
private boolean isFull(){
return this.usedSize == this.elem.length;
}
public int pop(){
if(isEmpty()) {
throw new RuntimeException("栈为空");
}
this.usedSize--;
return this.elem[usedSize];
}
public boolean isEmpty(){
return this.usedSize == 0;
}
public int peek(){
return this.elem[usedSize - 1];
}
public int size(){
return this.usedSize;
}
}三、栈的应用场景
1. 将递归转化为循环，例如链表的逆序打印：
递归方式：
public void reversePrint(ListNode head){
if(head != null){
reversePrint(head.next);
System.out.print(head.val + " ");
}
}栈方式：
public void reversePrintByStack(ListNode head){
ListNode cur = head;
Stack<ListNode> stack = new Stack<>();
while(cur != null){
stack.push(cur);
cur = cur.next;
}
while(!stack.isEmpty()){
ListNode top = stack.pop();
System.out.print(top.val + " ");
}
System.out.println();
}2. 括号匹配
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
public boolean isValid(String s) {
char[] sArr = s.toCharArray();
Stack<Character> stack = new Stack<>();
for(char ch : sArr){
if(ch == '(' || ch == '[' || ch == '{'){
stack.push(ch);
}else{
if(stack.isEmpty()) return false;
else{
char c = stack.pop();
if((c == '(' && ch != ')') ||
(c == '[' && ch != ']') ||
(c == '{' && ch != '}')) {
return false;
}
}
}
}
return stack.isEmpty();
}3. 逆波兰表达式
以如下表达式为例：
中缀表达式，即符合我们习惯的表达式，例如：a + b * c + (d * e + f) * g
后缀表达式，即逆波兰表达式，计算机实际运算时采用的表达式，是没有括号的；
中缀表达式转后缀表达式的方法：
先按照运算顺序加括号，例如：((a + (b * c)) + (((d * e) + f) * g))；
再将运算符移到括号后面，去掉所有括号，例如：a b c * + d e * f + g * +；
计算后缀表达式：遍历后续表达式
遇到数字：加入到栈中；
遇到运算符：以 * 为例，弹出栈顶元素存到 right 中，再弹出栈顶元素存到 left 中，运算 left * right，将计算的结果再存到栈中；
最终栈中存的元素就是表达式的结果；
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String s : tokens){
if("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s)){
int right = stack.pop();
int left = stack.pop();
switch(s){
case "+":{
stack.push(left + right); break;
}
case "-":{
stack.push(left - right); break;
}
case "*":{
stack.push(left * right); break;
}
case "/":{
stack.push(left / right); break;
}
}
}else{
int t = Integer.parseInt(s);
stack.push(t);
}
}
return stack.peek();
}4. 判断栈的序列
描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同
public boolean IsPopOrder (int[] pushV, int[] popV) {
Stack<Integer> stack = new Stack<>();
int n = pushV.length;
int j = 0;
for(int i = 0; i < n; i++){
stack.push(pushV[i]);
while(!stack.isEmpty() && popV[j] == stack.peek()){
stack.pop();
j++;
}
}
return stack.isEmpty();
}5. 模拟实现最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内（O(1)时间复杂度）检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
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.isEmpty()){
minStack.push(val);
}else{
int top = minStack.peek();
if(top >= val){
minStack.push(val);
}
}
}
public void pop() {
int val = 0;
if(!stack.isEmpty()){
val = stack.pop();
if(minStack.peek() == val){
minStack.pop();
}
}
}
public int top() {
if(stack.isEmpty()){
return -1;
}
return stack.peek();
}
public int getMin() {
if(minStack.isEmpty()){
return -1;
}
return minStack.peek();
}
}四、虚拟机栈，栈，栈帧的区别
栈：指的是数据结构栈；
虚拟机栈：内存上的一块区域，用于存放方法调用的相关信息，包括局部变量，返回地址等；
栈帧：调用方法时，会在栈上开辟一块空间；