详解java中的栈和队列，都在什么场景中使用呢？-每日运维

一、数据结构：栈

1.1 栈是什么

栈（Stack）是一种常见的数据结构，它遵循后进先出（LIFO，Last-In-First-Out）的原则。栈可以看作是一种容器，其中元素的添加和删除操作只能在栈的顶部进行。

在栈中，最后添加的元素是第一个被访问和删除的，而之前添加的元素则被压入栈底，直到栈顶。这就好像在现实生活中，我们将物体放入一堆堆叠的盘子中，只能从盘子的顶部取出或放入物体。

栈的两个主要操作是压栈（Push）和弹栈（Pop）：

压栈：将一个元素添加到栈的顶部。
弹栈：从栈的顶部移除一个元素，并返回该元素。

除了压栈和弹栈操作外，栈还可以提供查看栈顶元素但不移除它的操作（通常称为顶（Top）或峰（Peek）操作），以及判断栈是否为空的操作。

1.2 java中的栈

在Java中，栈（Stack）是一种常用的数据结构，用于存储方法调用和局部变量。

Java提供了Stack类来表示栈数据结构。Stack类是Vector类的子类，继承了Vector类的方法，并添加了一些额外的栈操作方法。

以下是一些常用的Stack类方法：

1.2.1 使用Stack类的示例

示例代码：

import java.util.Stack;

public class StackExample {

    public static void main(String[] args) {
        Stack stack = new Stack();

        // 压栈
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 弹出栈顶元素
        int top = stack.pop();
        System.out.println("弹出栈顶元素: " + top); // 输出：Popped element: 3

        // 查看栈顶元素
        int peeked = stack.peek();
        System.out.println("查看栈顶元素: " + peeked); // 输出：Peeked element: 2

        // 判断栈是否为空
        boolean isEmpty = stack.empty();
        System.out.println("判断栈是否为空? " + isEmpty); // 输出：Is stack empty? false

        // 搜索元素
        int position = stack.search(2);
        System.out.println("搜索元素 2: " + position); // 输出：Position of element 2: 2
    }

}

输出结果：

弹出栈顶元素: 3
查看栈顶元素: 2
判断栈是否为空? false
搜索元素 2: 1

1.3 栈的应用场景

栈（Stack）是一种常见的数据结构，具有后进先出（LIFO，Last-In-First-Out）的特性。由于其特点和操作方式的限制，栈在各种应用场景中发挥着重要的作用。

以下是一些常见的算法中使用栈的情况：

graph LR
A(栈的应用场景) ---> B(方法调用栈)
A(栈的应用场景) ---> C(表达式求值)
A(栈的应用场景) ---> D(括号匹配)
A(栈的应用场景) ---> E(浏览器历史记录栈)
A(栈的应用场景) ---> F(撤销和重做操作)
A(栈的应用场景) ---> G(递归算法)
A(栈的应用场景) ---> H(回文判断)

style B fill:#FFC0CB,stroke:#FFC0CB,stroke-width:2px
style C fill:#FFA07A,stroke:#FFA07A,stroke-width:2px
style D fill:#FFFFE0,stroke:#FFFFE0,stroke-width:2px
style E fill:#98FB98,stroke:#98FB98,stroke-width:2px
style F fill:#ADD8E6,stroke:#ADD8E6,stroke-width:2px
style G fill:#00FFFF,stroke:#00FFFF,stroke-width:2px
style H fill:#E6E6FA,stroke:#E6E6FA,stroke-width:2px

方法调用栈：在程序执行过程中，每个方法的调用和返回都需要使用栈来管理。当一个方法被调用时，其相关信息包括参数、局部变量和返回地址等被压入栈中，方法执行完毕后，栈顶的信息被弹出，程序继续执行调用者方法。

表达式求值：在编译器、解释器和计算器等应用中，栈常用于表达式的求值。例如，中缀表达式转换为后缀表达式时使用栈来存储操作符，并按照优先级进行运算。

括号匹配：在编码中，栈经常用于检查括号是否匹配。当遇到左括号时，将其压入栈中；当遇到右括号时，与栈顶元素进行匹配。如果匹配成功，则弹出栈顶元素；如果遍历结束后栈为空，则表示所有括号匹配成功。

浏览器历史记录栈：在浏览器中，前进和后退功能依赖于栈的数据结构。每当用户浏览新的页面时，当前页面的URL被压入栈中，当用户点击后退按钮时，栈顶的URL被弹出，实现页面的后退操作。

撤销和重做操作：在图形界面应用程序中，撤销和重做功能通常使用栈来实现。每次用户执行操作时，相关的状态信息被压入栈中，撤销操作将栈顶状态弹出，而重做操作将之前撤销的状态重新压入栈中。

