如图所示：

通常，称进数据的一端为 "队尾"，出数据的一端为 "队头"，数据元素进队列的过程称为 "入队"，出队列的过程称为 "出队"。

比如上图中的元素3就是队尾，元素1就是队头。从图中我们也可以看出，元素1是最先进入队列中的，同样他也是最先出队的，所以说队列是一种先进先出的结构。

二、Java中队列的使用

在Java中，队列Queue是个接口，底层是用双向链表实现的。

他主要的方法有一下这几个：

注意：Queue是个接口，我们不能直接对Queue进行实例化，但我们可以用Queue接口实例化LinkedList的对象，因为LinkedList实现了Queue接口。

使用实例：

三、队列的模拟实现


// 用单链表实现的队列，入队和出队的时间复杂度都是O(1)
public class MyQueue2 {
    class ListNode{
        public int val;
        public ListNode next;
        ListNode(int val) {
            this.val = val;
        }
    }
    ListNode head;
    ListNode last;
    // 入队，从尾入，从头出
    public void offer(int x) {
        ListNode node = new ListNode(x);
        if (empty()) { // 如果此时队列为空，新插入的结点就是头结点和尾巴结点
            head = node;
            last = node;
        }
        else {
            last.next = node;
        }
        last = node;
    }
    // 出队
    public int poll() {
        if (empty()) {
            throw new NullPointerException("当前队列为空，你的操作不合法！");
        }
        if (head == last) head = last = null;
        int tmp = head.val; // 先保留一下头节点的值，然后再更改指向
        head = head.next;
        return tmp;
    }
    // 只是获取将要出队的元素的值,不删除元素
    public int peek() {
        return head.val;
    }
    // 判断当前队列是否为空
    public boolean empty() {
        if (head == null) {
            return true;
        }
        return false;
    }
}

思路：
1.用单链表实现的队列，为了入队和出队的时间复杂度都是O(1),
2.我们还在单链表中设置了一个对尾结点的引用last，同时还需要保证我们都是尾插入队，头删出队
为什么呢？因为单链表只有后驱，没有前驱（即只知道后一个是谁，但不知道前一个是谁）
1.如果我们要尾删出队——就必须找到该结点的前一个是谁，就需要遍历链表O(N)时间复杂度
2.而如果头删，我们直接更改当前头结点的指向就好了，时间复杂度自然是O(1)
那为啥要尾插入队呢？我们如果从尾巴插入，是不是只要将当前的的尾巴结点指向新插入的结点就行了，
此时新插入的结点就变成了新的尾巴结点，时间复杂度也是O(1)；

测试：

四、力扣刷题演练

4.1 设计循环队列

题目链接：力扣

分析 :

我们刚才是用链表实现的队列，而这道题目要求我们用数组这种线性储存结构来实现队列的各种操作，所以我们就需要改变一下设计思想

数组是线性储存元素，那么我们的新增和删除该怎么操作呢？新增和删除时数组的下标是怎样变化的呢？题目中说的循序是怎样进行的呢？

思路:

在这个循环队列中，我们用front来表示队头的数组下标、rear表示队尾的数组下标。为了实现循环我们发现，所谓的头和尾其实是在不断变化着的，和链表一样，我们还是从尾巴入队，从头部出队;

当front == rear是表示当前队列为空，当一个元素入队后，表示队尾的数组下标rear就加一；出队后表示队头的数组下标front就加一，但问题了来了——如何判断当前队列是否满了呢？

有三种方法

设置一个标记flag;
每增加或减少一个元素后，用计数器usedSize记录当前队列中元素的个数。当usedSize == 数组的长度时说明满了;
空一格，当(rear + 1) % 数组的长度 == front 的时候说明数组满了;

说到这里，你可能对取模有点疑惑，为什么要取模呢???

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】

推荐阅读

相关标签