Stack和Queue—模拟实现，实战应用全解析！

news/2025/2/21 5:25:01

各位看官早安午安晚安呀

如果您觉得这篇文章对您有帮助的话

欢迎您一键三连，小编尽全力做到更好
欢迎您分享给更多人哦

大家好，我们今天来学习java数据结构的Stack和Queue（栈和队列）

一：栈

1.1：栈的概念

栈:入口和出口在一个地方（最先进去的只能最后出来）

想要另一端出去的则是队列（后面我会讲解）

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

1.2：模拟实现栈

java">package StackSimulate;

import java.util.Arrays;

public class MyStack {
    private int usedSize;//栈里的有效元素
    //如果我们在栈外就不需要这个变量来访问元素的个数了，应该使用size();
    private int [] elem;//栈底层是由数组实现的，它继承的Vector底层就是数组实现的
    //当然单双链表也可以，但是单链表尾巴进就麻烦了，没有last
    private static final int DEFAULT_CAPACITY = 10;

    public MyStack() {
        this.elem = new int [DEFAULT_CAPACITY];
    }

    //有效元素个数
    public int size(){

        return usedSize;
    }

    //压栈
    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 boolean empty() {
        return usedSize == 0;
    }

    //出栈
    public int pop() {
        if (empty()) {
            throw new EmptyException();
        }
//        usedSize--;  //这一步那个栈顶元素就已经没有了，就像5变成了4，
//        return elem[usedSize]; //这样写其实不好,因为这个元素我们认为没有了，但是你还是要去访问
        int oldVal = elem[usedSize -1];
        usedSize--;
        return oldVal;   //这样好一点，我们把这个元素保存起来了，然后返回
    }

    //返回栈顶元素
    public int peek() {
        if (empty()) {
            throw new EmptyException();
        }
        return elem[usedSize - 1];
    }

}

1.3：模拟栈测试

java">import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(10);
        myStack.push(20);
        myStack.push(66);
        myStack.push(66);
        myStack.push(88);
        myStack.push(99);
        System.out.println(myStack.size());
        System.out.println("=======================");
        System.out.println(myStack.pop());//99
        System.out.println(myStack.pop());//88
        System.out.println(myStack.empty());//false
        System.out.println(myStack.size());//4

        System.out.println(myStack.peek());//66

        System.out.println(myStack.size());//4

        myStack.pop();
        myStack.pop();
        myStack.pop();
        myStack.pop();
        //myStack.pop();//抛出异常

        System.out.println("===================");
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(100);
        stack.push(100);
        stack.push(222);
        stack.push(444);
        stack.push(666);
        System.out.println(stack.peek());//666
        System.out.println(stack);
    }
}

1.4：关于Stack目前的理解

Stack 继承了 Vector ， Vector 和 ArrayList 类似，都是动态的顺序表，不同的是 Vector 是线程安
全的

几张图概括：

队列和栈链式实现最好用双向链表

续：

Stack用顺序表这种结构（底层数组），由于自身的特性完美的避开了数组删除，增加元素的高时间复杂度

1.5：例题讲解

1.5.1将递归转化为循环

比如：逆序打印链表 
java">    // 递归方式
    public static void printList(Node head){
        if(null != head){
            printList(head.next);
            System.out.print(head.val + " ");
        }
    }

    // 循环方式
    public static void printList(Node head){
        if(null == head){
            return;
        }
        Stack<Node> s = new Stack<>();
// 将链表中的结点保存在栈中
        Node cur = head;
        while(null != cur){
            s.push(cur);
            cur = cur.next;
        }

// 将栈中的元素出栈
        while(!s.empty()){
            System.out.print(s.pop().val + " ");
        }
    }

1.5.2：括号匹配

括号匹配 
java">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 =='{'){
                //左括号
                stack.push(ch);
            }else {
                if (stack.empty()) { //判断是否为空，防止栈为空，出现空指针异常
                    return false;
                }
                char top = stack.peek();
                if ((ch == ')' && top == '(') || (ch == ']' && top == '[') || (ch == '}' && top == '{')) {

                    //右括号 
                    stack.pop();
                    continue;//跳过后面的return
                } 
                 return false;
            }
        }
        if(stack.empty()){
            return true;
        }
        return false;
    }
}