递归算法：递归算法是一种通过自身调用来解决问题的算法。在递归过程中，系统使用栈来存储每个递归调用的状态信息，包括参数、局部变量和返回地址等。

回文判断：回文是指正序和逆序读取结果相同的字符串或序列。利用栈的后进先出特性，可以将字符串的字符按顺序压入栈中，然后依次弹出与原字符串比较，以判断是否为回文。

二、数据结构：队列

2.1 队列是什么

队列（Queue）是一种常见的数据结构，它遵循先进先出（FIFO，First-In-First-Out）的原则。队列可以看作是一种容器，其中元素的添加操作只能在一端进行，而元素的删除操作只能在另一端进行。

在队列中，新元素被添加到队列的一端（通常称为队尾），而元素被删除的操作发生在队列的另一端（通常称为队头）。这就好像在现实生活中，人们在超市排队买单，第一个进入队列的人最先离开队列买单。

队列的两个主要操作是入队（Enqueue）和出队（Dequeue）：

入队：将一个元素添加到队列的队尾。
出队：从队列的队头删除一个元素，并返回该元素。

除了入队和出队操作外，队列还可以提供查看队头元素但不移除它的操作（通常称为Front操作），以及判断队列是否为空的操作。

2.2 java中的队列

在Java中，队列（Queue）是一种常见的数据结构，用于实现先进先出（FIFO，First-In-First-Out）的操作。

Java提供了多种队列的实现类，每个实现类都有其特定的用途和性能特点。

graph LR
A(队列实现类) ---> B(LinkedList)
A(队列实现类) ---> C(ArrayDeque)
A(队列实现类) ---> D(PriorityQueue)
A(队列实现类) ---> E(ArrayBlockingQueue)
A(队列实现类) ---> G(LinkedBlockingQueue)
A(队列实现类) ---> H(PriorityBlockingQueue)

style B fill:#FFC0CB,stroke:#FFC0CB,stroke-width:2px
style C fill:#FFA07A,stroke:#FFA07A,stroke-width:2px
style D fill:#FFFFE0,stroke:#FFFFE0,stroke-width:2px
style E fill:#98FB98,stroke:#98FB98,stroke-width:2px
style G fill:#00FFFF,stroke:#00FFFF,stroke-width:2px
style H fill:#E6E6FA,stroke:#E6E6FA,stroke-width:2px

下面我们详细介绍一下Java中的这些队列实现类。

2.2.1. LinkedList：

LinkedList实现了Queue接口，可以用作队列的实现。
它基于双向链表结构，提供了高效的插入和删除操作。
LinkedList可以作为普通队列使用，也可以作为双端队列（Deque）使用。
由于LinkedList是基于链表的，因此在随机访问操作上性能较差。

使用案例：

import java.util.LinkedList;
import java.util.Queue;

/**
 * 模拟排队系统
 * 假设有一个排队系统，需要按照先来先服务的原则处理任务。
 * 新的任务不断加入队尾，处理完一个任务后，从队头取出下一个任务进行处理。
 */
public class DemoLinkedList {

    public static void main(String[] args) {
        Queue queue = new LinkedList();
        queue.add("1号");
        queue.add("2号");
        queue.add("3号");

        // 处理任务...
        while (!queue.isEmpty()) {
            String task = queue.poll();
            System.out.println("处理任务: " + task);
        }
    }

}

输出结果：

处理任务: 1号
处理任务: 2号
处理任务: 3号

2.2.2 ArrayDeque：

ArrayDeque是基于数组实现的双端队列（双向队列），同时也是Queue接口的实现类。
它可以在队列的两端进行插入和删除操作，因此可以用作普通队列或栈。
ArrayDeque相对于LinkedList在插入和删除操作上具有较好的性能。
ArrayDeque不是线程安全的，如果在多线程环境下使用，需要进行适当的同步。

使用案例：

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 浏览器的前进后退功能
 * 
 * 在浏览器中，我们可以通过点击前进和后退按钮在访问历史记录中导航。
 * 使用ArrayDeque可以实现一个简单的浏览器导航功能，将访问的URL依次添加到队列的尾部，然后点击后退按钮时从队列的尾部弹出URL。
 */
public class DemoArrayDeque {

    public static void main(String[] args) {
        Deque history = new ArrayDeque();
        // 用户访问了一些URL
        history.addLast("https://www.example.com/page1");
        history.addLast("https://www.example.com/page2");
        history.addLast("https://www.example.com/page3");

        // 用户点击后退按钮
        String lastVisitedPage = history.removeLast();
        System.out.println("用户点击后退按钮: " + lastVisitedPage);
    }

}

