AI 助理
备案控制台
开发者社区 人工智能 文章 正文

【数据结构与算法】7、队列（Queue）的实现【用栈实现队列】

2024-03-01 73
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构与算法】7、队列（Queue）的实现【用栈实现队列】


一、队列介绍

☘️ 队列（Queue）是一种特殊的线性表，只能在头尾两端进行操作

🎁 队尾（rear）：只能从队尾添加元素，一般叫做 enQueue，入队

🎁 队头（front）：只能从队头移除元素，一般叫做 deQueue，出队

🎁 先进先出的原则，First In First Out，FIFO

二、使用 LinkedList 实现队列

/**
 * 利用动态数组实现栈
 */
public class Queue<E> {
    // 通过【组合】的方式使用 LinkedList
    private final List<E> list = new LinkedList<>();
    /**
     * 获取队列中的元素个数
     */
    public int size() {
        return list.size();
    }
    /**
     * 判断队列中是否一个元素都没有（判断是否是一个空队列）
     */
    public boolean isEmpty() {
        return list.isEmpty();
    }
    /**
     * 往队列中添加元素（入队）
     */
    public void enQueue(E element) {
        list.add(0, element);
    }
    /**
     * 取出队首元素, 并删之（出队）
     *
     * @return 队首元素
     */
    public E deQueue() {
        return list.remove(size() - 1);
    }
    /**
     * 获取队列的头元素
     */
    public E front() {
        return list.get(size() - 1);
    }
    /**
     * 清空队列
     */
    public void clear() {
        list.clear();
    }
}

☘️ 队列内部的实现可以直接利用动态数组和链表

☘️ 优先使用双向链表。① 队列主要是往头尾两端操作元素；② 双向链表由于有头指针 first 和尾指针 last 的存在，在头尾进行元素操作都是 O(1) 的复杂度

三、LeetCode：用【栈】实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/

(1) 老师讲之前我自己的实现（Correct）

🍃 代码是正确的，通过了 LeetCode 的检查

public class MyQueue {
    private Stack<Integer> stackLeft = new Stack<>(); // 左栈
    private Stack<Integer> stackRight = new Stack<>(); // 右栈
    /**
     * 构造方法
     */
    public MyQueue() {
    }
    /**
     * 入队
     */
    public void push(int x) {
        stackLeft.push(x);
    }
    /**
     * 出队
     */
    public int pop() {
        // 先把【左栈】的元素全部出栈并入栈到【右栈】中
        while (!stackLeft.isEmpty()) {
            stackRight.push(stackLeft.pop());
        }
        Integer elem = stackRight.pop();
        // 把【右栈】元素放入【左栈】
        while (!stackRight.isEmpty()) {
            stackLeft.push(stackRight.pop());
        }
        return elem;
    }
    /**
     * 返回队首元素
     */
    public int peek() {
        // 先把【左栈】的元素全部出栈并入栈到【右栈】中
        while (!stackLeft.isEmpty()) {
            stackRight.push(stackLeft.pop());
        }
        Integer elem = stackRight.peek();
        // 把【右栈】元素放入【左栈】
        while (!stackRight.isEmpty()) {
            stackLeft.push(stackRight.pop());
        }
        return elem;
    }
    public boolean empty() {
        return stackLeft.isEmpty();
    }
}
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

(2) 实现思路

📖 准备 2 个栈：inStack、outStack

📘入队时，把元素 push 到 inStack 中

📘出队时

✏️如果 outStack 为空，① 将 inStack 所有元素逐一弹出，push 到 outStack；② outStack 弹出栈顶元素

✏️如果 outStack 不为空， outStack 弹出栈顶元素

(3) 代码实现

