AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构——队列

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

一、理解队列


1. 队列的定义


队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列中数据的特点：先进先出，后进后出。


2. 队列的操作


允许插入的一端称为队尾，允许删除的一端称为队头。


我们可以将其想象成一个链表，队头就是这个链表中的第一个节点，队尾就是这个链表中的最后一个节点，然而我们只能对这个链表进行 尾插、头删 操作。


二、测试 Java 实现队列及其方法


程序清单1：


public class Test1 {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(2);//尾插
        queue.offer(4);
        queue.offer(6);
        queue.offer(8);
        System.out.println(queue);
        System.out.println(queue.peek());//访问队列头元素
        System.out.println(queue);
        System.out.println(queue.poll());//删除队列头元素
        System.out.println(queue);
    }
}


输出结果：


92f40bc37e964445aca285580d03d1f3.png


三、通过单链表实现自己的队列


第一个 java 文件放的是两个类
一个类实现节点 Node，另一个类实现队列 Queue


程序清单2：


class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val = val;
    }
}
public class Queue {
    public Node head;
    public Node last;
    //尾插
    public void offer(int val){
        Node node = new Node(val);
        if(this.head == null){
            head = node;
            last = node;
            return;
        }
        last.next = node;
        last = last.next;
    }
    //头删
    public int poll(){
        if(head == null){
            throw new RuntimeException("队列为空");
        }
        int headVal = head.val;
        head = head.next;
        return headVal;
    }
    public int peek(){
        if(head == null){
            throw new RuntimeException("队列为空");
        }
        return head.val;
    }
    public void print(){
        Node cur = head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
}


第二个 java 文件放的是一个类 Test
目的是使用主函数来测试队列的一系列功能


程序清单3：


public class Test {
    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.offer(2);
        queue.offer(4);
        queue.offer(6);
        queue.offer(8);
        queue.print();
        System.out.println(queue.peek());
        queue.print();
        System.out.println(queue.poll());
        queue.print();
        System.out.println(queue.poll());
        queue.print();
    }
}


输出结果：


f007f8afaad445f383efb11676c915d6.png


四、理解双端队列


双端队列可以实现两端都能进行出队和入队操作


db6125af88db47faa5623eaa9dad7153.png

1. 测试 Java 实现双端队列及其方法


程序清单4：


public class Test4 {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        deque.offer(2); //默认尾插
        deque.offerLast(4);
        deque.offerFirst(6);//头插
        deque.offerLast(8);//尾插
        System.out.println(deque);
        System.out.println(deque.peek());//默认访问队列头元素
        System.out.println(deque.peekFirst());//访问队列头元素
        System.out.println(deque.peekLast());//访问队列尾元素
    }
}


输出结果：


ff3d3cb4a170451eabe62e9707ae3056.png


程序清单5：


public class Test5 {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        deque.offer(2); //默认尾插
        deque.offerLast(4);
        deque.offerFirst(6);//头插
        deque.offerLast(8);//尾插
        System.out.println(deque);
        System.out.println(deque.poll());//默认删除队列头元素
        System.out.println(deque);
        System.out.println(deque.pollFirst());//删除队列头元素
        System.out.println(deque);
        System.out.println(deque.pollLast());//删除队列尾元素
        System.out.println(deque);
    }
}


输出结果：


644640b15a284ac4b486bbb6da995d5b.png


五、环形队列


环形队列底层是通过带环的顺序表实现的队列。这里我们要时刻清楚队头和队尾的位置！


3629efa637bd48069004cbd50c7f74b5.png


六、通过OJ题深入理解队列


题目一 循环队列


leetcode 622


程序清单6：


public class MyCircularQueue {
    public int[] elem;
    public int front; //队头下标
    public int rear; //队尾下标
    public MyCircularQueue(int k) {
        elem = new int[k+1];
    }
    //入列
    public boolean enQueue(int value) {
        //队列满了，无法添加元素
        if(isFull() == true){
            return false;
        }
        //队列没满，正常添加
        elem[rear] = value;
        rear = (rear+1) % elem.length;
        return true;
    }
    //出列
    public boolean deQueue() {
        //队列空了，无法删除元素
        if(isEmpty() == true){
            return false;
        }
        //队列没空，正常删除
        front = (front+1) % elem.length;
        return true;
    }
    //拿到队列的首元素
    public int Front() {
        if(isEmpty() == true){
            return -1;
        }
        return elem[front];
    }
    //拿到队列的末尾元素
    public int Rear() {
        if (isEmpty() == true) {
            return -1;
        }
        int lastRear = (rear + elem.length - 1) % elem.length;
        return elem[lastRear];
    }
    public boolean isEmpty() {
        if(front == rear){
            return true;
        }
        return false;
    }
    public boolean isFull() {
        int nextRear = (rear+1) % elem.length;
        if(nextRear == front){
            return true;
        }
        return false;
    }
}

32040a2fde274a098d527fe07830df2c.png


结论：


① 当元素入队的时候，让 rear 开始跑，在 front 和 rear 重合的情况下，那么这时的队列已满。


② 当元素出队的时候，让 front 开始跑，在 front 和 rear 重合的情况下，那么这时的队列已空。


思路：


① 元素入队：先判断队列是否满了，若满了，就返回 false；若没满，就正常添加，正常添加的时候，我们要考虑到顺序表的最后一个元素，比如说：数组的最后一个下标为 3，那么既然是循环队列，我们要让元素放在数组下标为0的位置，此时我们就不能使用 3 + 1 = 4。


