队列的使用及实现队列

队列的使用及实现

队列的概念

普通队列 Queue双端队列 Deque循环队列 队列的使用

插入元素 add offer删除元素 remove poll得到队头元素 element peek 双端队列的使用

插入删除得到队头队尾元素 实现队列

实现 Node定义队头和队尾向队列当中增加元素判断是否为空在队列当中弹出元素得到队头元素测试 循环队列

计算循环队列的下标图示

第三种方法 实现循环队列

初始化入队判满判空出队得到队头元素得到队尾元素测试：

队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点：FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）。队列就相当于在餐厅排队打饭一样，先排队的人先打饭，后排队的人，后打饭。

普通队列 Queue

只能队尾进，队头出。也可以当作栈来使用。

双端队列 Deque

双端队列可以队头增加删除元素，也可以在队尾增加删除元素。

循环队列

循环队列就是队列的头和尾相连。

队列的使用 插入元素 add offer

在队列当中，add 和 offer 都可以插入元素，因为 add 有的时候会报异常，所以插入元素建议用 offer 。

public static void main(String[] args) {
    Queue queue = new linkedList<>();
    queue.add(1);
    queue.offer(2);
    System.out.println(queue);
}

运行结果如下：

删除元素 remove poll

remove 和 poll 都是删除队头元素：

public static void main(String[] args) {
    Queue queue = new linkedList<>();
    queue.add(1);
    queue.offer(2);
    queue.offer(3);
    queue.offer(4);
    queue.offer(5);
    System.out.println(queue);
    queue.remove();
    System.out.println(queue);
    queue.poll();
    System.out.println(queue);
}

得到队头元素 element peek

element 和 peek 都是得到队头元素：

public static void main(String[] args) {
    Queue queue = new linkedList<>();
    queue.add(1);
    queue.offer(2);
    queue.offer(3);
    queue.offer(4);
    queue.offer(5);
    System.out.println(queue.element());
    System.out.println(queue.peek());
}

双端队列的使用 插入

相对于普通队列，双端队列多了队头插入，队尾插入。

public static void main(String[] args) {
    Deque queue2 = new linkedList<>();
    queue2.offerFirst(1);
    queue2.offerLast(2);
    queue2.offerLast(3);
    queue2.offerLast(4);
    queue2.offerLast(5);
    System.out.println(queue2);
}

运行结果如下：

删除

同样，删除也可以删除队头和队尾的元素：

public static void main(String[] args) {
    Deque queue2 = new linkedList<>();
    queue2.offerFirst(1);
    queue2.offerLast(2);
    queue2.offerLast(3);
    queue2.offerLast(4);
    queue2.offerLast(5);
    System.out.println(queue2);
    queue2.removeFirst();
    queue2.removeLast();
    System.out.println(queue2);
}

运行结果如下：

得到队头队尾元素

也是同样的方法来得到：

public static void main(String[] args) {
    Deque queue2 = new linkedList<>();
    queue2.offerFirst(1);
    queue2.offerLast(2);
    queue2.offerLast(3);
    queue2.offerLast(4);
    queue2.offerLast(5);
    System.out.println(queue2);
    System.out.println(queue2.peekFirst());
    System.out.println(queue2.peekLast());
}

运行结果如下：

实现队列

这里通过单链表来实现队列，队列的入队和出队的时间复杂度都是 O(1) ，不论是把头当作队头还是把尾当作队头，都会有一个时间复杂度是 O(n) ，所以通过增加一个 last 来指向队尾，这样的话就可以完成 O(1) 的时间复杂度了。

实现 Node

因为节点有值，而且需要知道下一个节点。所以代码如下：

class Node {
    public int val;
    public Node next;
    public Node(int val) {
        this.val = val;
    }
}

定义队头和队尾

public Node head;
public Node last;

向队列当中增加元素

在插入的时候，有两种情况：一、第一次插入：head 和 last 都是空，让 head 和 last 指向插入节点。二、非第一次插入：直接让 last.next = node; last = last.next;

public void offer(int val) {
    Node node = new Node(val);
    if(head == null) {
        head = node;
        last = node;
    } else {
        last.next = node;
        last = last.next;
    }
}

判断是否为空

判断是否为空的时候，直接判断 head 是否为 null 就可以了，因为 head 是队头。

public boolean isEmpty() {
    return this.head == null;
}

在队列当中弹出元素

在弹出元素的时候，首先要判断队列是否为空。然后让 head = head.next;

public int poll() {
    if (isEmpty()) {
        throw new RuntimeException("队列为空!");
    }
    int oldVal = head.val;
    this.head = head.next;
    return oldVal;
}

得到队头元素

