栈（Stack）

用户11820508

发布于 2026-01-12 15:04:30

120

一.栈（Stack）

1.概念

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出（先进后出） LIFO（Last In First Out）的原则。 压栈（进栈）：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据在栈顶。

栈在我们日常生活中的例子：

2.栈的使用

import java.util.Stack;

public class MyStack {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);//以上为压栈操作
        Integer x = stack.peek();
        System.out.println(x);//获取栈顶元素
        System.out.println(stack.size());//获取栈内有效元素个数
        System.out.println(stack.isEmpty());//检查栈是否为空
        
        Integer y = stack.pop();
        System.out.println(y);//出栈操作
        int z = stack.size();
        System.out.println(z);
    }
}

注意：

我们在判断栈中是否为空时，可以使用栈这个类中的Empty进行判断，也可以使用Vector类当中的isEmpty进行判断，因为Stack类是继承Vector类的

在以上例子中我们进行出栈操作，获取有效元素个数，获取栈顶元素时，我们既可以通过Integer来进行接收，也可以使用int进行拆箱操作来进行接收

3.栈的模拟实现

栈是一个特殊的顺序表,所以采用链表和数组的方式都可实现,但是,一般采用数组的方式实现.
usedSize来表示栈中有效元素个数，入栈一个元素则usedSize++，出栈一个元素则usedSize--，所以此时usedSize有两个含义： ①可以表示当前数据存放的个数 ②表示当前存放数据的下标说明：usedSize初始值为0，我们往栈里添加元素，将元素添加到下标为0的数组中，此时usedSize为0表示当前存放数据的下标，添加1个元素后，进行usedSize++操作，此时usedSize表示当前数据存放的个数 push()入栈：

先判断数组是否满了，若满了则进行扩容
若没满则进行入栈操作，即将元素按顺序添加到数组中，通过usedSize计数下标来进行添加，添加一个元素，下标就往后走一个，直到满了之后进行扩容

pop()出栈：

先判断栈中是否有元素，没有则抛出异常
有元素则进行出栈，我们返回的是栈顶的元素，即usedSize-1的元素即可，通过减少 usedSize 的值，我们实际上是在告诉栈：“我们刚刚移除了一个元素，所以现在的栈比刚才小了一个元素 为什么返回的是useSize-1的值而不是usedSize的值？ 因为在我们进行入栈操作时是先使用的usedSize来表示下标来进行添加元素操作的，添加一个元素usedSize就++，所以此时我们想返回栈顶元素时，栈顶元素的下标就是usedSize-1 如何进行空间释放？ 因为我们栈中的数据时简单类型，只需要将表示数组中元素个数的usedSize--即可，当下一次进行入栈操作时直接将元素覆盖即可，但如果是引用类型的数据则需要进行置空操作

import java.util.Arrays;

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[10];
    }
    public void push(int val){
        if (isFull()) {
            //如果满则进行扩容,此处进行两倍扩容
           elem = Arrays.copyOf(elem,elem.length * 2);
        }
        elem[usedSize] = val;//将元素按顺序进行压栈
        usedSize++;
    }
    public boolean isFull() {
        //判断栈是否满
        return usedSize == elem.length;
    }
    public int pop() {
        //将栈顶元素出栈,要求弹出栈顶上一个元素的值

        //如果usedSize为空则无法抛出
        if (empty()) {
            throw new RuntimeException("栈中没有元素，不能出栈");
        }
        int oldV = elem[usedSize - 1];//存储上一个元素的值
        usedSize--;
        return oldV;
    }
    public boolean empty() {
        return usedSize == 0;
    }
    public int peek() {
        if (empty()) {
            return 0;
        }
        return elem[usedSize - 1];
    }
}

刚刚实现的栈或者说Java集合类的Stack底层是一个数组。这种栈叫做顺序栈（基于数组）!

那栈是否可以使用链表来实现呢，链表实现的栈叫链式栈（基于链表）

如果是单链表那么入栈和出栈最好从链表头部进行入栈出栈。O(1)相反如果从链表的头部或者尾部进行入栈和出栈O(N)