输出结果：

用户点击后退按钮: https://www.example.com/page3

2.2.3 PriorityQueue：

PriorityQueue是一种优先级队列的实现，也是Queue接口的实现类。
它根据元素的优先级进行排序，每次出队操作都会返回最高优先级的元素。
PriorityQueue可以自定义比较器来定义元素的优先级，也可以使用元素的自然顺序。
PriorityQueue的底层实现是二叉堆（binary heap），因此插入和删除操作的时间复杂度为O(logN)。

使用案例：

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 任务调度系统
 * 
 * 假设有一个任务调度系统，每个任务都有不同的优先级。
 * 使用PriorityQueue可以根据任务的优先级进行排序，每次从队列中取出优先级最高的任务进行处理。
 */
public class DemoPriorityQueue {

    public static void main(String[] args) {
        Queue tasks = new PriorityQueue();
        tasks.add("High priority task 1");
        tasks.add("Medium priority task 2");
        tasks.add("Low priority task 3");

        // 处理任务...
        while (!tasks.isEmpty()) {
            String task = tasks.poll();
            System.out.println("处理任务: " + task);
        }
    }

}

输出结果：

处理任务: High priority task 1
处理任务: Low priority task 3
处理任务: Medium priority task 2

2.2.4 ArrayBlockingQueue：

ArrayBlockingQueue是一个基于数组的有界阻塞队列实现，实现了BlockingQueue接口。
它具有固定的容量，并且在队列已满时会阻塞插入操作，直到队列有空闲空间。
ArrayBlockingQueue提供了线程安全的操作，适合于多线程环境下的生产者-消费者模式。

使用案例：

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * 线程池任务队列
 *
 * 在多线程环境下，线程池通常使用一个任务队列来存储待执行的任务。
 * ArrayBlockingQueue可以作为线程池任务队列的实现，限制队列的容量，并提供线程安全的入队和出队操作。
 */
public class DemoArrayBlockingQueue {

    public static void main(String[] args) {
        BlockingQueue taskQueue = new ArrayBlockingQueue(10);
        ExecutorService executor = Executors.newFixedThreadPool(5);

        // 将任务加入线程池
        for (int i = 0; i < 10; i++) {
            taskQueue.add(new Thread());
        }

        // 从队列中取出任务并执行
        while (!taskQueue.isEmpty()) {
            Runnable task = null;
            try {
                task = taskQueue.take();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            executor.execute(task);
        }

        executor.shutdown();
    }

}

2.2.5 LinkedBlockingQueue：

LinkedBlockingQueue是一个基于链表的可选有界或无界阻塞队列实现，实现了BlockingQueue接口。
它可以选择设置容量，如果容量为无界，则可以一直插入元素；如果容量为有界，则在队列已满时会阻塞插入操作。
LinkedBlockingQueue提供了线程安全的操作，适合于多线程环境下的生产者-消费者模式。

使用案例：

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 生产者-消费者模式
 * 
 * 生产者-消费者模式是一个常见的多线程模式，生产者将数据放入队列，消费者从队列中取出数据进行处理。
 * LinkedBlockingQueue可以作为生产者和消费者之间的共享队列，实现线程安全的数据传递。
 */
public class DemoLinkedBlockingQueue {

