队列的数据项都是队列尾插入，然后移向队列头，并从队列头删除或者获取。
队列需要一个头指针(front)和尾指针(rear)，头指针会随着出队变动，rear会随着入队变动
两种常用队列 :线性队列，循环队列。
线性队列和循环队列的区别是：线性队列会产生假溢出，即头指针和尾指针都到了size大小
数组实现队列：LineQueue.java
package Queue; /** * @author zh * 利用数组模拟队列 * 队列有两个个指针：头指针，尾指针。出队时尾指针改变，入队是头指针改变 * 缺陷：假溢出（头指针与尾指针都为size），不采用 */ public class LineQueue { private int size;//队列大小 private int front;//头指针 private int rear;//尾指针 private Object data[] = null;//保存数据的数组 //默认构造函数 public LineQueue(){ this.size = 10; this.front = -1; this.rear = -1; this.data = new Object[this.size]; } //可改变大小的队列构造函数 public LineQueue(int size){ this.size =size; this.front = -1; this.rear = -1; this.data = new Object[this.size]; } //入队方法 public void inQueue(Object item){ //首先判断队列是否已满 if(rear < size-1){ //尾指针改变 rear++; //改变尾指针的值 data[rear] = item; }else{ System.out.println("队列已满"); } } //出队方法 public Object OutQueue() { Object item = null; //判断队列是否为空:头指针等于尾指针 if(rear == front){ System.out.println("队列为空"); } front++; item = data[front]; return item; } public void display(){ if(front != rear){ for(int i = front+1;i <= rear;i++){ System.out.println(data[i]); } } } public static void main(String[] args){ LineQueue queue = new LineQueue(20); for (int i= 0;i < 20;i++){ queue.inQueue(i); } // for(int i = 0 ;i < 20 ;i++){ // System.out.println(queue.OutQueue()); // } Object out = queue.OutQueue(); Object out2 = queue.OutQueue(); System.out.println(out2); // queue.display(); } }
链表实现队列：
节点类：Node.java
package Queue; /** * @author zh * 节点 */ public class Node { Object data; Node next; //头结点 public Node(){ data = null; next = null; } //构造节点：重载 public Node(Object data){ this.data = data; next = null; } }
队列类：LinkQueue.java
package Queue; /** * @author zh * 链表实现队列（线性队列） * 不需要判断是否为满，链表不存在已满情况 */ public class LinkQueue { Node head = null; public LinkQueue(){ head = new Node(); } //判断为空 public boolean empty(){ if(head.next == null) return true; return false; } //入队-->不需要判断满 public void inQueue(Object item){ //创建节点 Node data = new Node(item); Node temp = head; while(temp.next != null){ temp = temp.next; } temp.next = data; } //出队 public Object outQueue(){ Object item = null; if(empty()){ System.out.println("队列为空"); return item; } //获取第一个节点 item = head.next.data; //删除第一个节点 head.next = head.next.next; return item; } //遍历队列 public void display(){ Node temp = head; while(temp.next != null){ System.out.println(temp.next.data); temp = temp.next; } } public static void main(String[] args){ LinkQueue lq = new LinkQueue(); lq.inQueue(1); lq.inQueue(2); lq.inQueue(3); lq.inQueue(4); lq.inQueue(5); // System.out.println(lq.outQueue()); // System.out.println(lq.outQueue()); // System.out.println(lq.outQueue()); // System.out.println(lq.outQueue()); // System.out.println(lq.outQueue()); lq.display(); } }
循环队列：
实现：LoopQueue.java
package Queue; /** * @author zh * 循环队列:数组实现 */ public class LoopQueue { int size;//队列大小 int front;//头指针 int rear;//尾指针 Object data[] = null;//保存数据的数组 //默认构造函数 public LoopQueue(){ this.size = 10; this.front = 0; this.rear = 0; this.data = new Object[this.size]; } //可改变大小的队列构造函数 public LoopQueue(int size){ this.size =size; this.front = 0; this.rear = 0; this.data = new Object[this.size]; } //判断队列已满 public boolean full(){ if((rear+1)%size == front) return true; return false; } //判断队列为空 public boolean empty(){ if(rear == front) return true; return false; } //入队 public void inQueue(Object item){ if(full()) { System.out.println("队列已满"); }else{ //保证循环，不会出现假溢出 rear = (rear+1)%size; data[rear] = item; } } //出队 public Object outQueue(){ Object item = null; if(empty()){ System.out.println("队列为空"); }else{ front = (front+1)%size; item = data[front]; } return item; } //遍历队列 public void display(){ int f = front; int r = rear; while(f != r){ f = (f+1)%size; System.out.println(data[f]); } } public static void main(String[] args){ LoopQueue q = new LoopQueue(); q.inQueue(1); q.inQueue(2); q.inQueue(3); q.inQueue(4); q.inQueue(5); q.inQueue(6); q.inQueue(7); q.inQueue(8); q.inQueue(9); q.inQueue(10); q.inQueue(11); q.inQueue(12); q.inQueue(13); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); q.inQueue(14); q.inQueue(15); q.inQueue(16); q.inQueue(17); q.inQueue(18); q.inQueue(19); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); System.out.println("出队:"+q.outQueue()); } }