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

简介: 【数据结构与算法】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 个栈:inStackoutStack

📘入队时,把元素 pushinStack

📘出队

✏️如果 outStack 为空,① 将 inStack 所有元素逐一弹出,pushoutStack;② 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)

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

💴 英文 dequedouble 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

略…

目录
打赏
0
0
0
0
11
分享
相关文章
|
2月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
262 9
|
2月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
42 1
|
2天前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
112 75
|
2天前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
24 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
2天前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
27 9
|
2天前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
22 7
|
16天前
|
【算法】栈
栈相关算法题,供参考,附有链接地址及板书
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
78 5
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等