普通队列和循环队列的Java实现

什么是队列

对于数组来说，我们可以通过下标值拿到每一个具体的元素。但是有些时候我们需要一种限制存取顺序的数据结构，此时队列和栈便派上了用场。

队列与栈的不同之处在于，队列是先进先出（FIFO）而栈是后入先出（LIFO），其实队列二字“名副其实”，我们可以将其理解为日常生活中的排队：当我们在超市收银台结账时，肯定是排在前面的顾客先结账，然后依次是后面的顾客结账（不考虑某些人的插队行为）。

在这里插入图片描述

如上图所示，队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。删除（delete）操作也被称为出队（dequeue)。你只能移除第一个元素。

顺序队列

顺序队列可以基于动态数组和指向头部的指针的方式实现的，是连续的一块内存空间。其结构如下图：

按照上述，其实现也十分简单，下面给出一种实现

public class MyQueue {  //存储数据 private List<Integer> data; //指向队列头部数据的指针 private int p_start; public MyQueue() {  this.data = data = new ArrayList<Integer>(); this.p_start = 0; } //数据入列 public Boolean enQueue(int x){  data.add(x); return true; } //数据出列 public Boolean deQueue(){  if (isEmpty()){  return false; } p_start++; return true; } //获取队列头的元素 public int getFront(){  return data.get(p_start); } //判断是否为空 public Boolean isEmpty(){  return p_start >= data.size(); } public static void main(String[] args) {  MyQueue myQueue = new MyQueue(); myQueue.enQueue(1); myQueue.enQueue(2); myQueue.enQueue(3); myQueue.enQueue(4); System.out.println(myQueue.getFront()); myQueue.deQueue(); System.out.println(myQueue.getFront()); } }

顺序队列的缺点

顺序队列的实现确实很简单，但是随着我们对一部分数据进行出队操作后，头部指针会渐渐后移，而头部指针前面的空间虽然已经被释放，但是它既不能被回收也不能被再次利用，造成了很大的空间浪费，我们当然可以每次队列满了以后将数据总体前移（如下图所示），这样虽然保证了空间不会被浪费，但是时间复杂度从O(1)变成了O(n)，也是非常大的性能开销。

循环队列

上述通过数组来实现的队列，我们虽然进行了优化，但是当有空间无法利用时时，还是会进行一次数据搬移，性能也会收到影响，能否避免数据呢？答案是肯定的，看一下循环队列的解决思路。

循环队列就相当于一个圆环，数组可以想象成一条直线，我们把这条直线掰成一个圆环，就是循环队列，为了更形象的表示，可以看下图所示：

循环队列中，我们需要两个指针，即head和tail分别指向队列的头和尾，当队列初始化时，head和tail都指向索引为0的位置。如果有数据入队，tail则后移一次，如果有数据出队，head则后移一次。

但是上述的过程会出现一系列问题：

如果数组的大小为4，当tail指向3时，怎样让下一次入队时tail指向0（假设0位置可以插入）而不是指向4（指向4就造成数组下标越界了）？
当队列空或者满时，都存在head=tail，如何判断队列到底是空还是满？

下面我们逐个解决

关于指针越界的问题其实很简单，我们只需要每次在对tail或者head加1时进行一次取余操作，即
```
(head + 1) % size;
```
关于判断队列空和满状态的问题，我的思路是：舍弃一个存储空间。也就是说如果tail的下一个是head，那么现在tail指向的空间就不再存储数据。如果是队列不断进行出队操作，head渐渐“追上”tail时，会出现head=tail的情况，此时队列为空。

总结一下：舍弃队列的最后一个存储空间，那么队列为空的标志是(tail + 1) % size = head，队列为满的标志是head = tail。

为了满足用户的需求，在实现时我们必须保证用户请求的空间数，因此具体到代码实现上，我们初始化队列时就初始化一个比用户申请空间大1的数组。下面给出一种代码实现：

public class MyCircularQueue {  private int[] data; private int head; private int tail; private int size; /** * Initialize your data structure here. Set the size of the queue to be k. */ public MyCircularQueue(int k) {  //初始化一个比用户要求大1的数组 size = k+1; data = new int[size]; head = 0; tail = 0; } /** * Insert an element into the circular queue. Return true if the operation is successful. */ public boolean enQueue(int value) {  if (isFull()) {  return false; } data[tail] = value; tail = (tail + 1) % size; return true; } /** * Delete an element from the circular queue. Return true if the operation is successful. */ public boolean deQueue() {  if (isEmpty()){  return false; } head = (head + 1) % size; return true; } /** * Get the front item from the queue. */ public int Front() {  if (isEmpty()){  return -1; } return data[head]; } /** * Get the last item from the queue. */ public int Rear() {  if (isEmpty()){  return -1; } //之所以要加上size是因为此处tail可能是0 return data[(tail - 1 + size) % size]; } /** * Checks whether the circular queue is empty or not. */ public boolean isEmpty() {  return head == tail; } /** * Checks whether the circular queue is full or not. * 如果仅仅使用tail == head来判断队列是否满，则无法判断到底是空还是满 * 因此要牺牲最后一个存储单元。即如果tail的下一个是head，就认为满了 */ public boolean isFull() {  return (tail + 1) % size == head; } }