初阶数据结构（6）（队列的概念、常用的队列方法、队列模拟实现【用双向链表实现、用数组实现】、双端队列 (Deque)、OJ练习【用队列实现栈、用栈实现队列】）

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

接上次博客初阶数据结构5栈的概念、栈的模拟实现、栈的应用及练习【改变元素的序列 、 将递归转化为循环、括号匹配、逆波兰表达式求值、出栈入栈次序匹配、最小栈】、链栈和顺序栈栈、虚拟机栈、栈帧的区别_di-Dora的博客-CSDN博客

目录

队列(Queue)的概念

 常用的队列方法

队列模拟实现

我们先用双向链表来实现一个吧

现在考虑用数组实现​

双端队列 (Deque)

OJ练习

1、用队列实现栈

2、用栈实现队列

队列(Queue)的概念

队列是一种特殊的线性表它只允许在一端进行插入数据操作而在另一端进行删除数据操作。这个特性使得队列的数据按照先进先出FIFO的顺序进行处理。这意味着最先插入的元素将最先被删除而最后插入的元素将最后被删除。

在队列中进行插入操作的一端称为队尾Tail/Rear新元素将被添加到队尾而进行删除操作的一端称为队头Head/Front最早插入的元素将从队头被删除。

这个过程就好像人们排队等候服务先来的人先被服务后来的人排在队尾等待。

举个例子来说明队列的概念。假设有一个队列初始时队列为空。现在按照顺序依次执行以下操作

  • 将元素A插入队尾。
  • 将元素B插入队尾。
  • 将元素C插入队尾。
  • 删除队头元素。
  • 将元素D插入队尾。
  • 删除队头元素。

在这个过程中元素A首先被插入队尾然后是元素B再然后是元素C。当执行删除操作时队头的元素A被删除。接着元素D被插入队尾然后队头的元素B被删除。

根据队列的特性删除操作总是在队头进行而插入操作总是在队尾进行确保了元素的顺序是先进先出的。

队列在实际应用中具有广泛的应用例如任务调度、消息传递、广度优先搜索等场景都可以使用队列来实现。

 

 在Java中Queue是个接口底层是通过链表实现的

注意Queue是个接口在实例化时必须实例化LinkedList的对象因为LinkedList实现了Queue接口。 

Deque<Integer> queue2 = new LinkedList<>();

Queue<Integer> queue1 = new LinkedList<>();

 常用的队列方法

  • boolean add(E element): 将元素添加到队列的尾部如果队列已满则抛出异常。
  • boolean offer(E element): 将元素添加到队列的尾部如果队列已满则返回false。
  • E remove(): 删除并返回队列头部的元素如果队列为空则抛出异常。
  • E poll(): 删除并返回队列头部的元素如果队列为空则返回null。
  • E element(): 返回队列头部的元素如果队列为空则抛出异常。
  • E peek(): 返回队列头部的元素如果队列为空则返回null。
  • int size(): 返回队列中的元素个数。
  • boolean isEmpty(): 判断队列是否为空。
  • boolean contains(Object element): 判断队列是否包含指定的元素。
  • void clear(): 清空队列中的所有元素。

当然除了上述方法Queue接口还继承了Collection接口中的一些方法如iterator()、addAll(Collection<? extends E> c)等。 

我们可以试验一下这些方法

import java.util.Queue;
import java.util.LinkedList;

public class QueueExample {
    public static void main(String[] args) {
        // 创建一个队列
        Queue<String> queue = new LinkedList<>();

        // 添加元素到队列
        queue.add("Apple");
        queue.offer("Banana");
        queue.offer("Cherry");

        // 删除并返回队列头部的元素
        String removedElement = queue.remove();
        System.out.println("删除的元素: " + removedElement);

        // 返回队列头部的元素
        String head = queue.element();
        System.out.println("队列头部元素: " + head);

        // 判断队列是否为空
        boolean isEmpty = queue.isEmpty();
        System.out.println("队列是否为空: " + isEmpty);

        // 获取队列的大小
        int size = queue.size();
        System.out.println("队列大小: " + size);

        // 遍历队列并打印元素
        System.out.println("队列元素: ");
        for (String fruit : queue) {
            System.out.println(fruit);
        }

        // 判断队列是否包含指定的元素
        boolean containsElement = queue.contains("Banana");
        System.out.println("队列是否包含Banana: " + containsElement);

        // 清空队列
        queue.clear();
        System.out.println("清空后的队列大小: " + queue.size());
    }
}

 你有没有发现最上面的几种方法好像有些功能上是重复的

