【Java数据结构】栈与队列 经典面试题——刷题笔记(上)

简介: 笔记

1. 实现一个最小栈

题目:


30.png


思路:


把题目要求的最小栈内部分为两个栈,一个stack用于储存所有元素,另一个min_stack用于储存最小的元素


压入第一个元素时,这个元素就是当前栈里最小元素,所以不光要压入stack栈中也要压入min_stack栈中

压入第二个元素的时候,要判断这个元素是否小于min_stack里的栈顶元素,如果小于,则将其压入min_stack

总之min_stack栈顶元素要始终保持是栈里最小的元素


删除栈顶元素的时候,除了要弹出stack里的栈顶元素

还要判断这个栈顶元素是否和min_stack栈里的栈顶元素相同,如果相同则要把min_stack栈里的栈顶元素也弹出

因为min_stack只是辅助栈,一个元素如果在储存元素的栈里都没了,辅助栈里怎么能还有呢?


获取栈顶元素就简单了,直接用java自带的方法peek()就好了,只是获取,不操作


检索最小元素就更简单了,min_stack栈是用来干嘛的?

就是用来存最小元素的嘛,直接弹出min_stack栈栈顶元素可以了

这个栈顶元素必然是整个栈里的最小元素

31.gif


实现代码

class MinStack {
    Stack<Integer> stack;
    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{
            if(val <= MinStack.peek())//如果新压入的元素小于辅助栈栈顶元素
            MinStack.push(val);//将新元素压入辅助栈
        }
    }
    public void pop() {
        //如果从普通栈中弹出的元素等于辅助栈的栈顶元素,那么也要将此元素从辅助栈弹出
        if(stack.pop().equals(MinStack.peek())){//这里要用eqauls,不能用==,pop方法和peek方法返回的是一个object类型,也就是两个对象,我们要比较对象的值,如果用==,比较的是对象的地址
            MinStack.pop();//弹出辅助栈栈顶元素
        }
    }
    public int top() {
        if(MinStack.isEmpty()){
            return -1;
        }
        return stack.peek();//查看普通栈栈顶元素
    }
    public int getMin() {
        if(MinStack.isEmpty()){
            return -1;
        }
        return MinStack.peek();//查看辅助栈栈顶元素
    }
}


2. 括号匹配问题


题目:

31.png


思路:


  1. 左括号和右括号是匹配关系,考虑用栈的方法实现
  2. 栈里只放三种左括号
  3. 遍历字符串,遇到左括号,将其入栈遇到右括号,就查看栈顶的左括号,看是否能匹配。如果能匹配上,就将此左括号出栈(删除),如果最后栈为空,那么它是有效的括号,反之不是。

32.png



实现代码

class Solution {
    public boolean isValid(String s) {
        if(s==null||s.length()==0){
            return true;
        }
        //定义一个栈,来存放左括号
        Stack stack = new Stack();
        //遍历字符串
        for(int i =0; i<s.length(); i++){
            //获取当前i小标是一个啥字符
            char ch = s.charAt(i);
            //判断当前的字符是哪个左括号,因为题上说 只有3种左括号。
            if(ch=='('||ch=='['||ch=='{'){
                stack.push(ch);
            }else{
                //进入else 说明当前i下标是一个右括号
                //但是 要判断栈空不空,有可能第一个括号就是右括号
                if(stack.empty()){
                    //说明右括号多了
                    return false;
                }
               //获取栈顶元素,只是查看是否能和读取到的括号匹配,不是出栈
               char tmp = (char)stack.peek();
               if(tmp=='('&& ch == ')'||tmp=='['&& ch == ']'||tmp=='{'&& ch == '}'){
                   //如果有可匹配的,就出栈当前的栈顶的括号
                   stack.pop();
               }else{
                   //说明括号不匹配
                   return false;
               }
            }
        }
        //字符遍历完了,判断栈是否为空
        if(stack.empty()){//如果栈最终为空,说明括号刚好都匹配上了
            return true;
        }else{//左括号多了
            return false;
        }
    }
}

