Java_栈(Stack)详解

2023-12-15 14:53:38

前言

栈(Stack)

栈的概念?

前言

栈的图文详解，栈的使用，栈的相关题型，栈的OJ题

栈(Stack)

栈的概念?

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

压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。

出栈：栈的删除操作叫做出栈。 出数据在栈顶 。?

栈的使用

?注意 peek和pop的区别：

pop是取出最后压入的元素，也就是用完后删除

peek则是获取最后压入的元素，并不会删除

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());
    }
}

栈的相关题型?

做题是巩固知识和深入理解的好办法

选择题?

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 2

2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）。

A: 12345ABCDE ????????B: EDCBA54321 ????????C: ABCDE12345 ????????D: 54321EDCBA

答案：

1. C? 解析：“进栈过程中可以出栈” 的意思就是可以一边入栈一边出栈例如 A入栈之后可以马上取出A? ? ? ? ?

2. B? 解析：“依次入栈，然后再依次出栈”?

OJ题

链接：有效的括号

提示：用栈的性质来做?

我们可以试着先自己做，多思考

解析?

代码实现

class Solution {
    public boolean isValid(String s) {
        Stack<Character> test = new Stack<>();//定义一个存储字符的栈
        for (int i = 0; i < s.length(); i++) {//遍历字符串
            char cmp = s.charAt(i);
            if (cmp == '(' || cmp == '[' || cmp == '{') {//左括号就压栈
                test.push(cmp);
            }else if (cmp == ')') {
                if (test.isEmpty()) {//栈中为空就返回false
                    return false;
                }
                if (test.pop() != '(') {//栈顶部不是相对应的左括号也返回false
                    return false;
                }
            }else if (cmp == ']') {
                if (test.isEmpty()) {
                    return false;
                }
                if (test.pop() != '[') {
                    return false;
                }
            }else if (cmp == '}') {
                if (test.isEmpty()) {
                    return false;
                }
                if (test.pop() != '{') {
                    return false;
                }
            }
        }
        if (!test.isEmpty()) {
            return false;
        }
        return true;//上面全是false的所有情况，都不满足的话，那就是true
    }
}