你可以跳转到源代码去看一看英文的注解

所以我们可以把它们分为两组这两组的差别如下

add(E element)和offer(E element)

add(E element): 将元素添加到队列的尾部。如果队列已满抛出一个IllegalStateException异常。
offer(E element): 将元素添加到队列的尾部。如果队列已满则返回false

区别add()方法在无法添加元素时会抛出异常而offer()方法在无法添加元素时返回false。

remove()和poll()

remove(): 删除并返回队列头部的元素。如果队列为空抛出一个NoSuchElementException异常。
poll(): 删除并返回队列头部的元素。如果队列为空则返回null。
 

区别remove()方法在队列为空时会抛出异常而poll()方法在队列为空时返回null。

element()和peek()

element(): 返回队列头部的元素但不会删除它。如果队列为空则抛出一个NoSuchElementException异常。

peek(): 返回队列头部的元素但不会删除它。如果队列为空则返回null。

区别element()方法在队列为空时会抛出异常而peek()方法在队列为空时返回null。

总体上这三组方法的功能相同不同之处在于在特定情况下的异常处理方式。add()、remove()和element()方法在无法执行操作时会抛出异常而offer()、poll()和peek()方法则会返回特定值来指示操作的成功与否。

队列模拟实现

队列中既然可以存储元素那底层肯定要有能够保存元素的空间我们通过前面线性表的学习了解到常见的空间类型有两种顺序结构 和 链式结构。队列的实现使用顺序结构还是链式结构好

都可以随意选。

我们先用双向链表来实现一个吧

import java.util.List;

/**
 * @Author 12629
 * @Description
 */
public class MyQueue {
    static class ListNode {
        private int val;
        private ListNode prev;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    private ListNode front;//队头
    private ListNode rear;//队尾

    private int usedSize;
 


    //我们和源代码保持一致用头插法
    public void offer(int x) {
        ListNode node = new ListNode(x);
        if(front == null) {
            front = rear = node;
        }else {
            node.next = front;
            front.prev = node;
            front = node;
        }
        usedSize++;
    }

    //出队列 相当于 删除尾节点
    //先进先出
    public int poll() {
        if(front == null) {
            return -1; //抛异常也可以
        }
        int ret = rear.val;
        if(front == rear) {
            front = null;
            rear = null;
            usedSize--;
            return ret;
        }
        rear = rear.prev;
        rear.next = null;
        usedSize--;
        return ret;
    }

    public int peek() {
        if(front == null) {
            return -1;
        }
        return front.val;
    }

    public int getUsedSize() {
        return usedSize;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }
}
    public static void main(String[] args) {
    MyQueue myQueue = new MyQueue();
    myQueue.offer(1);
    myQueue.offer(2);
    myQueue.offer(3);
    myQueue.offer(4);
    // 4   3   2   1

    System.out.println(myQueue.poll());
    System.out.println(myQueue.poll());
    System.out.println(myQueue.poll());
    System.out.println(myQueue.poll());
    System.out.println(myQueue.poll());
    System.out.println(myQueue.poll());
    }

来来来做个选择题看看你是不是理解了

下列关于队列的叙述错误的是( )

A.队列可以使用链表实现

B.队列是一种"先入先出"的数据结构

C.数据出队列时一定只影响队尾引用

D.数据入队列时一定从尾部插入

 答案 C.数据出队列时一定只影响队尾引用

C的说法是错误的。数据出队列时会同时影响队头和队尾引用。

在队列中数据的插入入队列是在队尾进行的而数据的删除出队列是在队头进行的。当数据出队列时队头引用会更新为下一个元素同时队尾引用也可能需要进行更新特别是当队列中只有一个元素时出队列后队尾引用会变为null或者空值。

现在考虑用数组实现

 就像是一个“开心大转盘”或者一个飞镖靶子订奖品的那种

 数组下标循环的小技巧

1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length。