先判断队列是否为空，然后通过返回 head.val 就可以得到队头元素了。

public int peek() {
    if (isEmpty()) {
        throw new RuntimeException("队列为空！");
    }
    return this.head.val;
}

测试

public static void main(String[] args) {
    MyQueue queue = new MyQueue();
    queue.offer(1);
    queue.offer(2);
    queue.offer(3);
    System.out.println(queue.isEmpty());
    System.out.println(queue.peek());
    System.out.println(queue.poll());
    System.out.println(queue.poll());
    System.out.println(queue.poll());
}

运行结果如下：

循环队列

在用数组做队列（循环队列的本质就是数组）的时候，就会出现像下面这种情况，把元素往队列里面放：

先放入五个元素：

然后再出掉前几个：

再放入后面：

此时队列已经满了，但实际并没有满，因为前面有了空的部分。要想把前面的部分也利用起来，那就需要把队尾放到前面，然后继续插入，如果继续删除，那么队头也应该挪到前面，这样就是循环队列。

计算循环队列的下标

通过这样一个公式来计算偏移后的下标，如图片所示：

因为我们是一个一个往后挪，所以每次的 offset 都是 1 .

图示

我们用 front 表示队头，用 rear 表示队尾，如果 rear == front 了 那么可能是空了，也可能是满了：


所以目前又遇到了一个问题：相遇的时候是空还是满。

使用 uesdSize 和数组长度比较，确定满或者空使用标志位，flag = false 在开始的时候，rear == front && flag == false 来表示空。那么：入队每放一个元素，就置为 true ，直到 rear 和 front 相遇，就是 true 就是满了。每出一个元素，就换为 false ：

每出一个元素，就换成 false

最后就是这个样子：

第三种方法

第三种方法就是浪费一个空间，每次放之前检查一下下一个是不是 front 。如果是，那么就是满的。

实现循环队列 初始化

因为我们自己实现循环队列需要有数组，front，rear 。所以要定义这些，因为我们是牺牲了一个位置来实现的，所以初始化的时候要多给一个空间，也就是下面的 this.elem = new int[k + 1]; ：

public int[] elem;
public int front;
public int rear;
public MyCircleQueue(int k) {
    this.elem = new int[k + 1];
}

入队

入队的时候，先判断满没满，然后再入队，会有极端情况，从最后一个下标走到 0 下标，要走到这个下标的话，就用 (rear+1)%length 就可以了。

public boolean enQueue(int value) {
    if (isFull()) {
        return false;
    }
    this.elem[rear] = value;
    rear = (rear+1)% elem.length;
    return true;
}

判满

因为实现的时候是 rear 的下一个是 front ，所以直接判断是不是就可以确定满没满了：

public boolean isFull() {
    if((this.rear+1)% elem.length == front){
        return true;
    }
    return false;
}

判空

当队列是空的时候的时候，front == rear ，所以直接这样判断就可以了：

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

出队

出队的时候要先判断是否为空，也会有像入队时的那样的极端情况，出队的时候也同样会有那样的极端情况，所以也是 front = (front+1)%length； 就可以了。

public boolean deQueue() {
    if (isEmpty()) {
        return false;
    }
    front = (front+1)% elem.length;
    return true;
}

得到队头元素

要得到队头元素，也就是得到 front 下标的元素就可以了，不过也要先判断空：

public int Front() {
    if (isEmpty()) {
        throw new  RuntimeException("队列为空");
    }
    return this.elem[front];
}

得到队尾元素

在拿队尾元素的时候，会有这样的特殊情况：

就是 rear(队尾) 的下标是 0 ，所以也是特殊情况，也不能简单的 -- 来获得元素。所以就应该判断一下这个位置：如果当前位置为 0 ，那么就返回数组大小减 1 。不是的话，就返回 rear - 1 下标的值：

public int Rear() {
    if (isEmpty()) {
        return -1;
    }
    int index = -1;
    if(rear == 0){
        index = elem.length - 1;
    } else {
        index = rear - 1;
    }
    return this.elem[index];
}

测试：

public static void main(String[] args) {
    MyCircleQueue myCircleQueue = new MyCircleQueue(4);
    myCircleQueue.enQueue(1);
    myCircleQueue.enQueue(2);
    myCircleQueue.enQueue(3);
    myCircleQueue.enQueue(4);
    int val = myCircleQueue.front;//得到队头元素
    System.out.println(val);
    int val2 = myCircleQueue.rear;//得到队尾元素
    System.out.println(val2);
    myCircleQueue.deQueue();
    int val3 = myCircleQueue.front;
    System.out.println(val3);
}

运行结果如下：

最后一个值是出队之后得到的队头的值。