1.5.3：逆波兰表达式求值

逆波兰表达式求值

java">class Solution {
    public int evalRPN(String[] tokens) {
        
        Stack <Integer> stack = new Stack<>();
        for(String s:tokens){
            if(isOpreations(s)){
                int ret1 = stack.pop();
                int ret2 = stack.pop();
                switch(s){
                    case "+":{
                        stack.push(ret1 + ret2);
                        break;
                    }
                    case "-":{
                        stack.push(ret2 - ret1);
                        break;
                    }
                    case "*":{
                        stack.push(ret1 * ret2);
                        break;
                    }
                    case "/":{
                        stack.push(ret2 / ret1);
                        break;
                    }
                }
            }else{
                stack.push(Integer.parseInt(s));
            }
        }
        return stack.pop();
    }
    public boolean isOpreations(String s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }
        return false;
    }
}

1.5.4：栈的压入、弹出序列

栈的压入、弹出序列 
java">public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型一维数组 
     * @param popV int整型一维数组 
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushA, int[] popB) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int j = 0;  //记得放外边
        for(int x : pushA){
            stack.push(x);
            while(!stack.empty() && j<popB.length && stack.peek() == popB[j] ){
                //这里一定要判断stack是否为空，你想想，我一直搁着pop，一会就pop完了
                // 最后i到5，j到1，你就算是判断你也stack.peek();就越界了
                // 其实 J < pop.length就够了，（!stack.empty()）相加就加
                stack.pop();
                j++;
            }
        }
        /*
        if(stack.empty()){
            return true;
        }
        return false;
        */
        return stack.empty();
    }
}

1.5.5：最小栈

 最小栈

java">import java.util.*;
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);//不管怎么样你一定要push进去
        if(minStack.empty()){       // 最小栈里面的是空的，这个时候你放进去一个任意数，这个任意数就是最小值
            minStack.push(val);
        }
        if(val <= minStack.peek()){//等于也要加上
            minStack.push(val);
        }
    }
    
    public void pop() {
        if(! stack.empty()){ //根本不用担心minStack会空指针异常，最后Stack和MinStack都会剩下一个元素
            int ret = stack.pop();//不管怎么样你一定要pop出去，除非空指针了
        if( ret == minStack.peek()){//等于也要加上
            minStack.pop();
           }
        }
     }
        
    
    public int top() {
        if(stack.empty()){
            return -1;
        }
        return stack.peek();
    }
    
    public int getMin() {
        if(minStack.empty()){
            return -1;
        }
        return minStack.peek();
    }
}

1.6：栈、虚拟机栈、栈帧有什么区别呢？

栈（Stack）

  1. 定义：栈是一种基本的线性数据结构，它按照后进先出（LIFO, Last In First Out）的原则存储和操作数据。

  2. 特点：

    • 栈中的数据项只能在一端（栈顶）进行插入和删除操作。
    • 栈底固定，栈顶可以动态变化。
    • 栈具有有限的容量，当容量达到上限时，称为栈溢出。
    • 栈的操作简单高效，时间复杂度为O(1)。

  3. 应用场景：栈在多种场景下都有应用，如撤销操作、浏览器的前进后退功能、逆序输出、中缀表达式转换为后缀表达式等。

虚拟机栈（Java Virtual Machine Stack）包含着栈帧

  1. 定义：虚拟机栈是Java虚拟机中用于方法调用和执行的一块特殊作用的内存空间。

  2. 特点：

    • 每个线程在创建时都会创建一个虚拟机栈，该栈是线程私有的。
    • 虚拟机栈中保存着一个个的栈帧（Stack Frame），每个栈帧对应着一次Java方法调用。
    • 虚拟机栈的访问速度仅次于程序计数器，是快速有效的分配存储方式。