 2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length。

看看掌握程度

现有一循环队列其队头为front队尾为rear循环队列长度为N,最多存储N-1个数据。其队内有效长度为

A.(rear - front + N) % N + 1
B.(rear - front + N) % N
C.(rear - front) % (N + 1)
D.(rear - front + N) % (N - 1) 

答案A

这样就已经排除两个了 我们再来了解一下 A 的原理

 A. (rear - front + N) % N + 1:

这是计算循环队列队内有效长度的公式。解释如下

(rear - front + N) % N首先计算rear和front之间的差值即队尾和队头的相对位置。由于循环队列的特性rear可能小于front表示循环回到队列的开头因此需要加上N来确保差值为正数。然后再进行取模运算将差值限定在0到N-1之间。

1由于队内有效长度是指队列中实际存储的元素个数需要将前面计算得到的差值加1即为队内有效长度。

因此选项A使用了合适的公式来计算循环队列的队内有效长度。

力扣622. 设计循环队列 - 力扣Leetcode 

我们看一下这个代码的具体要求

class MyCircularQueue {

    public MyCircularQueue(int k) {

    }
    
    public boolean enQueue(int value) {

    }
    
    public boolean deQueue() {

    }
    
    public int Front() {

    }
    
    public int Rear() {

    }
    
    public boolean isEmpty() {

    }
    
    public boolean isFull() {

    }
}

class MyCircularQueue {

    private int[] elem;
    private int front;//队头下标
    private int rear;//队尾下标

    public MyCircularQueue(int k) {
        this.elem = new int[k+1]; //因为会浪费空间所以为了确保数组不会越界多给一个空间
    }

    public boolean enQueue(int value) {
        if(isFull()) {
            return false;
        }
        elem[rear] = value;
        rear = (rear+1)%elem.length; //可不能 rear++会越界
        return true;
    }

    public boolean deQueue() {
        //1、空的 不能出
        if(isEmpty()) {
            return false;
        }
        //2、不空 则 保存队头元素 然后front往后走
        front = (front+1)%elem.length;
        return true;
    }

    //得到队头元素
    public int Front() {
        if(isEmpty()) {
            return -1;
        }
        return elem[front];
    }

    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        int index = (rear == 0) ? elem.length-1 : rear-1;
        return elem[index];
        //return elem[(rear - 1 + elem.length) % elem.length];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        //rear的下一个是front
        if((rear+1)%elem.length == front) {
            return true;
        }
        return false;
    }
}

return elem[(rear - 1 + elem.length) % elem.length]由于rear指向队尾的下一个位置所以要获取队尾元素的索引需要将rear减1。然后加上elem.length是为了处理rear-1为负数的情况确保索引为正数。最后再进行取模运算将索引限制在0到capacity-1之间实现循环。
elem[...]通过计算得到的索引访问elements数组中对应位置的元素即为队尾元素的值。

如下是使用链表的方法是力扣的官方题解

class MyCircularQueue {
    private ListNode head;
    private ListNode tail;
    private int capacity;
    private int size;

    public MyCircularQueue(int k) {
        capacity = k;
        size = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        ListNode node = new ListNode(value);
        if (head == null) {
            head = tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        size++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        ListNode node = head;
        head = head.next;  
        size--;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return head.val;
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return tail.val;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }
}

来做个小练习 

对于循环队列下列叙述中正确的是

A.队头是固定不变的
B.队头一定大于队尾
C.队头一定小于队尾
D.队头可以大于队尾也可以小于队尾 

答案D、队头可以大于队尾也可以小于队尾

解析对于循环队列队头和队尾的相对位置是可以变化的。循环队列通过使用取模运算来实现循环的效果当队尾达到数组的末尾时下一个元素将回到数组的开头。这样可以利用数组的空间进行循环利用。

在循环队列中队头可以在队尾之后也可以在队尾之前这取决于队列中元素的个数和队列的操作历史。例如当队列为空时队头和队尾指向同一个位置队列中只有一个元素当队列已满时队头可能在队尾之后。

因此选项D中的说法是正确的循环队列中队头可以大于队尾也可以小于队尾。

双端队列 (Deque)

双端队列Deque是一种数据结构它允许在队列的两端进行插入和删除操作。其名称"Deque"是"double ended queue"的缩写。双端队列可以被视为同时具有队列和栈的性质因为它允许在队列的两端进行元素的添加和移除。

双端队列与普通队列的主要区别在于普通队列只允许在队尾进行入队操作并且只能从队头进行出队操作。而双端队列允许在队头和队尾同时进行入队和出队操作。

双端队列的特性使得它在许多场景下非常有用。下面是一些双端队列的常见应用场景

