队列是一个动态集合，作为数据结构中最常用的数据类型，其实现了先进先出（first-in,first-out，缩写FIFO）的策略。
我们把作用于队列上的insert操作称为入队（enqueue）,把作用于队列上的delete操作称为出队（dequeue）,和栈的pop一样，出队也是一个无参方法。队列的FIFO性质就想我们排了一个队伍做核酸一样，新来同学排在队尾，队首的同学也是来的最早入队的。
二、两种不同实现方式1，使用数组实现
初始化一个固定大小的数组容器，并声明一个存放队首元素的角标head,以及一个指向队尾+1的角标tail。当有对象入队时，将元素放入tail角标的容器位置上，再将tail向后移动一位。当出队时返回head角标的元素array[head]，然后将head也进行+1向后移动一位。
入队：
出队：
package com.xiaohui.basics.queue.array;
public class MyArrayQueue {
private int head;
private int tail;
private Integer[] arrayVals;
public Integer enqueue(Integer val){
// % 运算主要是为了当数组尾部满了后，数组前面为空时可以继续入队
tail = tail % arrayVals.length;
arrayVals[tail++] = val;
return val;
}
public Integer dequeue(){
return arrayVals[head++];
}
public MyArrayQueue(int size) {
this.arrayVals = new Integer[size];
}
}
测试类：
package com.xiaohui.basics.queue;
import com.xiaohui.basics.queue.array.MyArrayQueue;
import com.xiaohui.basics.queue.linked.Node;
public class QueueApplicaion {
public static void main(String[] args) {
arrayQueueTest();
}
private static void arrayQueueTest() {
MyArrayQueue queue = new MyArrayQueue(15);
queue.enqueue(5);
queue.enqueue(2);
queue.enqueue(0);
queue.enqueue(1);
Integer pop = queue.dequeue();
System.out.println(pop);
Integer pop2 = queue.dequeue();
System.out.println(pop2);
Integer pop3 = queue.dequeue();
System.out.println(pop3);
}
}
打印输出：
D:Javajdk1.8.0_131binjava.exe ... 5 2 0 Process finished with exit code 0
2，使用链表实现
定义一个节点对象Node（包含一个存储节点值的value，以及一个指向下一个节点的指针next）， 声明一个指向队首的指针head,以及一个指向队尾的指针tail。当第一个对象入队时，将head和tail同时指向该入队元素。当再有元素入队时，将队尾元素的next 指针指向新入队的元素，再将tail指向新入队的元素。当出队时返回head指向的元素，将head修改为head之前指向的元素的next指向对象。
入队：
出队：
定义节点Node：
package com.xiaohui.basics.queue.linked;
public class Node {
private Node next;
private Integer value;
public Node(Integer value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
}
定义队列
package com.xiaohui.basics.queue.linked;
public class MyLinkedQueue {
private Node head;
private Node tail;
public Node push(Node item){
// 第一次入队
if(head == null){
head = item;
}else {
tail.setNext(item);
}
tail = item;
return item;
}
public Node pop(){
Node headItem = head;
head = head.getNext();
return headItem;
}
}
测试类：
package com.xiaohui.basics.queue;
import com.xiaohui.basics.queue.linked.MyLinkedQueue;
import com.xiaohui.basics.queue.linked.Node;
public class QueueApplicaion {
public static void main(String[] args) {
linkedQueueTest();
}
private static void linkedQueueTest() {
MyLinkedQueue linkedQueue = new MyLinkedQueue();
linkedQueue.push(new Node(5));
linkedQueue.push(new Node(2));
linkedQueue.push(new Node(0));
linkedQueue.push(new Node(1));
Node pop = linkedQueue.pop();
System.out.println(pop.getValue());
Node pop2 = linkedQueue.pop();
System.out.println(pop2.getValue());
Node pop3 = linkedQueue.pop();
System.out.println(pop3.getValue());
}
}
输出：
D:Javajdk1.8.0_131binjava.exe ... 5 2 0 Process finished with exit code 0
