【数据结构】队列

队列

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表，一种先进先出的数据结构。
队尾：允许插入的一端。
队头：允许删除的一端。

队列的模拟实现

队列的底层可以是顺序表，可以是链表实现。

队列的链式实现

在实现队列前我们先思考使用什么样的链表来实现？
由于栈的特性是先入先出，如果使用单链表和双向链表都可以，
只要在单链表标记一下尾节点就行，
但是因为Java提供的是双向链表实现的，所以我们使用双向链表。

接口实现

实现的接口如下：

public class MyQueue {//入队列public void offer(int val) {}//出队列public int poll() {}//获取队头元素 但是不删除public int peek() { }//判空public boolean isEmpty() { } //获取队列元素个数public int size(){}      
}

内部类

跟双向链表的内部类实现差不多。

static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;

入队列

实现思路：

1. 先看队列是否为空，为空，头尾指向入队节点。
2. 不为空尾节点的后继next指向入队节点，入队节点前驱prev指向尾节点，尾节点变为入队节点。

public void offer(int val){ListNode cur = new ListNode(val);if(isEmpty()){head = last = cur;return;}last.next = newNode;newNode.prev = last;last = newNode;
}

出队列

实现思路：

1. 先判断队列是否为空，队列为空抛异常。
2. 队列不为空，将头节点记录下来，头节点后一个节点前驱prev置为空，头节点变为后一个节点。

public int poll() throws NullPointerException{try{if(isEmpty()){throw new NullPointerException;}}catch(NullPointerException e){e.printStackTrace();}ListNode cur = head;head.next.prev = null;head = head.next;return cur.val;
}

获取队头元素 但是不删除

实现思路：

1. 先判断队列是否为空，队列为空抛异常。
2. 队列不为空，返回头节点。

 public int peek() throws NullPointerException{try{if(isEmpty()){throw new NullPointerException;}}catch(NullPointerException e){e.printStackTrace();}return head.val;
}

判空

直接返回头是否为空就行。

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

获取队列元素个数

直接循环遍历即可。

    public int size(){ListNode cur = head;int size = 0;while(cur != null){cur = cur.next;size++;}return size;} 

队列的顺序实现（循环队列）

直接使用顺序表的缺陷

当我们直接使用顺序表来放数据时，我们将元素入队列放在数组尾，出队列时将数组前面元素出去后，会使前面浪费的空间越来越大。
基于此我们就用循环队列来实现，还是数组作为底层，但我们将其想象成一个圆。

接口实现

class MyCircularQueue {//构造器，设置队列长度为 kpublic MyCircularQueue(int k) {}// 向循环队列插入一个元素。如果成功插入则返回真。public boolean enQueue(int value) {}//从循环队列中删除一个元素。如果成功删除则返回真。public boolean deQueue() {}//从队首获取元素。如果队列为空，返回 -1 public int Front() {}//获取队尾元素。如果队列为空，返回 -1 。public int Rear() {}//检查循环队列是否为空。public boolean isEmpty() {}//检查循环队列是否已满。public boolean isFull() {}
};

成员变量

数组arr ，头下标front，尾节点下一个下标rear，数组长度size。

private int []arr;
private int front;
private int rear;
private int size;

构造器，设置队列长度为 k

因为我们使用的判空方法（下文讲）会造成一个空间的浪费，所以多申请一个空间。

public MyCircularQueue(int k) {size = k+1;arr = new int[size];front = rear = 0;}

向循环队列插入一个元素 成功插入则返回真

实现思路：

1. 判断队列是否已满，满了就返回false。
2. 不满就在rear放。
3. 因为是循环队列，所以rear的赋值要使用取余。

public boolean enQueue(int value) {if(isFull()){return false;}else{arr[rear] = value;rear = (rear + 1) % size;return true;}}

从循环队列中删除一个元素 成功删除则返回真

实现思路：

1. 判断队列是否为空，空就返回false。
2. 不空就直接将front指向下一个位置。
3. 因为是循环队列，所以front的赋值要使用取余。

public boolean deQueue() {if(isEmpty()){return false;}else{front = (front + 1) % size;return true;}}

从队首获取元素。如果队列为空，返回 -1

实现思路：

1. 先判断队列是否为空，为空返回-1。
2. 不为空，返回front下标对应值。

public int Front() {if(isEmpty()){return -1;}else{return arr[front];}}

获取队尾元素。如果队列为空，返回 -1

实现思路：

1. 先判断队列是否为空，为空返回-1。
2. 不为空，再判断rear是否为0，是0就返回数组最后一个元素。
3. 不为0，就直接返回rear-1下标对应的元素。

public int Rear() {if(isEmpty()){return -1;}else{if(rear == 0){return arr[size - 1];}else{return arr[rear - 1];}                    }}

检查循环队列是否为空

检查空根据循环队列的实现有两种方法：

1. 使用usedSize记录队列元素个数，个数为0就是空。
2. 空一个空间，如果front和rear相等那就是空。

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

检查循环队列是否已满

检查满根据循环队列的实现有两种方法：

1. 使用usedSize记录队列元素个数，个数和size相等就是满。
2. 空一个空间，如果rear的下一个位置就是front那就是满。

public boolean isFull() {return front == (rear+1) % size;}

Java中的Queue

Java中Queue的底层是LinkedList实现的。
并且Queue只是一个接口，必须new对象LinkedList才能使用。

实现的接口

实现的接口如下：

常用方法

常用方法如下：

队列练习

用队列实现栈

用栈实现队列

设计循环队列