  • 队列和栈的结合双端队列可以用作队列或栈的替代品。你可以选择从队头或队尾插入和删除元素从而灵活地应对不同的需求。
  • 路径搜索算法在某些路径搜索算法如广度优先搜索中需要在搜索过程中同时从前面和后面进行扩展。双端队列提供了高效的操作使得这样的算法更容易实现。
  • 滑动窗口问题滑动窗口问题是一类常见的算法问题通常涉及到在一个固定大小的窗口内进行计算。双端队列可以用来维护窗口内的元素并且能够在常数时间内进行插入和删除操作。

双端队列的实现方式有多种可以使用数组、链表或双向链表来实现。具体选择哪种实现方式取决于应用场景和性能要求。无论使用何种实现方式双端队列的操作复杂度应该尽量为O(1)。

下面是双端队列的一些常见操作

  • 入队操作从队头或队尾插入元素可以通过 insertFront() 和 insertLast() 等方法来实现。
  • 出队操作从队头或队尾删除元素可以通过 deleteFront() 和 deleteLast() 等方法来实现。
  • 获取队头和队尾元素可以通过 getFront() 和 getLast() 等方法来获取队头和队尾元素的值而不进行删除操作。
  • 判断双端队列是否为空可以通过 isEmpty() 方法来判断双端队列是否为空。

总而言之双端队列是一种非常有用的数据结构它允许在队列的两端进行插入和删除操作。它可以灵活地应对不同的应用场景并且能够以常数时间复杂度进行插入和删除操作。

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

 ArrayDeque<>() 是 Deque 的数组实现跳转过去看看

 ArrayDeque的介绍

ArrayDeque是Java中的一个双端队列deque实现类。

它实现了Deque接口允许在队列两端进行快速插入和删除操作。

双端队列是一种具有队列和栈特性的数据结构可以在队列的两端进行元素的插入和删除。ArrayDeque使用动态数组作为其内部实现它可以根据需要自动调整大小。

与LinkedList相比ArrayDeque提供了更高效的随机访问和更快的插入/删除操作。然而ArrayDeque在插入和删除操作中的开销较高需要移动其他元素来保持队列的连续性。

以下是ArrayDeque常用的一些方法

  • addFirst(element)将元素添加到队列的开头。
  • addLast(element)将元素添加到队列的末尾。
  • removeFirst()移除并返回队列的第一个元素。
  • removeLast()移除并返回队列的最后一个元素。
  • peekFirst()返回队列的第一个元素但不移除它。
  • peekLast()返回队列的最后一个元素但不移除它。
  • size()返回队列中元素的数量。

ArrayDeque可以用于实现双向队列、栈、循环队列等数据结构并且它是线程不安全的不支持多线程并发操作。如果需要在多线程环境下使用队列可以考虑使用ConcurrentLinkedDeque等线程安全的实现类。

        Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
        
        stack.push(1);  //双端队列实现的栈

OJ练习

1、用队列实现栈

请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
实现 MyStack 类

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的返回 true 否则返回 false 。

力扣225. 用队列实现栈 - 力扣Leetcode 

我想先问你一个问题我们最普通的队列可以实现一个栈吗

答案是否定的。

 

 好了现在来实现一下

import java.util.LinkedList;
import java.util.Queue;

public class MyStack {

    private Queue<Integer> qu1;
    private Queue<Integer> qu2;

    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }

    /*
     * 入栈操作
     * 入到不为空的队列当中如果都为空 入到qu1
     */
    public void push(int x) {
        if(!qu1.isEmpty()) {
            qu1.offer(x);
        }else if(!qu2.isEmpty()) {
            qu2.offer(x);
        }else {
            qu1.offer(x);
        }
    }

    public int pop() {
        if(empty()) {
            return -1;//栈为空的
        }

        if(!qu1.isEmpty()) {
            int size = qu1.size();
            for (int i = 0; i < size-1; i++) {
                int tmp = qu1.poll();
                qu2.offer(tmp);
            }
            return qu1.poll();
        }else {
            int size = qu2.size();
            for (int i = 0; i < size-1; i++) {
                int tmp = qu2.poll();
                qu1.offer(tmp);
            }
            return qu2.poll();
        }
    }