栈帧（Stack Frame）

  1. 定义：栈帧也叫过程活动记录，是编译器用来实现过程/函数调用的一种数据结构。

  2. 特点：

    • 每个方法在运行时，JVM都会为其创建一个栈帧，并将该栈帧压入到对应的虚拟机栈中。
    • 当方法调用结束时，该方法对应的栈帧会从虚拟机栈中出栈。
    • 栈帧中包含局部变量表、操作数栈、动态链接（指向运行时常量池的方法引用）、方法返回地址以及一些附加信息。

总之：

二：队列

2.1：队列的概念


在Java中，Queue是个接口，底层是通过链表实现的。（头进尾出或者尾进头出）

2.2.队列的模拟实现

java">public class MyQueue {

    //其实这就是双链表的不同实现方法的名字而已，没啥区别（就是里面的方法不一样罢了）
    //队列和栈里的方法极其相似
    class ListNode{
        int value;//队列里面的有效值
        ListNode pre;//前一个节点的地址
        ListNode next;
        public ListNode(int value) {
            this.value = value;
        }
    }
    ListNode front;  //头结点的地址
    ListNode rear;  //尾巴节点
    int usedSize;

    //尾巴进去
    public void offer(int data){
        ListNode node = new ListNode(data);
        if(rear == null){
            rear = node;
            front = node;
        }else{
            rear.next = node;
            node.pre = rear;
            rear = node;
        }
        usedSize++;
    }

    //头出
    public int poll(){
        if(front == null){
            throw new NullPointerException();
        }
        int ret = front.value;
        if(front == rear){
            front = null;
            rear = null;
        }else{
            front = front.next;
            front.pre = null;
        }
        usedSize--;
        return ret; //这里一定不能写front.value！！！
    }

    public int size(){
        return usedSize;
    }
    public int peek(){
        if(front == null){
            throw new NullPointerException();
        }
        int ret = front.value;
        return ret;
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }
}

2.3.模拟队列测试：

java">public class Test {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(10);
        myQueue.offer(20);
        myQueue.offer(66);
        myQueue.offer(77);
        myQueue.offer(99);

        System.out.println(myQueue.peek());//10
        System.out.println(myQueue.poll());//10
        System.out.println(myQueue.peek());//20

        System.out.println("=================");

        System.out.println(myQueue.size());//4
        myQueue.poll();
        myQueue.poll();
        System.out.println(myQueue.isEmpty());//是否为空,false
        myQueue.poll();
        myQueue.poll();
        System.out.println(myQueue.isEmpty());//是否为空,true

        //myQueue.poll();//空指针异常
}
}

2.4.队列的方法的一些区别

队列的offer和add的区别在哪里？

1.返回值：
offer(E e): 返回boolean类型。如果元素成功被添加到队列中，则返回true；如果队列已满（对于某些有界队列），则返回false。
add(E e): 也返回boolean类型。如果元素成功被添加到队列中，则返回true。但如果队列已满（对于某些有界队列），则会抛出IllegalStateException异常。（）
异常处理：
offer(E e): 不会抛出异常，总是返回true或false来表示操作是否成功。
add(E e): 在队列已满的情况下会抛出IllegalStateException，不返回false。
使用场景：
offer(E e): 更常用于需要检查队列是否已满而不想处理异常的情况。
add(E e): 更适合在需要确保元素一定被添加且队列容量足够时使用，因为它在无法添加元素时会通过异常来通知调用者。

IllegalStateException：

 IllegalStateException：是 Java 中的一个运行时异常（RuntimeException 的子类），它表明某个应用程序对象当前处于不适当的状态，因此无法执行请求的操作。这个异常通常不是由系统抛出，而是由程序员在代码中显式地抛出。（譬如如果尝试在一个已经关闭的文件流上写入数据，可能会抛出 IllegalStateException。）

poll和remove方法的区别？

  • poll（）方法：队列为空时不会抛出异常，总是返回null或移除的元素。
  • remove()方法：在队列为空时会抛出NoSuchElementException异常。

