数据结构第08小节：双端队列

双端队列（deque，double-ended queue）是一种具有队列和栈特性的数据结构，允许在其两端进行插入和删除操作。在Java中，java.util.Deque接口就是双端队列的实现，而ArrayDeque和LinkedList是其中的具体实现类。

下面是一个使用ArrayDeque实现的双端队列的例子，我们将使用它来管理一个在线购物车系统中的商品列表。用户可以从任何一端（前面或后面）添加或移除商品。

java">import java.util.ArrayDeque;
import java.util.Deque;

// 商品类
class Product {
    String name;
    double price;

    public Product(String name, double price) {
        this.name = name;
        this.price = price;
    }

    @Override
    public String toString() {
        return "Product{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }
}

public class ShoppingCart {
    private Deque<Product> cart;

    public ShoppingCart() {
        cart = new ArrayDeque<>();
    }

    // 向购物车尾部添加商品
    public void addProduct(Product product) {
        cart.addLast(product);
    }

    // 向购物车头部添加商品
    public void addFirstProduct(Product product) {
        cart.addFirst(product);
    }

    // 从购物车尾部移除商品
    public Product removeProduct() {
        return cart.pollLast();
    }

    // 从购物车头部移除商品
    public Product removeFirstProduct() {
        return cart.pollFirst();
    }

    // 显示购物车中的所有商品
    public void displayCart() {
        while (!cart.isEmpty()) {
            System.out.println(cart.pollFirst());
        }
    }

    public static void main(String[] args) {
        ShoppingCart cart = new ShoppingCart();

        // 添加商品
        cart.addProduct(new Product("Apple iPhone 13", 999.99));
        cart.addFirstProduct(new Product("Google Pixel 6", 599.99));
        cart.addProduct(new Product("Samsung Galaxy S21", 799.99));

        // 显示购物车内容
        System.out.println("Shopping Cart Contents:");
        cart.displayCart();

        // 移除商品
        System.out.println("\nAfter removing the last item:");
        cart.removeProduct();
        cart.displayCart();

        // 再次移除商品
        System.out.println("\nAfter removing the first item:");
        cart.removeFirstProduct();
        cart.displayCart();
    }
}

在这个例子中：

  • Product 类表示商品，包含名称和价格属性。
  • ShoppingCart 类使用ArrayDeque作为内部数据结构来存储商品。它提供了添加商品到队列尾部或头部的方法，以及从队列尾部或头部移除商品的方法。
  • main 方法创建了一个ShoppingCart对象，添加了一些商品，显示了购物车的内容，然后移除了商品并再次显示购物车的内容。

这个例子展示了如何使用Java中的双端队列来管理一个购物车系统中的商品列表，允许用户从任意一端添加或移除商品，这在许多实际应用场景中都非常有用。

让我们通过一个详细的案例和表格来进一步说明如何使用双端队列（Deque）在Java中管理一个购物车系统。我们将使用ArrayDeque作为我们的双端队列实现，并跟踪购物车中的商品添加和移除操作。

示例代码

java">import java.util.ArrayDeque;
import java.util.Deque;

// 商品类
class Product {
    String name;
    double price;

    public Product(String name, double price) {
        this.name = name;
        this.price = price;
    }

    @Override
    public String toString() {
        return "Product{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }
}

public class ShoppingCart {
    private Deque<Product> cart;

    public ShoppingCart() {
        cart = new ArrayDeque<>();
    }

    // 向购物车尾部添加商品
    public void addProduct(Product product) {
        cart.addLast(product);
    }

    // 向购物车头部添加商品
    public void addFirstProduct(Product product) {
        cart.addFirst(product);
    }

    // 从购物车尾部移除商品
    public Product removeProduct() {
        return cart.pollLast();
    }

    // 从购物车头部移除商品
    public Product removeFirstProduct() {
        return cart.pollFirst();
    }

    // 显示购物车中的所有商品
    public void displayCart() {
        System.out.println("Current Cart Contents:");
        for (Product product : cart) {
            System.out.println(product);
        }
    }