    //peek
    public int top() {
        if(empty()) {
            return -1;//栈为空的
        }
        int tmp = -1;
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            for (int i = 0; i < size; i++) {
                tmp = qu1.poll();
                qu2.offer(tmp);
            }
            return tmp; //最后一次覆盖掉 tmp 的值就是我们栈顶的元素
        }else {
            int size = qu2.size();
            for (int i = 0; i < size; i++) {
                tmp = qu2.poll();
                qu1.offer(tmp);
            }
            return tmp;
        }
    }

    /*
     * 2个队列都为空 表示 栈为空 
     *
     */
    public boolean empty() {
        //2个对列 都为空的时候
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

注意 pop() 我这样写可不可以

if(!qu1.isEmpty()) {
    for (int i = 0; i < qu1.size()-1; i++) {
         int tmp = qu1.poll();
         qu2.offer(tmp);
    }
    return qu1.poll();
 }else {
    for (int i = 0; i < qu2.size()-1; i++) {
                int tmp = qu2.poll();
                qu1.offer(tmp);
    }
    return qu2.poll();
}

当然不可以

因为我们每次 poll qu1 和 qu2 的 size 都会改变是一个变量。

2、用栈实现队列

力扣232. 用栈实现队列 - 力扣Leetcode

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty
实现 MyQueue 类

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空返回 true 否则返回 false

我觉得这个思路已经没什么好说的了和前一个几乎是一样的不是吗

所以我们稍微变换一下思路不用临时变量了用输出栈和输入栈直接进行模拟

输出栈永远是负责输出元素的 

import java.util.Stack;

public class Myqu{
    private Stack<Integer> stack1; // 输入栈
    private Stack<Integer> stack2; // 输出栈

    public Myqu() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        // 将stack2中的元素全部转移到stack1
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        stack1.push(x);
    }

    private void shiftStacks() {
        if (stack2.isEmpty()) {
            // 当输出栈为空时将输入栈中的元素转移到输出栈
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
    }

    public int pop() {
        shiftStacks(); // 确保输出栈中有元素
        return stack2.pop(); // 从输出栈弹出元素
    }

    public int peek() {
        shiftStacks(); // 确保输出栈中有元素
        return stack2.peek(); // 返回输出栈顶元素
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty(); // 队列为空的条件是输入栈和输出栈都为空
    }

    public static void main(String[] args) {
        Myqu obj = new Myqu();
        obj.push(1);
        obj.push(2);
        int param_2 = obj.pop();
        int param_3 = obj.peek();
        boolean param_4 = obj.empty();
        System.out.println(param_2);  // 输出1
        System.out.println(param_3);  // 输出2
        System.out.println(param_4);  // 输出false
    }
}

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：阿里云轻量服务器--Docker--RocketMq安装

下一篇：SpringBoot 代码混淆真香，再也不用担心反编译代码泄露...

“初阶数据结构（6）（队列的概念、常用的队列方法、队列模拟实现【用双向链表实现、用数组实现】、双端队列 (Deque)、OJ练习【用队列实现栈、用栈实现队列】）” 的相关文章

红袖添香,绝代妖娆,Ruby语言基础入门教程之Ruby3基础数据类型(data types)EP021年前 (2023-02-02)
SparkSubmit提交yarn流程分析（学习版）1年前 (2023-02-02)
day03-模块化编程1年前 (2023-02-02)
[Android开发学iOS系列] Auto Layout1年前 (2023-02-02)
Qt项目-翻金币游戏1年前 (2023-02-02)
女友让我每天半夜十二点给她发晚安？我用 Python 做了个定时发消息神器！怕她干嘛！1年前 (2023-02-02)
DTSE Tech Talk 第18期丨统计信息大揭秘，数仓SQL执行优化之密钥1年前 (2023-02-02)
【Java全栈学习路线】最全的Java学习路线及知识清单，Java自学方向指引1年前 (2023-02-02)
双向链表1年前 (2023-02-02)
使用matlab进行回声处理（三重回声）-数字信号处理课设1年前 (2023-02-02)

阿里云国际版