详解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<Integer> 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）的特性。由于其特点和操作方式的限制，栈在各种应用场景中发挥着重要的作用。

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

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

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

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

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

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

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

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

二、数据结构：队列

2.1 队列是什么

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

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

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

• 入队：将一个元素添加到队列的队尾。

• 出队：从队列的队头删除一个元素，并返回该元素。

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

2.2 java中的队列

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

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

下面我们详细介绍一下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<String> 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;

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

    public static void main(String[] args) {
        Deque<String> 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;

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

    public static void main(String[] args) {
        Queue<String> 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<Runnable> 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;

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

    public static void main(String[] args) {
        BlockingQueue<String> 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;

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

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

        // 启动多个消费者线程
        for (int i = 0; i < 3; i++) {
            Thread consumer = new Thread(() -> {
                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）是两种常见的数据结构，它们在数据的组织和访问方式上有一些重要的区别。

3.1 数据结构

• 栈：栈是一种后进先出（LIFO）的数据结构，类似于一叠盘子，最后放入的盘子会最先被取出。

• 队列：队列是一种先进先出（FIFO）的数据结构，类似于排队，先来的元素先被处理。

3.2 插入和删除操作

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

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

3.3 访问顺序

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

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

3.4 主要操作

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

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

3.5 底层实现

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

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

四、总结

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

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