public class MyQueue {
    // 入队时, 往 inStack 插入元素
    private Stack<Integer> inStack = new Stack<>();
    private Stack<Integer> outStack = new Stack<>();
    /**
     * 构造方法
     */
    public MyQueue() {
    }
    /**
     * 入队（只要是入队, 就往 inStack 插入元素）
     */
    public void push(int x) {
        inStack.push(x);
    }
    /**
     * 出队
     */
    public int pop() {
        if (outStack.isEmpty()) { // 如果 outStack 为空
            // 将 inStack 所有元素逐一弹出, push 到 outStack 中
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }
    /**
     * 返回队首元素
     */
    public int peek() {
        if (outStack.isEmpty()) { // 如果 outStack 为空
            // 将 inStack 所有元素逐一弹出, push 到 outStack 中
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

四、jdk 的 Queue

☘️ offer()：入队

☘️ poll()：出队

☘️ peek()：返回队头元素

☘️ jdk 的 Queue 底层也是 LinkedList

五、双端队列（Deque）

💴 双端队列是能在头尾两端添加、删除的队列

💴 英文 deque 是 double ended queue 的简称

☆ 队尾是链表的末尾

☆ 队头是链表的第一个元素

/**
 * 双端队列
 */
public class Deque<E> {
    private final List<E> linkedList;
    public Deque() {
        this.linkedList = new LinkedList<>();
    }
    public int size() {
        return linkedList.size();
    }
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }
    public void clear() {
        linkedList.clear();
    }
    /**
     * 从队尾入队
     */
    public void enQueueRear(E element) {
        linkedList.add(element);
    }
    /**
     * 从队头入队
     */
    public void enQueueFront(E element) {
        linkedList.add(0, element);
    }
    /**
     * 从队头出队
     */
    public E deQueueFront() {
        return linkedList.remove(0);
    }
    /**
     * 从队尾出队
     */
    public E deQueueRear() {
        return linkedList.remove(size() - 1);
    }
    /**
     * 获取队列的头元素
     */
    public E front() {
        return linkedList.get(0);
    }
    /**
     * 获取队列的【尾】元素
     */
    public E rear() {
        return linkedList.get(size() - 1);
    }
}

六、循环队列

(1) 分析

☘️ 队列底层也可以使用动态数组实现，并且各项接口也可以优化到 O(1) 的时间复杂度

☘️ 用数组实现并且优化之后的队列也叫做：循环队列（Circle Queue）

☘️ 循环双端队列：可以进行两端添加、删除操作的循环队列

(2) 入队

/**
   * 往队列中添加元素（入队）
   */
  public void enQueue(E element) {
      elements[(front + size) % elements.length] = element;
      size++;
  }

(3) 出队

/**
   * 取出队首元素, 并删之（出队）
   *
   * @return 队首元素
   */
  public E deQueue() {
      E frontElem = elements[front];
      elements[front] = null;
      front = (front + 1) % elements.length;
      size--;
      return frontElem;
  }

(4) 动态扩容

① 我自己的垃圾实现

🍀 也是能够满足要求的，但代码效率不行 😪

private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        // 如果所需容量足够, 则不扩容
        if (oldCapacity >= capacity) return;
        // 申请全新的数组空间（新容量是旧容量的 1.5 倍）
        capacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[capacity];
        // 把旧数组中的数据复制到新数组中
        int index = 0;
        int flagSize = 0;
        E[] oldElements = this.elements;
        while (!this.isEmpty()) {
            E e = this.deQueue();
            flagSize++;
            newElements[index] = e;
            index++;
        }
        // elements 指针指向新数组
        this.elements = newElements;
        // 队头 front 指向 0
        front = 0;
        size = flagSize;
        System.out.println(oldCapacity + "扩容为" + capacity);
    }

② 老师的代码实现

private void ensureCapacity(int capacity) {
     int oldCapacity = elements.length;
     // 如果所需容量足够, 则不扩容
     if (oldCapacity >= capacity) return;
     // 申请全新的数组空间（新容量是旧容量的 1.5 倍）
     capacity = oldCapacity + (oldCapacity >> 1);
     E[] newElements = (E[]) new Object[capacity];
     for (int i = 0; i < size; i++) {
         newElements[i] = elements[(i + front) % elements.length];
     }
     // elements 指针指向新数组
     this.elements = newElements;
     // 队头 front 指向 0
     front = 0;
     System.out.println(oldCapacity + "扩容为" + capacity);
 }

(5) 索引映射封装

public int realIndex(int index) {
      return (front + index) % elements.length;
  }

(6) 循环队列完整代码

/**
 * 循环队列
 */
@SuppressWarnings("all")
public class CircleQueue<E> {
    private int front; // 记录着队头元素的下标
    private int size;
    private E[] elements;
    public static final int DEFAULT_CAPACITY = 10;
    public CircleQueue(int capacity) {
        capacity = (capacity > DEFAULT_CAPACITY) ? capacity : DEFAULT_CAPACITY;
        elements = (E[]) new Object[capacity];
    }
    public CircleQueue() {
        this(DEFAULT_CAPACITY);
    }
    /**
     * 获取队列中的元素个数
     */
    public int size() {
        return size;
    }
    /**
     * 判断队列中是否一个元素都没有（判断是否是一个空队列）
     */
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * 获取队列的头元素
     */
    public E front() {
        return elements[front];
    }
    /**
     * 往队列中添加元素（入队）
     */
    public void enQueue(E element) {
        // 扩容检测
        ensureCapacity(size + 1);
        elements[realIndex(size)] = element;
        size++;
    }
    /**
     * 我自己的垃圾实现
     */
//    private void ensureCapacity(int capacity) {
//        int oldCapacity = elements.length;
//        // 如果所需容量足够, 则不扩容
//        if (oldCapacity >= capacity) return;
//
//        // 申请全新的数组空间（新容量是旧容量的 1.5 倍）
//        capacity = oldCapacity + (oldCapacity >> 1);
//        E[] newElements = (E[]) new Object[capacity];
//
//        // 把旧数组中的数据复制到新数组中
//        int index = 0;
//        int flagSize = 0;
//        E[] oldElements = this.elements;
//        while (!this.isEmpty()) {
//            E e = this.deQueue();
//            flagSize++;
//            newElements[index] = e;
//            index++;
//        }
//
//        // elements 指针指向新数组
//        this.elements = newElements;
//        // 队头 front 指向 0
//        front = 0;
//        size = flagSize;
//
//        System.out.println(oldCapacity + "扩容为: " + capacity);
//    }
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        // 如果所需容量足够, 则不扩容
        if (oldCapacity >= capacity) return;
        // 申请全新的数组空间（新容量是旧容量的 1.5 倍）
        capacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[capacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[realIndex(i)];
        }
        // elements 指针指向新数组
        this.elements = newElements;
        // 队头 front 指向 0
        front = 0;
        System.out.println(oldCapacity + "扩容为" + capacity);
    }
    private void print(String s, E[] es) {
        System.out.println("s = " + s);
        for (E e : es) {
            System.out.println(e);
        }
        System.out.println("s = " + s);
    }
    /**
     * 取出队首元素, 并删之（出队）
     *
     * @return 队首元素
     */
    public E deQueue() {
        E frontElem = elements[front];
        elements[front] = null;
        front = realIndex(1);
        size--;
        return frontElem;
    }
    /**
     * 清空队列
     */
    public void clear() {
        for (E element : elements) {
            element = null;
        }
        size = 0;
        front = 0;
    }
    public int realIndex(int index) {
        return (front + index) % elements.length;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{size=").append(size).
            append(", capacity=").append(elements.length).
            append(", [");
        for (int i = 0; i < elements.length; i++) {
            // 不是第 0 个元素就拼接【, 】
            if (i != 0) {
                sb.append(", ");
            }
            sb.append(elements[i]);
        }
        sb.append("]}");
        return sb.toString();
    }
}

七、循环双端队列

☘️ 用数组实现并且优化之后的队列也叫做：循环队列（Circle Queue）

🍀 循环双端队列不需要存在一个叫做 rear 的变量来存储队尾元素的下标

🍃 队尾元素的下标: front + size - 1

略…

文章标签：
算法
Java
索引
存储
关键词：
数据结构栈
数据结构队列
算法队列
数据结构与算法队列
数据结构与算法栈
张思睿ZGQ
目录
相关文章
ephemerals__
|
14天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
那年春天
|
5天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
14 1
德国都芳最好
|
8天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
46 21
html的七十二变
|
11天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
24 2
dufadayang
|
13天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
40 4
肾透侧视攻城狮
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
17 1
简简单单做算法
|
24天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中，通过游戏理论优化动态频谱访问，提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本：Matlab 2022a。完整代码包含详细中文注释和操作视频。
简简单单做算法
39 2
简简单单做算法
|
9天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值（FCM）算法的图像分割技术。算法运行效果良好，无水印。使用MATLAB 2022a开发，提供完整代码及中文注释，附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割，适用于灰度和彩色图像，广泛应用于医学影像、遥感图像等领域。
简简单单做算法
41 9
软件算法开发
|
10天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题（JSSP）通过遗传算法（GA）和模拟退火算法（SA）优化多个作业在并行工作中心上的加工顺序和时间，以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试，展示了有效性和可行性。核心程序采用作业列表表示法，结合遗传操作和模拟退火过程，提高算法性能。
软件算法开发
38 9
软件算法开发
|
10天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题（TSP）是一个经典的组合优化问题，目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法（IA）的解决方案，该算法模拟生物免疫系统的运作机制，通过克隆选择、变异和免疫记忆等步骤，有效解决了TSP问题。程序使用MATLAB 2022a版本运行，展示了良好的优化效果。
软件算法开发
28 8

热门文章

最新文章

  • 1
    18 回归算法 - Softmax回归 - 信贷审批案例
  • 2
    [干货]基础机器学习算法
  • 3
    泛型KMP算法
  • 4
    【算法】算法之美—Fire Net
  • 5
    A* + 弗洛伊德 算法 打造 360 向寻路 - [ActionScript3.0]
  • 6
    OneMob（一体传媒）：大数据算法 让营销更精准
  • 7
    Node.js使用jsrsasign实现SHA256withRSA加密算法
  • 8
    算法学习之顺序结构
  • 9
    字符串相似度算法 递归与动态规划求解分析
  • 10
    【算法研究】Bresenham画线算法
  • 1
    数据结构与算法 动态规划(启发式搜索、遗传算法、强化学习待完善)
    98
  • 2
    数据结构与算法 回溯
    35
  • 3
    数据结构与算法 分治
    38
  • 4
    数据结构与算法 搜索（下）
    38
  • 5
    数据结构与算法 搜索（上）
    33
  • 6
    数据结构与算法 搜索
    45
  • 7
    数据结构与算法 排序（下）
    47
  • 8
    数据结构与算法 排序（上）
    53
  • 9
    数据结构与算法 图
    29
  • 10
    数据结构与算法 树（B树，B+树，红黑树待完善）
    57

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 基于深度学习的广告CTR预估算法
  • 解密阿里内部人工智能算法迭代工具AI Boost
  • Apache Flink 流式应用中状态的数据结构定义升级

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云OSS设置跨域访问