3. 用队列实现栈


题目:

33.png


思路:

栈是先进后出,队列是先进先出,所以这里用两个队列来回倒,从而实现栈

抓住一个关键点,不管入栈还是出栈,都找不为空的队列进行操作

入栈时,找到不为空的队列,从队列尾部插入元素即可,就达到了入栈的效果

出栈时,找到不为空的队列,将size-1个元素加入到另一个空的队列里,然后把这个队列最后一个元素出列,就达到了出栈效果

返回栈顶元素方法与出栈类似(注意,只查看,不删除),不过要设置一个临时变量tmp储存最后出队的那个元素,而且最后出队的这个元素也要继续加入另一个队列,不然就是出栈操作了


34.gif

实现代码:

class MyStack {
    //创建两个队列
    Queue<Integer> que1;
    Queue<Integer> que2;
    public MyStack() {
        que1 = new LinkedList<>();//队列是接口,不能直接实例化
        que2 = new LinkedList<>();//队列是由链表实现的,所以要用链表来实例化队列
    }
    public void push(int x) {
        if(empty()){//一开始两个队列都是空的时候,默认将第一个元素插入到que1中
            que1.offer(x);
        }else{//从第二个元素开始,哪个队列不为空,对哪个队列进行插入操作
            if(que1.isEmpty()){
                que2.offer(x);
            }else{
                que1.offer(x);
            }
        }
    }
    public int pop() {
        if(empty()){
            return -1;
        }
      //出栈也是找哪个队列不为空,就对哪个队列进行操作
        if(que1.isEmpty()){
            int size = que2.size();
            for(int i =0 ; i<size-1 ;i++){
                int tmp = que2.poll();
                que1.offer(tmp);
            }
            return que2.poll();
        }else{
            int size = que1.size();
            for(int i =0 ; i<size-1 ;i++){
                int tmp = que1.poll();
                que2.offer(tmp);
            }
            return que1.poll();
        }
    }
    public int top() {
        if(empty()){
            return -1;
        }
     //查看栈顶元素,和出栈类似,只不过记得把队列最后一个元素继续插入到另一个队列的最后
     //不然就是出栈操作了
        if(que1.isEmpty()){
            int size = que2.size();
            int tmp = -1;
            for(int i =0 ; i<size ;i++){
                tmp = que2.poll();
                que1.offer(tmp);
            }
            return tmp;
        }else{
            int size = que1.size();
            int tmp = -1;
            for(int i =0 ; i<size ;i++){
                tmp = que1.poll();
                que2.offer(tmp);
            }
            return tmp;
        }
    }
    public boolean empty() {
        return que1.isEmpty() &&  que2.isEmpty();
    }
}



相关文章
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
5天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
14 1
|
23天前
|
Java 开发工具 Android开发
Kotlin语法笔记(26) -Kotlin 与 Java 共存(1)
本系列教程笔记详细讲解了Kotlin语法,适合需要深入了解Kotlin的开发者。若需快速学习Kotlin,建议查看“简洁”系列教程。本期重点介绍了Kotlin与Java的共存方式,包括属性、单例对象、默认参数方法、包方法、扩展方法以及内部类和成员的互操作性。通过这些内容,帮助你在项目中更好地结合使用这两种语言。
40 1
|
8天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
11天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
13天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
40 4
|
14天前
|
安全 Java 编译器
Kotlin教程笔记(27) -Kotlin 与 Java 共存(二)
Kotlin教程笔记(27) -Kotlin 与 Java 共存(二)
|
14天前
|
Java 开发工具 Android开发
Kotlin教程笔记(26) -Kotlin 与 Java 共存(一)
Kotlin教程笔记(26) -Kotlin 与 Java 共存(一)
|
14天前
|
Java 编译器 Android开发
Kotlin教程笔记(28) -Kotlin 与 Java 混编
Kotlin教程笔记(28) -Kotlin 与 Java 混编
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!