    public static void main(String[] args) {
        BlockingQueue queue = new LinkedBlockingQueue();

        // 生产者线程
        Thread producer = new Thread(() -> {
            try {
                queue.put("Data 1");
                queue.put("Data 2");
                queue.put("Data 3");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        // 消费者线程
        Thread consumer = new Thread(() -> {
            try {
                while (true) {
                    String data = queue.take();
                    System.out.println("Processing data: " + data);
                    // 处理数据...
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        producer.start();
        consumer.start();
    }

}

2.2.6 PriorityBlockingQueue：

PriorityBlockingQueue是一个基于优先级的无界阻塞队列实现，实现了BlockingQueue接口。
它类似于PriorityQueue，根据元素的优先级进行排序。
PriorityBlockingQueue提供了线程安全的操作，适合于多线程环境下的优先级任务调度。

使用案例：

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.PriorityBlockingQueue;

/**
 * 并发任务调度
 * 
 * 在多线程环境下，使用PriorityBlockingQueue可以实现并发任务调度，
 * 任务根据优先级进行排序，多个线程可以并发地从队列中取出任务进行处理。
 */
public class DemoPriorityBlockingQueue {

    public static void main(String[] args) {
        BlockingQueue tasks = new PriorityBlockingQueue();

        // 启动多个消费者线程
        for (int i = 0; i  {
                try {
                    // 处理任务...
                    while (true) {
                        String task = tasks.take();
                        System.out.println("处理任务: " + task);
                    }
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
            consumer.start();
        }

        // 生产者线程
        Thread producer = new Thread(() -> {
            try {
                tasks.put("High priority task");
                tasks.put("Medium priority task");
                tasks.put("Low priority task");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        producer.start();
    }

}

三、栈和队列的区别

栈（Stack）和队列（Queue）是两种常见的数据结构，它们在数据的组织和访问方式上有一些重要的区别。

graph LR
A(栈和队列的区别) ---> B(数据结构)
A(栈和队列的区别) ---> C(插入和删除操作)
A(栈和队列的区别) ---> D(访问顺序)
A(栈和队列的区别) ---> E(主要操作)
A(栈和队列的区别) ---> G(底层实现)

style B fill:#FFC0CB,stroke:#FFC0CB,stroke-width:2px
style C fill:#FFA07A,stroke:#FFA07A,stroke-width:2px
style D fill:#FFFFE0,stroke:#FFFFE0,stroke-width:2px
style E fill:#98FB98,stroke:#98FB98,stroke-width:2px
style G fill:#00FFFF,stroke:#00FFFF,stroke-width:2px

3.1 数据结构

栈：栈是一种后进先出（LIFO）的数据结构，类似于一叠盘子，最后放入的盘子会最先被取出。
队列：队列是一种先进先出（FIFO）的数据结构，类似于排队，先来的元素先被处理。

3.2 插入和删除操作

栈：栈的插入操作称为推入（push），删除操作称为弹出（pop）。新元素总是被推入到栈的顶部，而弹出操作也总是从栈的顶部删除元素。
队列：队列的插入操作称为入队（enqueue），删除操作称为出队（dequeue）。新元素总是被插入到队列的末尾，而出队操作总是从队列的头部删除元素。

3.3 访问顺序

栈：栈的访问顺序是从栈顶到栈底，最后入栈的元素首先被访问。
队列：队列的访问顺序是从队头到队尾，最先入队的元素首先被访问。

3.4 主要操作

栈：栈主要支持推入元素、弹出元素和查看栈顶元素的操作。
队列：队列主要支持入队元素、出队元素和查看队头元素的操作。

3.5 底层实现

栈：栈可以使用数组或链表来实现，具体实现方式有数组栈、链表栈和双向链表栈等。
队列：队列也可以使用数组或链表来实现，具体实现方式有数组队列、链表队列和双向链表队列等。

四、总结

本文主要详细介绍了两种数据结构：栈和队列。主要介绍了什么是栈和队列，以及java中怎么去实现它的，Java实现类怎么使用也提供了基础案例。

希望我的文章能够给你带来帮助，中秋国庆快乐。

详解java中的栈和队列，都在什么场景中使用呢？

一、数据结构：栈

1.1 栈是什么

1.2 java中的栈

1.2.1 使用Stack类的示例

1.3 栈的应用场景

二、数据结构：队列

2.1 队列是什么

2.2 java中的队列

2.2.1. LinkedList：

2.2.2 ArrayDeque：

2.2.3 PriorityQueue：

2.2.4 ArrayBlockingQueue：

2.2.5 LinkedBlockingQueue：

2.2.6 PriorityBlockingQueue：

三、栈和队列的区别

3.1 数据结构

3.2 插入和删除操作

3.3 访问顺序

3.4 主要操作

3.5 底层实现

四、总结

相关文章

发布评论取消回复

大白菜程序猿

服务器端口转发，带你了解服务器端口转发

百度搜索：蓝易云 – Linux之查看系统性能命令大全

MySQL 主从复制的问题及解决方案

详解java中的栈和队列，都在什么场景中使用呢？

一、数据结构：栈

1.1 栈是什么

1.2 java中的栈

1.2.1 使用Stack类的示例

1.3 栈的应用场景

二、数据结构：队列

2.1 队列是什么

2.2 java中的队列

2.2.1. LinkedList：

2.2.2 ArrayDeque：

2.2.3 PriorityQueue：

2.2.4 ArrayBlockingQueue：

2.2.5 LinkedBlockingQueue：

2.2.6 PriorityBlockingQueue：

三、栈和队列的区别

3.1 数据结构

3.2 插入和删除操作

3.3 访问顺序

3.4 主要操作

3.5 底层实现

四、总结

相关文章

发布评论 取消回复

大白菜程序猿

服务器端口转发，带你了解服务器端口转发

百度搜索：蓝易云 – Linux之查看系统性能命令大全

MySQL 主从复制的问题及解决方案

发布评论取消回复