rear = (rear+1) % elem.length; //true
//rear = rear + 1 //false


② 元素出队：先判断队列是否为空，若为空，就返回 false；若不为空，就正常删除元素，正常删除的时候，我们只需要让 front 遍历数组下标即可，不用管上一个元素还存在数组中，因为下一次元素入队的时候，就会将未删除的元素直接覆盖。


③ 拿到队首元素：正常情况下，直接返回 front 下标的元素。


④ 拿到队尾元素：正常情况下，我们要让 rear 下标退一格，这里也要注意不能使数组越界。

int lastRear = (rear + elem.length - 1) % elem.length;
return elem[lastRear];


⑤ 另外在做 leetcode 题目的时候，我们要让数组的长度为 k+1，为什么这么做呢？因为我们通过 front 和 rear 实现的时候，这会造成 rear 总是表示的是队尾的下一个下标位，因为我们总是通过 rear + 1 来判断队列元素是不是已满的问题，如果满了，就不往里面放元素了，所以假设当数组长度为4时，我们只能放3个元素进行，其余一个空位就是用来判断队列是否已满。


public MyCircularQueue(int k) {
  elem = new int[k+1];
}


题目二 利用队列实现栈


leetcode 225


程序清单7：


class MyStack {
    Queue<Integer> queue1 = new LinkedList<>();
    Queue<Integer> queue2 = new LinkedList<>();
    public MyStack() {
    }
    //往栈中放数据
    public void push(int x) {
        if(queue1.isEmpty() == true){
            queue2.offer(x);
        }else if(queue2.isEmpty() == true){
            queue1.offer(x);
        }else {
            queue1.offer(x);
        }
    }
    //从栈顶拿数据
    public int pop() {
        if(empty() == true){
            return -1;
        }
        int size1 = queue1.size()-1;
        int size2 = queue2.size()-1;
        if(queue2.size() == 0){
            for (int i = 0; i < size1; i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }else {
            for (int i = 0; i < size2; i++) {
                queue1.offer(queue2.poll());
            }
        }
        return queue2.poll();
    }
    //访问栈顶的元素
    public int top() {
        if(empty() == true){
            return -1;
        }
        int midVal = 0;
        int size1 = queue1.size();
        int size2 = queue2.size();
        if(queue2.size() == 0){
            for (int i = 0; i < size1; i++) {
                midVal = queue1.poll();
                queue2.offer(midVal);
            }
            return midVal;
        }else {
            for (int i = 0; i < size2; i++) {
                midVal = queue2.poll();
                queue1.offer(midVal);
            }
            return midVal;
        }
    }
    public boolean empty() {
        if(queue1.isEmpty() == true && queue2.isEmpty() == true){
            return true;
        }
        return false;
    }
}



题目三 利用栈实现队列


程序清单8：


class MyQueue {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    public MyQueue() {
    }
    public void push(int x) {
        stack1.push(x);
    }
    public int pop() {
        if(empty()){
            return -1;
        }
        int size1 = stack1.size();
        if(stack2.size() == 0){
            for (int i = 0; i < size1; i++) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }else {
            return stack2.pop();
        }
    }
    public int peek() {
        if(empty()){
            return -1;
        }
        int size1 = stack1.size();
        if(stack2.size() == 0){
            for (int i = 0; i < size1; i++) {
                stack2.push(stack1.pop());
            }
            return stack2.peek();
        }else {
            return stack2.peek();
        }
    }
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}


利用栈实现队列其实与利用队列实现栈的思想是一样的。


我们始终要清楚一件事情：


栈：先进后出

队列：先进先出


我简明地说一下思路：


① 模拟入队：利用栈 stack1 实现，而且 stack1 只用来实现入队。


② 模拟出队：利用栈 stack2 实现，而且 stack2 只用来实现出队。

当 stack2 不为空，就直接拿栈顶元素；

当 stack2 为空，就将 stack1 一直 pop 进入 stack2，然后再拿 stack2 的栈顶元素即可。


文章标签：
Java
关键词：
数据结构队列
十七ing
目录
相关文章
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
137 9
糜终
|
2月前
|
缓存 算法 调度
数据结构之 - 双端队列数据结构详解: 从基础到实现
数据结构之 - 双端队列数据结构详解: 从基础到实现
糜终
75 5
糜终
|
2月前
|
存储 算法 搜索推荐
探索常见数据结构：数组、链表、栈、队列、树和图
探索常见数据结构：数组、链表、栈、队列、树和图
糜终
112 64
肾透侧视攻城狮
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
21 1
禁默
|
2月前
初步认识栈和队列
初步认识栈和队列
禁默
61 10
java冯坚持
|
2月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列，数组模拟队列，模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
java冯坚持
25 0
数据结构与算法学习二、稀疏数组与队列，数组模拟队列，模拟环形队列
GuGuStudy
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
GuGuStudy
33 2
努力学习的小廉
|
2月前
【数据结构】--- 栈和队列
【数据结构】--- 栈和队列
努力学习的小廉
33 1
糜终
|
2月前
|
消息中间件 存储 Java
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
糜终
39 4
是店小二呀
|
2月前
【初阶数据结构】深入解析队列:探索底层逻辑
【初阶数据结构】深入解析队列:探索底层逻辑
是店小二呀
26 1