    public static void main(String[] args) {
        ShoppingCart cart = new ShoppingCart();

        // 添加商品到购物车
        cart.addProduct(new Product("Apple iPhone 13", 999.99));
        cart.addFirstProduct(new Product("Google Pixel 6", 599.99));
        cart.addProduct(new Product("Samsung Galaxy S21", 799.99));

        // 显示购物车内容
        cart.displayCart();

        // 移除商品
        System.out.println("\nAfter removing the last item:");
        cart.removeProduct();
        cart.displayCart();

        // 再次移除商品
        System.out.println("\nAfter removing the first item:");
        cart.removeFirstProduct();
        cart.displayCart();
    }
}

表格说明

购物车操作记录
操作描述购物车状态（从左至右为队首至队尾）
初始化创建一个空的购物车[]
添加到队尾（addLast）添加“Apple iPhone 13”[“Apple iPhone 13”]
添加到队首（addFirst）添加“Google Pixel 6”[“Google Pixel 6”, “Apple iPhone 13”]
添加到队尾（addLast）添加“Samsung Galaxy S21”[“Google Pixel 6”, “Apple iPhone 13”, “Samsung Galaxy S21”]
移除队尾（removeLast）移除“Samsung Galaxy S21”[“Google Pixel 6”, “Apple iPhone 13”]
移除队首（removeFirst）移除“Google Pixel 6”[“Apple iPhone 13”]

通过这个案例和表格，我们可以清楚地看到双端队列在购物车管理中的应用：商品可以被添加到队列的任一端，也可以从任一端移除。这种灵活性使得双端队列成为处理双向数据流或需要快速访问两端数据的场景的理想选择。

让我们继续深入探讨双端队列（Deque）的应用，这一次我们将使用它来解决一个常见的编程问题：回文检测。回文是指正读反读都一样的字符串，例如“racecar”。我们将使用双端队列的特性来高效地检查一个给定的字符串是否是回文。

示例代码

java">import java.util.ArrayDeque;
import java.util.Deque;

public class PalindromeChecker {
    public static boolean isPalindrome(String str) {
        Deque<Character> deque = new ArrayDeque<>();

        // 将字符串中的字符添加到双端队列中
        for (char c : str.toLowerCase().toCharArray()) {
            if (Character.isLetter(c)) {
                deque.addLast(c);
            }
        }

        char first, last;
        while (deque.size() > 1) {
            first = deque.removeFirst();
            last = deque.removeLast();

            if (first != last) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String testString = "A man a plan a canal Panama";
        if (isPalindrome(testString)) {
            System.out.println(testString + " is a palindrome.");
        } else {
            System.out.println(testString + " is not a palindrome.");
        }
    }
}

代码解释

在这段代码中，我们定义了一个名为PalindromeChecker的类，其中包含一个静态方法isPalindrome，该方法接受一个字符串参数并返回一个布尔值，指示该字符串是否为回文。

  1. 初始化双端队列：我们使用ArrayDeque作为双端队列的实现，并将其实例化。
  2. 添加字符：遍历输入字符串的每个字符，只将字母字符转换为小写并添加到队列的尾部。
  3. 比较字符：从双端队列的头部和尾部同时移除字符，并比较它们是否相同。如果任何时候两个字符不匹配，那么字符串就不是回文，方法立即返回false。
  4. 结束条件：如果队列中只剩下一个字符或没有字符，则说明字符串是回文，方法返回true。

运行结果

当你运行main方法时，它会检查字符串“A man a plan a canal Panama”是否为回文。由于忽略空格和大小写，这个字符串实际上是一个回文，因此控制台将输出：“A man a plan a canal Panama is a palindrome.”

这个例子展示了如何利用双端队列的特性来简化和优化一些算法，如回文检测，这在实际编程中是非常有用的技巧。

接下来，我们将使用双端队列（Deque）来解决一个有趣的问题：浏览器的历史记录管理。当我们浏览网页时，通常会使用浏览器的前进和后退按钮来在历史记录之间导航。双端队列非常适合模拟这一行为，因为它允许我们在队列的两端高效地添加和移除元素。

示例代码

java">import java.util.ArrayDeque;
import java.util.Deque;

public class BrowserHistory {
    private Deque<String> history;
    private Deque<String> forwardHistory;

    public BrowserHistory() {
        history = new ArrayDeque<>();
        forwardHistory = new ArrayDeque<>();
    }

    // 访问新的网址
    public void visit(String url) {
        history.addLast(url);
        forwardHistory.clear(); // 清空前进历史
    }

    // 返回上一个页面
    public String back() {
        if (history.size() > 1) {
            String currentUrl = history.removeLast();
            forwardHistory.addFirst(currentUrl);
            return history.getLast();
        } else {
            return "No more pages to go back.";
        }
    }

    // 前往下一个页面
    public String forward() {
        if (!forwardHistory.isEmpty()) {
            String nextUrl = forwardHistory.removeFirst();
            history.addLast(nextUrl);
            return nextUrl;
        } else {
            return "No more pages to go forward.";
        }
    }