peek()和element（）方法的区别?

  • peek（）方法：队列为空时不会抛出异常，总是返回null或队顶的元素。
  • element（）方法：在队列为空时会抛出NoSuchElementException异常。

NoSuchElementException异常：

这个异常通常在尝试访问某个不存在的元素时抛出，尤其是在使用迭代器（Iterator）、列表迭代器（ListIterator）、队列（Queue）等集合框架中的组件时。

Stack：可以本身就用new一个Stack这个结构，也可以用LinkedList（链式队列），ArrayDueue（双端队列）(底层是数组）。

Queue和Dueue：底层就是LinkedList，所以用LinkedList实现这两种结构都没问题，当然new一个ArrayDueue也完全没问题。

底层是数组的：可以是顺序表，栈，队列，双端队列

底层是链表的：单双链表，栈，队列，双端队列

2.4 循环队列（上面说的用数组实现）

设计循环队列

实际中我们有时还会使用一种队列叫循环队列，环形队列通常使用数组实现。 （队列的数组实现还有ArrayDueue哦（双端队列））
代码实现（以及注解和图形理解） 
java">class MyCircularQueue {
    int front;
    int rear;
    int[] elem;

    public MyCircularQueue(int k) {
        elem = new int[k + 1];
    }
    //向循环队列插入一个元素。如果成功插入则返回真。
    public boolean enQueue(int value) {
       if(isFull()){  //插入元素，应该是rear出发，
        return false;
       }
       elem[rear] = value;
       rear = (rear +1) % elem.length;
       return true;
    }
    //从循环队列中删除一个元素。如果成功删除则返回真。
    public boolean deQueue() { 
         if(isEmpty()){ 
            return false;
        }
        front =  (front + 1) % elem.length;//我这个是为了防止本来在 7位置，你突然++ 就变成8了，但是我这个数组根本没有这个下标
        return true;
    }
    //返回队首元素
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return elem[front];  //这个front下标一直都有元素
    }
    //返回队尾元素
    public int Rear() {  //rear下标一直没有元素，返回上一个下标的元素。
        if(isEmpty()){
            return -1;
        }
        if(rear == 0){
            int cur = 0;
            cur = elem.length -1;
            return elem[cur];
        }
        return elem[rear -1];
    }
    //判断是否为空
    public boolean isEmpty() {
        return front == rear;
    }
    //判断是否满了
    public boolean isFull() {
        return (rear + 1) % elem.length == front;   // 这里可不是rear + 1 == front，一定要%elem.length
    }
}

图解：

三. 双端队列 (Deque)

双端队列（ deque ）是指允许两端都可以进行入队和出队操作的队列， deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队
在实际工程中，使用 Deque 接口是比较多的，栈和队列均可以使用该接口 
java">        Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现(直接当成栈就完全没问题
        //毕竟你两边都能进出嘛
        stack.push(1);
        
        Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

        Deque<Integer> stack1 = new LinkedList<>();//栈来玩玩啦，队列也可以
        //这里一定要注意，这里并不是栈本身的结构，只是这个名字(这里你可别new 一个Stack了，没实现这个接口）

四. 总结