如果是双向链表来实现栈那么复杂度均是O(1)

public static void main(String[] args) {
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.peek());
        stack.pop();
        System.out.println(stack.size());
    }

链栈与顺序栈相比，比较明显的优点是入栈时不需要扩容；

链式结构实现栈时，每次入栈相当于链表中头插一个节点，没有扩容一说

如果是链栈，一般需要进行头插或者头删操作，而顺序栈一般进行尾插和尾删操作，链表的操作比顺序表复杂，因此使用顺序结构实现栈更简单

二.栈相关习题

1.逆波兰表达式求值

（1）链接

逆波兰表达式求值

https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

（2）解析

解题之前我们先理解什么叫中缀表达式和后缀表达式中缀表达式：该表达式就是我们平常学习中常用的表达式，例如：(3 + 4) * 5 它的特点为：

操作符（如加、减、乘、除等）位于操作数之间。
需要括号来改变默认的运算优先级。

后缀表达式（逆波兰表达式）： 例如：3 4 + 5 *（相当于 (3 + 4) * 5，结果是 35）

操作符位于操作数之后。
不需要括号来指明运算优先级，因为操作符的优先级由它们在表达式中的位置决定。

如何将中缀表达式转为后缀表达式呢？ 这里我们通过两个例子来进行演示：

我们将 (3 + 4) * 5 这个中缀表达式转为后缀表达式 ①我们将这个表达式按照先乘除后加减的规则，将表达式中所有的式子加上括号，即： ((3 + 4) * 5) ②将运算符移至当前表达式所在括号的外面，即： ((3 4)+ 5)* ③将所有的括号去掉，即 3 4+ 5* 此时我们就完成了转换
1 +2*3 +(4*5 +6)*7 再来个更复杂的转换

对应转换为种植表达式就是：1 +2*3 +(4*5 +6)*7 = 189

总结：

按照先乘除后加减的规则进行添加括号操作
将运算符移至当前表达式所在括号的外面
将所有的括号去掉

后缀表达式是如何存储到栈中并计算呢？ 是操作数就放入栈中，直到遇到运算符，弹出栈顶的第一个元素作为右操作数，第二个作为左操作数，计算出的结果再放入栈中，重复这一操作即可

（3）题解

class Solution {
    public int evalRPN(String[] tokens) {
        //思路：将数组中的操作数进行压栈操作，当遇到运算符时，则将栈顶元素拿出来作为右操作数，再取一次作为左操作数
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            //操作数和运算符要进行不同的操作
            String tmp = tokens[i];
            if (isoperation(tmp)) {
                //为运算符时，则赋值左右操作数
                Integer val2 = stack.pop();
                Integer val1 = stack.pop();
                //拿出来个操作数后，可能会进行+-*/四个操作
                switch (tmp) {
                    case "+" -> stack.push(val1 + val2);
                    case "-" -> stack.push(val1 - val2);
                    case "*" -> stack.push(val1 * val2);
                    case "/" -> stack.push(val1 / val2);
                }
            }else {
                //为操作数时，，则进行入栈操作
                Integer val = Integer.valueOf(tmp);
                stack.push(val);
            }
        }
        return stack.pop();
    }
    public boolean isoperation(String s) {
        if (s.equals("+") || s.equals("-") ||s.equals("*") || s.equals("/")) {
            return true;
        }else {
            return false;
        }
    }
}

2.括号匹配

（1）链接

括号匹配

https://leetcode.cn/problems/valid-parentheses/description/

（2）解析

分四种情况：

