队列

定义：也称队，一端插入，另一端删除的运算受限的线性表。遵循FIFO（First In First Out）先进先出。
   一种特殊的线性表，在存储结构上分，顺序存储和链式存储，只是在操作上与普通线性表不一样。

队头（front）指针：删除数据端
队尾（rear）指针：插入数据端

顺序队列：队列的顺序存储结构
   特点：
       1.静态分配存储空间
       2.入队只能在队尾进行，出队只能在队头进行
       3.空队列，front = rear
       4.队列为满时，rear = 队列长度 - 1
       5.队列非空非满时，front < rear < 队列长度 - 1

链式队列：队列的链式存储结构（单链表）
   特点：
       1.动态分配存储空间
       2.入队在队尾进行，出队在队头进行
       3.链式队列为空队列条件：front = rear
       4.链式队列在入队时未队满的问题

范例：链式队列
1.队列操作的接口 - Queue

 1 /**
 2  * @Description: 队列操作的接口
 3  * @author Ivy
 4  */
 5 public interface Queue {
 6 //  队尾压入值
 7     public void push(Object item);
 8 //  查询并返回队头的值，且删除队头的值
 9     public Object pop();
10 //  查询并返回队头的值
11     public Object peek();
12 //  判断是否为空队列
13     public boolean isEmpty();
14 //  返回队列的大小值
15     public int size();
16     
17 }

2.队列操作的接口的实现类（链式队列） - LinkedQueue

 1 public class LinkedQueue implements Queue {
 2 
 3     private SingleLinkedList queueList;
 4     
 5     /**
 6      * 初始化单链表
 7      */
 8     public LinkedQueue(){
 9         queueList = new SingleLinkedList();
10     }
11     
12     @Override
13     public void push(Object item) {
14         queueList.add(item);
15 
16     }
17 
18     @Override
19     public Object pop() {
20         if (isEmpty()) {
21             throw new NoSuchElementException("LinkedQueue pop() : empty");
22         }
23         return queueList.remove(0);
24     }
25 
26     @Override
27     public Object peek() {
28         if (isEmpty()) {
29             throw new NoSuchElementException("LinkedQueue front : empty");
30         }
31         return queueList.get(0);
32     }
33 
34     @Override
35     public boolean isEmpty() {
36         return queueList.isEmpty();
37     }
38 
39     @Override
40     public int size() {
41         return queueList.size();
42     }
43 
44 }

3.测试类

 1 package com.Elastic.LinkedListDemo.ivy.test;
 2 
 3 import com.Elastic.LinkedListDemo.ivy.Queue;
 4 import com.Elastic.LinkedListDemo.ivy.impl.LinkedQueue;
 5 
 6 public class LinkedQueueTest {
 7 
 8     public static void main(String[] args) {
 9         Queue LQ = new LinkedQueue();
10         int i = 1001;
11         while (1 < 1011) {
12             LQ.push(i);
13             i++;
14         }
15 //        System.out.println("食堂打饭：");
16         /*while (!LQ.isEmpty()) {
17             System.out.println("
" + LQ.pop() + "打完饭离开打饭队伍；");
18         }*/
19 
20     }
21 
22 }