关于队列的简单理解

1.队列(Queue) 

1.1 关于队列

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

        下图通过图解来了解关于队列入队和出队的操作；

1.2队列与链表

        在Java中，Queue是个接口，底层是通过链表实现的 ，具体情况如下图所示；​​​
        

1.3 队列的基本使用方法

        下图是使用队列时具体的基本方法；

        注意：Queue是个接口，在实例化时该接口时，必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。 

2.用链表实现队列

        我们本次使用的是双向链表；

2.1创建队列

public class MyLLQueue {//创建静态内部类,实例对象作为队列中的节点public static class Node {int value;Node next;Node prev;public Node(int value) {this.value = value;}}public Node front;//双向链表的头结点public Node rear;//双向链表的尾结点public int usedSize = 0;//记录队列中节点个数
}

2.2入队列

        思路：

        1、创建一个要添加的值为value的节点node。

        2.1判断当前队列是否为空？即链表头结点front是否为null,若为null，则该node既是front（队头）和也是rear（队尾）。

        2.2若队头不为null，则将该节点的引用给当前队列的队尾的next，至此队尾就是我们新添加的节点；

        4、队列里面的数据容量加一。

        代码如下：

public boolean offer(int vale) {Node node = new Node(vale);if (isEmpty()) {front = node;rear = node;} else {rear.next = node;node.prev = rear;}rear = node;usedSize++;return true;}

2.3 判断队列是否为空

private boolean isEmpty() {return usedSize == 0;}

 2.4出队列

        1、队列为空，则直接返回队列为空的自定义异常。

public class EmptyException extends RuntimeException{public EmptyException(String msg) {super(msg);}
}

        2、队列此时不为空。

        2.1 此时队列中只有一个元素；（即队头的next域里存放的是空指针null），出队操作之后队列就为空，故此让队头和队尾都指向空指针；

        2.2 此时队列中有多个元素：让队头的后域指向下一个节点，队头的前域指向空指针；

        3、队列里面的数据容量减一；

//出队列---将双向链表第一个节点删除掉,并返回第一个删除节点的值public int poll() {// 1. 队列为空// 2. 队列中只有一个元素----链表中只有一个节点---直接删除// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException("队列为空,操作错误!!");}//用ret记录返回的队头元素的数据int ret = front.value;if (front.next == null) {//当前链表只有一个节点front = null;rear = null;usedSize--;return ret;}front = front.next;front.prev = null;usedSize--;return ret;}

2.5获取队头元素 

        思路类似于2,4部分

//获取队头元素的值,不出队列int peek(){if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException("队列为空,操作错误!!");}return front.value;}

2.6 双向链表（linkedlist）实现队列的完整代码

public class MyLLQueue {//创建静态内部类,实例对象作为队列中的节点public static class Node {int value;Node next;Node prev;public Node(int value) {this.value = value;}}public Node front;//双向链表的头结点public Node rear;//双向链表的尾结点public int usedSize = 0;//记录队列中节点个数//为了体现队列的先进先出特点,规定从尾入,从头出(也可以头进尾出)//插入操作,原理为双链表的尾插法public boolean offer(int vale) {Node node = new Node(vale);if (isEmpty()) {front = node;rear = node;} else {rear.next = node;node.prev = rear;}rear = node;usedSize++;return true;}private boolean isEmpty() {return usedSize == 0;}//出队列---将双向链表第一个节点删除掉,并返回第一个删除节点的值public int poll() {// 1. 队列为空// 2. 队列中只有一个元素----链表中只有一个节点---直接删除// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException("队列为空,操作错误!!");}//用ret记录返回的队头元素的数据int ret = front.value;if (front.next == null) {//当前链表只有一个节点front = null;rear = null;usedSize--;return ret;}front = front.next;front.prev = null;usedSize--;return ret;}//获取队头元素的值,不出队列int peek(){if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException("队列为空,操作错误!!");}return front.value;}//获取队列的长度public int size(){return usedSize;}public static void main(String[] args) {MyLLQueue myLLQueue = new MyLLQueue();System.out.println(myLLQueue.isEmpty());myLLQueue.offer(1);myLLQueue.offer(2);myLLQueue.offer(3);System.out.println(myLLQueue.size());System.out.println(myLLQueue.peek());System.out.println(myLLQueue.poll());System.out.println(myLLQueue.peek());System.out.println(myLLQueue.size());}
}

        测试结果如下：

           

3. 双端队列 (Deque)

        双端队列（deque）：是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

        Deque是一个接口，与queue类似在使用时必须创建LinkedList的对象，以下是详细图解：

        在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口，代码如下：

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

ps：本次内容就到这里，如果喜欢的话就请一键三连哦！！！