括号匹配的情况下，栈最终为空且字符串已经遍历完成。(){}
左括号和右括号不匹配 (]{}
字符串没有遍历完成，遇到了右括号，但是栈为空。())))
字符串遍历完成，但是栈当中仍然存在左括号。 (()

只有当获取的字符串为左括号时我们才进行入栈操作，当遇到右括号时我们分为两种情况：①当第一个元素就是右括号，此时栈为空，直接返回false即可②如果右括号不是第一个元素，我们就看当前元素是否与栈顶的元素匹配，若匹配则将栈顶的元素出栈，若不匹配则返回false 当整个循环走完，栈为空时则为true 例：())))，栈内不为空则为false 例：()((

（3）题解

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 == '{') {
                //1.为左括号直接入栈
                stack.push(ch);
            }else {
                //2.为右括号时分两种情况：s中第一个元素就是右括号，此时栈为空直接返回false即可
                // 栈内有左括号，依次进行匹配()[]
              if (stack.empty()) {
                  return false;
              }else {
                  char chL = stack.peek();
                  //将栈顶元素与给定的字符串进行匹配,如果匹配那么将栈内与之匹配的左括号进行出栈操作，最终栈内为空则为true
                  if (chL == '(' && ch == ')' || chL == '[' && ch == ']' || chL == '{' && ch == '}') {
                      stack.pop();
                      //这里不能直接返回true，因为栈中可能还有元素
                  }else {
                      //括号与之不匹配(]{]则返回false
                      return false;
                  }
              }
            }
        }
        return stack.empty();
    }
}

3.栈的压入弹出序列

（1）链接

栈的压入弹出序列

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

（2）解析

pushV数组表示压栈后的数组，popV数组表示出栈后的数组可能弹出的顺序

我们先对pushV数组进行遍历，并将该数组中的元素依次压入栈中，每压一次就与popV数组j下标的元素进行比较，比较之后有两种情况： ①若stack中的元素与popV中j下标的元素相同则将栈顶元素进行出栈操作，j++,i++ （popV数组中必须不能为空，j下标不能超过数组的长度，且只有当栈顶元素与popV数组对应的j下标的元素相等时才会进行出栈操作） ②若stack中的元素与popV中j下标的元素不同则i++进行下一次与当前j下标元素的判断（不进入内层循环，直接进行下一次判断）
出栈的过程当中，如果一直是一样的，那么一直出。遇到不一样的。i++继续入栈。
当循环走完，如果popV数组弹出序列是一致的，那么栈此时应该是空的状态，因此我们只需返回stack.empty()即可

（3）题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型一维数组 
     * @param popV int整型一维数组 
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        //1.遍历pushv数组
        for(int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            while(j < popV.length && !stack.empty() && stack.peek() == popV[j]){
                stack.pop();
                j++;
            }
        }
         return stack.empty();
    }
}

4.最小栈

（1）链接

最小栈

https://leetcode.cn/problems/min-stack/

（2）解析

这里我们的设计思路是使用两个栈，第一个普通栈是为了满足top()方法返回栈顶元素；第二个栈为最小栈是为了满足getMin()方法返回栈的最小元素，此时我们限制最小栈入栈的规则，使得栈顶为最小的元素，直接返回最小栈的栈顶元素即可 存放元素push的过程：

如果第一次存放元素，普通栈和最小栈都得存放。
如果不是第一次存放的时候，普通栈肯定得放，但是最小栈我们需要和最小栈的栈顶元素比较，是否比最小栈元素小（小于等于）?只有小了才能放

取元素的过程:pop()

每次pop元素的时候，都需要判断pop的元素是不是和最小栈的栈顶元素一样?一样:最小栈也得pop.

top ==> peek()返回值是普通栈的值 getMin()获取最小栈的栈顶元素

（3）题解

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        //不论是第几次入栈，stack都要入栈
        stack.push(val);
        //最小栈第一次入栈时需要放元素，之后的入栈都需要将val与最小栈的栈顶元素进行比较
        if(minStack.empty()) {
            minStack.push(val);
        }else {
            if(val <= minStack.peek()){
                minStack.push(val);
            }
        }
    }
    
    public void pop() {
        if(stack.empty()) {
            return;
        }
        int popval = stack.pop();
        if(minStack.peek() == popval) {
            minStack.pop();
        }
    }
    
    public int top() {
        if(stack.empty()){
            return -1;
        }
        return stack.peek();
    }
    
    public int getMin() {
        if(minStack.empty()){
            return -1;
        }
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-19，如有侵权请联系 cloudcommunity@tencent.com 删除

链表