队列

概念介绍　

　　有同学想看队列，今天它来了！你去购物消费需要它，你去医院挂号看病需要它，你去银行取钱也需要它（你是VIP？请走开！），它被称为“和谐一号”！

　　一个和谐的队列有什么特点？大家回忆一下，去买东西时，是不是排在你前面的人能够先结账从而离开这个队列，而后面来想付款的人，只能往队列的最后边加入进行排队，因此，队列的特点呼之欲出，那就是：先进先出，在我们的购物场景中，先进行排队的，能够先结账。

代码实现

　　接下来，我们将用代码来实现队列！队列是一个有序列表，可以用数组或是链表来实现，遵循先入先出的原则，这是队列的特点。我们要实现的是循环队列。什么是循环队列呢？环形队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。

　　举个例子，我们定义一个长度为4的队列，1,2,3,4依次入队，那么现在队列中的情况是[1,2,3,4],如果我们想下一个数5入队，显然是不行的，因为队列满了，我们需要队列中有数字离开，根据先进先出原则，1必须得离开，1离开后的队列为[X,2,3,4],这时候5入队，5是最后一个入队的，但是它的位置却是原来1在的地方，也就[5,2,3,4],存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间也就是这么个意思，不知道大家理解没有？反正我是懂了。。。

　　队列的属性定义：

1     // 表示队列的长度
2     private int maxQueueSize;
3     // head表示队列的头指向，初始值 = 0
4     private int head;
5     // head表示队列的尾指向，初始值 = 0
6     private int tail;
7     // 该数组用于存放真实的数据
8     private int[] dataArr;

　　四个属性，都有用，别少了哦。

　　队列的带参构造方法，用于创建队列，传入的参数为队列长度-1：

1     public CircleQueue(int queueSize) {
2         maxQueueSize = queueSize + 1;
3         dataArr = new int[maxQueueSize];
4     }

　　接下来是一些通用方法的实现：

1     // 判断队列是否为空
2     public boolean isEmpty() {
3         return tail == head;
4     }

1     // 判断队列是否已满
2     public boolean isFull() {
3         return (tail + 1) % maxQueueSize == head;
4     }

　　说明：在循环队列中，当队列为空时，有tail = head ，而当所有队列全占满时，也有tail = head。为了区别这两种情况，我们定义的循环队列最多只能有maxQueueSize -1个元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是tail = head，而队列判满的条件是head=(tail + 1) % maxQueueSize。

　　入队：只在队列的尾（tail）进行添加操作

 1     public void addData(int n) {
 2         if (isFull()) {
 3             System.out.println("队已列满，不能加入数据！");
 4             return;
 5         }
 6 
 7         dataArr[tail] = n;
 8         tail = (tail + 1) % maxQueueSize;
 9         System.out.println(tail);
10     }

　　出队：只在队列的头（head）进行删除操作

 1 public int getData() {
 2         if (isEmpty()) {
 3             throw new RuntimeException("队列为空，不能取数据");
 4         }
 5         // 先把 head 对应的值保留到一个临时变量
 6         int value = dataArr[head];
 7         // 将 head 后移, 取模
 8         head = (head + 1) % maxQueueSize;
 9         // 将临时保存的变量返回
10         return value;
11     }

　　至此，代码编写完成，Git地址：https://github.com/HollowCup/algorithms-and-data-structure，具体实现位于data-structure工程下的queue目录，如果发现不足之处，请联系我进行更改，十分感谢！关注我，为社会和谐文明而排队的你点赞!

队列

推荐阅读