1. Toy模板网首页
  2. > Toy博客

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

9月前 作者：JavaLearnerZGQ 分类：Toy博客 阅读(42) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】7、队列（Queue）的实现【用栈实现队列】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、队列介绍

☘️ 队列（Queue）是一种特殊的线性表，只能在头尾两端进行操作
🎁 队尾（rear）：只能从队尾添加元素，一般叫做 enQueue，入队
🎁 队头（front）：只能从队头移除元素，一般叫做 deQueue，出队
🎁 先进先出的原则，First In First Out，FIFO

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

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

二、使用 LinkedList 实现队列

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

/**
 * 利用动态数组实现栈
 */
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 弹出栈顶元素

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

(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 的简称
【数据结构与算法】7、队列（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) 分析

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

☘️ 队列底层也可以使用动态数组实现，并且各项接口也可以优化到 O(1) 的时间复杂度
☘️ 用数组实现并且优化之后的队列也叫做：循环队列（Circle Queue）

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

(2) 入队

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

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

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

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

(3) 出队

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

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

(4) 动态扩容

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

① 我自己的垃圾实现

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

    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

略…文章来源地址https://www.toymoban.com/news/detail-530566.html

到了这里，关于【数据结构与算法】7、队列（Queue）的实现【用栈实现队列】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】数据结构题解（12）[用栈实现队列]

    【LeetCode】数据结构题解（12）[用栈实现队列]

    所属专栏：玩转数据结构题型❤️ 🚀 博主首页：初阳785❤️ 🚀 代码托管：chuyang785❤️ 🚀 感谢大家的支持，您的点赞和关注是对我最大的支持！！！❤️ 🚀 博主也会更加的努力，创作出更优质的博文！！❤️ 🚀 关注我，关注我，关注我，重要的事情说三遍！！！！！

    2024年02月13日
    浏览(42)
  • 《数据结构初阶》用队列实现栈&&用栈实现队列的细致解析

    《数据结构初阶》用队列实现栈&&用栈实现队列的细致解析

    目录 一、⏱️本章重点 二、⏱️队列实现栈 三、⏱️栈实现队列 四、⏱️解题思路总结 用两个队列实现栈 用两个栈实现队列 解题思路总结  我们有两个队列：  入栈数据1、 2、 3 可以将数据入队列至队列一或者队列二。 如何出栈？  但出栈要先出1，怎么办？ 第一步 ：

    2023年04月25日
    浏览(37)
  • 【数据结构】队列篇| 超清晰图解和详解：循环队列模拟、用栈实现队列、用队列实现栈

    【数据结构】队列篇| 超清晰图解和详解：循环队列模拟、用栈实现队列、用队列实现栈

    博主简介： 努力学习的22级计算机科学与技术本科生一枚🌸 博主主页： @是瑶瑶子啦 每日一言🌼: 每一个不曾起舞的日子，都是对生命的辜负。——尼采 🔗622. 设计循环队列 👧🏻 思路： 🍊数据结构： 使用数组为数据结构，且采用牺牲一个空间的方法来包装判空和判满的

    2024年02月11日
    浏览(39)
  • 数据结构刷题训练：用栈实现队列（力扣OJ）

    数据结构刷题训练：用栈实现队列（力扣OJ）

    目录 前言 1. 题目：用栈实现队列 2. 思路 3. 分析  3.1 定义 “ 队列 ”  3.2 创建队列 3.3 入队  3.4 队头数据  3.5 出队  3.6 判空和销毁 4.题解 总结         栈和队列是数据结构中的两个重要概念，它们在算法和程序设计中都有着广泛的应用。本文将带你深入了解如何使用

    2024年02月13日
    浏览(38)
  • 速学数据结构 | 我不允许还有人不会用栈实现队列！

    速学数据结构 | 我不允许还有人不会用栈实现队列！

    🎬 鸽芷咕 ：个人主页  🔥个人专栏 :《Linux深造日志》《C++干货基地》 ⛺️生活的理想，就是为了理想的生活!    🌈 hello！ 各位铁铁们大家好啊，不知道大家对栈和队列的学习都学过了吧？那么用栈来实现队列你会做嘛？    ⛳️ 栈和队列我们前面说了都是一种特殊

    2024年02月02日
    浏览(41)
  • 【数据结构】 队列(Queue)与队列的模拟实现

    【数据结构】 队列(Queue)与队列的模拟实现

    队列 ：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有==先进先出FIFO(FirstIn First Out) ==入队列： 进行插入操作的一端称为 队尾（Tail/Rear） 出队列： 进行删除操作的一端称为 队头（Head/Front） 在Java中， Queue是个接口，底层是通过链表实现

    2024年02月11日
    浏览(49)
  • 【数据结构】队列（Queue）的实现 -- 详解

    【数据结构】队列（Queue）的实现 -- 详解

    1、概念 队列 ：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有 先进先出 FIFO(First In First Out)。 入队列 ：进行 插入 操作的一端称为 队尾 。 出队列 ：进行 删除 操作的一端称为 队头 。 2、结构 （1）队列的顺序存储结构 入队 ，不需要

    2024年02月15日
    浏览(38)

  • 【Golang】实现简单队列(Queue)数据结构

     在计算机科学中，队列是一种特殊的线性数据结构，它遵循FIFO（先进先出）原则。队列中的元素只能从一端（称为队尾或后端）添加，并且只能从另一端（称为队头或前端）移除。这种特性使得队列在许多算法和数据结构中都有广泛的应用，例如操作系统中的任务调度、网

    2024年01月19日
    浏览(39)
  • 【数据结构与算法】C++的STL模板（迭代器iterator、容器vector、队列queue、集合set、映射map）以及算法例题

    【数据结构与算法】C++的STL模板（迭代器iterator、容器vector、队列queue、集合set、映射map）以及算法例题

    更多算法例题链接: 【数据结构与算法】递推法和递归法解题（递归递推算法典型例题） 什么是迭代器(iterator) 迭代器(iterator)的定义： 迭代器是一种检查容器内元素并遍历元素的数据类型。 迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。 容器

    2024年04月14日
    浏览(50)
  • 【数据结构】队列-Queue

    【数据结构】队列-Queue

    ⭐ 作者：小胡_不糊涂 🌱 作者主页：小胡_不糊涂的个人主页 📀 收录专栏：浅谈数据结构 💖 持续更文，关注博主少走弯路，谢谢大家支持 💖 队列： 只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：

    2024年02月08日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包