队列：先进先出
两种实现方式：
1.利用数组
2.链式存储
需要两个变量指向队头front和队尾rear，当入队时，队尾后移；出队时，队头后移
使用数组实现，当我们入队至数组满，然后出队至数组空，此时虽然数组为空，但是却不能再入队了，因为队尾rear已经指向了数组的最后一个索引位置。那么如何充分利用数组呢？
通过一定的计算操作使得数组虚拟为环形的数组
package dream.linearlist.queue;
/**
* 队列：底层用数组实现
* 规定队列使用数组的n-1个空间
*/
public class ArrQueue {
private int front,rear;
private Object[] queue;
private int maxSize;
public ArrQueue(int maxSize){
this.maxSize = maxSize;
queue = new Object[maxSize];
}
public boolean isEmpty(){
return front == rear;
}
public boolean isFull(){
return (rear+1)%maxSize == front;
}
public void addQ(Object o){
if((rear + 1)% maxSize == front){
System.out.println("队列已满，不能再入列...");
return;
}
rear = (rear + 1) % maxSize;
queue[rear] = o;
}
public Object deleteQ(){
if(front == rear){
System.out.println("队列为空，不能再出列...");
return null;
}
front = (front + 1) % maxSize;
return queue[front];
}
public void display(){
for(int i = front + 1;i <= rear || i < (rear + 1) % maxSize;i ++){
System.out.print(queue[i]+" ");
}
System.out.println();
}
public static void main(String[] args){
ArrQueue aq = new ArrQueue(6);
aq.addQ(2);
aq.addQ(3);
aq.addQ(4);
aq.addQ(5);
aq.deleteQ();
aq.display();
System.out.println(aq.isEmpty());
}
}链表可谓是队列的最佳实现结构，因为链表没有长度的限制。
package dream.linearlist.queue;
/**
* 队列：使用链表实现
*/
class Node{
Object data;
Node next;
public Node(Node next,Object data){
this.next = next;
this.data = data;
}
public Node(Object data){
this(null,data);
}
public Node(){
this(null,null);
}
}
public class LinkQueue {
private Node front;
private Node rear;
public LinkQueue(){
front = rear = null;
}
public boolean isEmpty(){
return front == null;
}
public void addQ(Object o){
Node newNode = new Node(o);
//如果是空队列，头和尾均指向新节点
if(front == null){
front = rear = newNode;
return;
}
//否则新节点增加至尾指针后，同时尾指针后移，指向新增的节点
rear.next = newNode;
rear = newNode;
}
public Object deleteQ(){
//如果队列为空
if(front == null){
System.out.println("队列为空，不能再出列...");
return null;
}
//如果队列只有一个元素
Node curr = front;
if(front == rear && rear != null){
front = rear = null;
}
front = front.next;
return curr.data;
}
public void display(){
Node tem = front;
while(tem != rear){
System.out.print(tem.data+" ");
tem = tem.next;
}
System.out.println(rear.data);
}
public static void main(String[] args){
LinkQueue lq = new LinkQueue();
lq.addQ(2);
lq.addQ(3);
lq.addQ(4);
lq.addQ(5);
lq.deleteQ();
lq.display();
System.out.println(lq.isEmpty());
}
}