【数据结构与算法】7、队列（Queue）的实现【用栈实现队列】-阿里云开发者社区

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

2024-03-01 172

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构与算法】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

略…

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

一、队列介绍

二、使用 LinkedList 实现队列

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

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

(2) 实现思路

(3) 代码实现

四、jdk 的 Queue

五、双端队列（Deque）

六、循环队列

(1) 分析

(2) 入队

(3) 出队

(4) 动态扩容

① 我自己的垃圾实现

② 老师的代码实现

(5) 索引映射封装

(6) 循环队列完整代码

七、循环双端队列

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

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

一、队列介绍

二、使用 LinkedList 实现队列

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

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

(2) 实现思路

(3) 代码实现

四、jdk 的 Queue

五、双端队列（Deque）

六、循环队列

(1) 分析

(2) 入队

(3) 出队

(4) 动态扩容

① 我自己的垃圾实现

② 老师的代码实现

(5) 索引映射封装

(6) 循环队列完整代码

七、循环双端队列

热门文章

最新文章

相关课程

相关电子书