1.Stack：可以本身就用new一个Stack这个结构，也可以用LinkedList（链式队列），ArrayDueue（双端队列）(底层是数组）。

2.Queue和Dueue：底层就是LinkedList，所以用LinkedList实现这两种结构都没问题，当然new一个ArrayDueue（双端队列，底层是数组）也完全没问题。

1.底层是数组的：可以是顺序表，栈，队列，双端队列

2.底层是链表的：单双链表，栈，队列，双端队列

上述就是Stack，Queue—模拟实现，实战应用全解析！的全部内容了，能看到这里相信您一定对小编的文章有了一定的认可，数据结构的出现让我们对于数据的组织的利用有了更加方便的使用~~

有什么问题欢迎各位大佬指出
欢迎各位大佬评论区留言修正

您的支持就是我最大的动力​​​！！！！


http://www.niftyadmin.cn/n/5860209.html

相关文章

c/c++蓝桥杯经典编程题100道（23）最小生成树

c/c++蓝桥杯经典编程题100道（23）最小生成树

最小生成树&#xff08;MST&#xff09;问题 ->返回c/c蓝桥杯经典编程题100道-目录 目录 最小生成树&#xff08;MST&#xff09;问题 一、题型解释 二、例题问题描述 三、C语言实现 解法1&#xff1a;Kruskal算法&#xff08;基于并查集&#xff0c;难度★★★&#…
阅读更多...
Linux System V - 消息队列与责任链模式

Linux System V - 消息队列与责任链模式

概念 消息队列是一种以消息为单位的进程间通信机制&#xff0c;允许一个或多个进程向队列中发送消息&#xff0c;同时允许一个或多个进程从队列中接收消息。消息队列由内核维护&#xff0c;具有以下特点&#xff1a; 异步通信&#xff1a;发送方和接收方不需要同时运行&#x…
阅读更多...
58同城深度学习推理平台：基于Istio的云原生网关实践解析

58同城深度学习推理平台：基于Istio的云原生网关实践解析

在当今数字化时代&#xff0c;深度学习技术的快速发展为各行各业带来了革命性的变化。作为国内领先的分类信息网站&#xff0c;58同城一直致力于通过技术创新提升服务质量和用户体验。近期&#xff0c;58同城AI Lab推出了一项重要的技术革新——基于Istio的云原生网关深度学习推…
阅读更多...
用DeepSeek来帮助学习three.js加载3D太极模形

用DeepSeek来帮助学习three.js加载3D太极模形

画一个平面的太极图是很容易&#xff0c;要实现3D的应该会很难 一、参考3D模形效果 看某网页看到一个效果&#xff0c;像一个3D太极球&#xff0c;觉得挺有趣&#xff0c;挺解压的&#xff0c;想进一步去了解下这是如何实现 效果&#xff1a; 链接地址&#xff1a; http://www.…
阅读更多...
python：多重继承、MRO（方法解析顺序）

python：多重继承、MRO（方法解析顺序）

在 Python 中&#xff0c;当类存在多重继承时&#xff0c;方法的调用顺序由 方法解析顺序&#xff08;Method Resolution Order, MRO&#xff09; 决定。 Python 使用 C3线性化算法 来确定类的继承顺序&#xff08;MRO&#xff09;&#xff0c;其核心规则是&#xff1a; 子类优…
阅读更多...
第六届全球数据库大赛：PolarDB TPC-C性能优化挑战赛方案分享（一）--参数调优

第六届全球数据库大赛：PolarDB TPC-C性能优化挑战赛方案分享（一）--参数调优

文章目录 前言一、基本参数二、提分参数三、关键参数四、遗漏参数总结前言 今年由于阿里承办了全国大学生计算机系统能力大赛PolarDB数据库创新设计赛，本以为数据库大赛会取消，直到十一左右比赛才姗姗来迟，所以赛程较往年缩短了一个月左右，初赛和复赛都只有一个月时间，时…
阅读更多...
跟着 Lua 5.1 官方参考文档学习 Lua (5)

跟着 Lua 5.1 官方参考文档学习 Lua (5)

文章目录 2.10 – Garbage Collection2.10.1 – Garbage-Collection Metamethods2.10.2 – Weak Tables 2.10 – Garbage Collection Lua performs automatic memory management. This means that you have to worry neither about allocating memory for new objects nor abo…
阅读更多...
如何调用 DeepSeek API：详细教程与示例

如何调用 DeepSeek API：详细教程与示例

目录 一、准备工作 二、DeepSeek API 调用步骤 1. 选择 API 端点 2. 构建 API 请求 3. 发送请求并处理响应 三、Python 示例&#xff1a;调用 DeepSeek API 1. 安装依赖 2. 编写代码 3. 运行代码 四、常见问题及解决方法 1. API 调用返回 401 错误 2. API 调用返回…
阅读更多...
最新文章

Copyright @ 2022~2023