    public static void main(String[] args) {
        BrowserHistory browser = new BrowserHistory();

        // 访问一些网址
        browser.visit("google.com");
        browser.visit("youtube.com");
        browser.visit("facebook.com");

        // 后退到上一个页面
        System.out.println("Back: " + browser.back());

        // 再次后退
        System.out.println("Back again: " + browser.back());

        // 前进到下一个页面
        System.out.println("Forward: " + browser.forward());
    }
}

表格说明

浏览器历史记录操作记录
操作描述当前页面历史记录（从左至右为最新至最旧）前进历史（从左至右为最近至最远）
初始化创建一个新的浏览器历史管理器N/A[][]
访问（visit）访问“google.com”google.com[“google.com”][]
访问（visit）访问“youtube.com”youtube.com[“google.com”, “youtube.com”][]
访问（visit）访问“facebook.com”facebook.com[“google.com”, “youtube.com”, “facebook.com”][]
后退（back）后退到上一个页面youtube.com[“google.com”, “youtube.com”][“facebook.com”]
后退（back）再次后退google.com[“google.com”][“youtube.com”, “facebook.com”]
前进（forward）前进到下一个页面youtube.com[“google.com”, “youtube.com”][“facebook.com”]

通过这个案例和表格，我们可以看到双端队列如何有效地模拟浏览器的历史记录管理。每当访问一个新的网址时，它会被添加到历史记录的尾部，并清空前进历史。后退操作会从历史记录的尾部移除当前页面并将其添加到前进历史的头部，而前进操作则相反。这种方法保证了高效且直观的网页导航体验。


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

相关文章

电容的作用和应用

电容的作用和应用

电容是一种常见的电子元件&#xff0c;在电路中起着多种重要作用&#xff0c;并广泛应用于各种电子设备和系统中。 一、电容的主要作用 储能&#xff1a;电容的基本作用是储存电荷。当电容两端加上电压时&#xff0c;电容会储存电荷&#xff0c;储存的电荷量与电压成正比。这…
阅读更多...
直播视频怎么录制？让你秒变录制达人

直播视频怎么录制？让你秒变录制达人

随着直播行业的蓬勃发展&#xff0c;越来越多的人开始参与到直播中&#xff0c;分享自己的生活、技能与见解。然而&#xff0c;在直播过程中&#xff0c;有时我们希望能够记录下精彩的瞬间&#xff0c;或是将整个直播内容保存下来以供日后回顾或分享。可是直播视频怎么录制呢&a…
阅读更多...
纯前端低代码开发脚手架 - daelui/molecule

纯前端低代码开发脚手架 - daelui/molecule

daelui/molecule低代码开发脚手架&#xff1a;分子组件开发、预览、打包 页面代码示例、大屏代码示例预览 可开发页面组件 可开发大屏组件 项目git地址&#xff1a;https://gitee.com/daelui/molecule 在线预览&#xff1a;http://www.daelui.com/daelui/molecule/app/index.…
阅读更多...
Docker-自定义镜像发布到DockerHub仓库、阿里云仓库

Docker-自定义镜像发布到DockerHub仓库、阿里云仓库

文章目录 推送镜像DockerHub仓库推送镜像阿里云仓库 更多相关内容可查看 推送镜像DockerHub仓库 在服务器中 使用 docker 登录命令 docker login -u 账户 #enter 后输入密码推送镜像到DockerHub docker push 镜像名:tag但个人不建议推送到DockHub上&#xff0c;毕竟不是咱自…
阅读更多...
Codeforces 220B

Codeforces 220B

传送门 题目大意 给出一个长度为 n n n的序列&#xff0c;进行 m m m次询问。 每次询问区间 [ l , r ] [l,r] [l,r]内&#xff0c;有多少个数字 x x x刚好出现了 x x x次。 思路 枚举右端点 r r r&#xff0c;维护左端点 l l l&#xff0c;设法将 s u m ( l , r ) s u m (…
阅读更多...
Kafka 入门指南

Kafka 入门指南

Kafka 入门指南 简介 Kafka 是一个由 Apache 软件基金会开发的开源流处理平台。它最初由 LinkedIn 开发&#xff0c;并在 2011 年作为开源项目发布。Kafka 是一个分布式、可扩展、高吞吐量的消息队列系统&#xff0c;广泛应用于实时数据流处理场景。 主要概念 1. 主题 (Top…
阅读更多...
51单片机嵌入式开发：STC89C52环境配置到点亮LED

51单片机嵌入式开发：STC89C52环境配置到点亮LED

STC89C52环境配置到点亮LED 1 环境配置1.1 硬件环境1.2 编译环境1.3 烧录环境 2 工程配置2.1 工程框架2.2 工程创建2.3 参数配置 3 点亮一个LED3.1 原理图解读3.2 代码配置3.3 演示 4 总结 1 环境配置 1.1 硬件环境 硬件环境采用“华晴电子”的MINIEL-89C开发板&#xff0c;这…
阅读更多...
高级Redis之HyperLogLog的用法示例

高级Redis之HyperLogLog的用法示例

HyperLogLog是 Redis 提供的一种基数估计算法数据结构&#xff0c;主要用于估算不重复元素的数量。它能够在使用非常少的内存空间的情况下&#xff0c;快速和高效地进行去重计数操作。HyperLogLog 的误差率约为 0.81%&#xff0c;在处理大数据量的场景下非常有用。 例如使用 R…
阅读更多...
最新文章

Copyright @ 2022~2023