【数据结构与算法】深度理解队列(上)

✨hello，进来的小伙伴们，你们好耶！✨

🚎🚎系列专栏：【数据结构与算法】

🚀🚀本篇内容:队列从0到1的学习！

⛵⛵作者简介：一名双非本科大三在读的科班Java编程小白，道阻且长，你我同行！

🚍🚍码云存放仓库gitee：Java数据结构代码托管！

一、概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

二、 队列的使用

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

三、常用方法

** 代码演示：**

1、入队

public class TestDemo1 {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        System.out.println(queue);
    }
}

运行结果：

2、出队(这里我们出2个元素，那么队列里的结果应该是剩下3,4)

public class TestDemo1 {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        System.out.println(queue);
        queue.poll();
        queue.poll();
        System.out.println(queue);
    }
}

运行结果：

3、获取队头元素

public class TestDemo1 {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        int s = queue.peek();//获取队头元素但是不删除
        System.out.println(s);
    }
}

运行结果:(可以知道我们的peek()方法只是获得队头元素而不是删除队头元素 那么结果应该就是1)

4、判断队列是否为空

public class TestDemo1 {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        boolean b1 = queue.isEmpty();
        System.out.println(b1);
    }
}

运行结果：

5、获取队列中有效元素的个数

public class TestDemo1 {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        System.out.println(queue.size());
    }
}

运行结果：

四、队列的模拟实现

1、老规矩还是把我们队列的学习内容放在一个包下。

2、所有方法实现代码

package Queue;

/**
 * User:辰柒
 * Date:2022-10-02
 * Time:17:08
 */
public class MyQueue {
    static class ListNode {
        public int val;
        public ListNode next;

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

    public ListNode head;
    public ListNode tail;
    public int usedSize;

    public void offer(int val) {
        ListNode node = new ListNode(val);
        if (head == null) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = tail.next;
        }
        usedSize++;
    }

    public int poll() {
        if (empty()) {
            return -1;
        }
        int ret = head.val;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        usedSize--;
        return ret;
    }

    public int peek() {
        if (empty()) {
            return -1;
        }
        return head.val;
    }

    public boolean empty() {
        return usedSize==0;
    }

    public int getUsedSize() {
        return usedSize;
    }
}

🍎🍎OK，那么本篇博客先带大家入门一下队列的概念以及方法，接下来的博客我将会更新循环队列 双端队列的实现，以及队列的面试题分析，内容干货满满，期待你的一键三连！🤟🤟