队列概述
队列是一种先进先出的线性表（first in first out，简称FIFO）。它只允许在队列的一段插入数据，另一端取出数据。允许插入数据的一端叫做队尾（rear），允许删除的一段则称为队头（front）。
队列无论在实际生活中还是在开发中都是非常常见的。比如我们去银行办理业务的排号系统就是队列。消息中间件也是队列的思想。
队列ADT
下面给出队列的抽象定义，在后文中我们将以此ADT开发队列的实现。
/**
* @author jaune
* @since 1.0.0
*/
public interface Queue<E> {
/**
* 查看队列中的第一个元素，仅仅查看元素，不从队列中取出。
* @return 队列中的第一个元素
* @throws NoSuchElementException 队列为空时抛出
*/
E peek();
/**
* 向队列中添加元素，元素添加到队尾。
*/
void push(E e);
/**
* 从队列中取出第一个元素。
* @return 队列中的第一个元素。
* @throws NoSuchElementException 队列为空时抛出
*/
E pop();
/**
* 清空队列并
*/
void clear();
/**
* 队列中元素的数量，如果队列为空，则返回0
*
* @return 队列中元素的数量
*/
int size();
/**
* 判断队列是否为空
* @return true-空，false-非空
*/
boolean isEmpty();
/**
* 判断队列是已满
* @return true-已满，false-未满
*/
boolean isFull();
}
使用数组实现的基本思想
定义两个指针，一个指向队头（front），一个指向队尾(rear)。
当从队列中取出元素时，front指针后移；当向队列中添加元素时rear指针后移。
当队头和队尾在同一个位置时，队列为空。
采用数组的方式实现队列的最大问题就是，当front和rear指针全部指向队列的尾部时，队列失效了。无法添加新的元素至队列中。当添加元素时因为指针指向队尾，所以出现队列已满的情况。在后面我将介绍如何处理这种情况。在本文中对这种情况不做处理。
代码实现
package com.codestd.study.queue;
import java.util.NoSuchElementException;
/**
* 数组队列的实现
*
* @author jaune
* @since 1.0.0
*/
public class ArrayQueue<T> implements Queue<T> {
final int maxSize;
final T[] queueArray;
private int front = -1;
private int rear = -1;
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.queueArray = (T[]) new Object[maxSize];
}
@Override
public T peek() {
if (this.isEmpty()) {
throw new NoSuchElementException("队列为空");
}
return this.queueArray[this.front + 1];
}
@Override
public void push(T t) {
if (this.isFull()) {
throw new RuntimeException("队列已满，无法添加新的元素。");
}
this.queueArray[++this.rear] = t;
}
@Override
public T pop() {
if (this.isEmpty()) {
throw new NoSuchElementException("队列为空");
}
T element = this.queueArray[++this.front];
this.queueArray[this.front] = null;
return element;
}
@Override
public int size() {
return this.rear - this.front;
}
/**
* 清空队列，并重置队头和队尾指针。
*/
@Override
public void clear() {
for (int i = (this.front + 1); i <= this.rear; i++) {
this.queueArray[i] = null;
}
this.front = -1;
this.rear = -1;
}
@Override
public boolean isEmpty() {
return this.rear == this.front;
}
@Override
public boolean isFull() {
return this.rear + 1 == this.maxSize;
}
}
测试代码
package com.codestd.study.queue;
import org.junit.Test;
import static org.assertj.core.api.Assertions.*;
/**
* Test for {@link ArrayQueue}
*/
public class ArrayQueueTest {
@Test
public void test() {
Queue<Integer> queue = new ArrayQueue<>(3);
assertThat(queue.isEmpty()).isTrue();
assertThat(queue.isFull()).isFalse();
queue.push(1);
assertThat(queue.isEmpty()).isFalse();
assertThat(queue.peek()).isEqualTo(1);
assertThat(queue.size()).isEqualTo(1);
int el = queue.pop();
assertThat(queue.isEmpty()).isTrue();
assertThat(el).isEqualTo(1);
queue.push(2);
queue.push(3);
assertThat(queue.isEmpty()).isFalse();
assertThat(queue.isFull()).isTrue();
assertThat(queue.size()).isEqualTo(2);
el = queue.pop();
assertThat(el).isEqualTo(2);
el = queue.pop();
assertThat(el).isEqualTo(3);
assertThat(queue.isFull()).isTrue();
assertThat(queue.isEmpty()).isTrue();
queue.clear();
assertThat(queue.isEmpty()).isTrue();
assertThat(queue.isFull()).isFalse();
queue.push(1);
queue.clear();
assertThat(queue.isEmpty()).isTrue();
assertThat(queue.isFull()).isFalse();
}
}
总结
前文中已经提到这种方式存在严重的问题，这是一个一次性的队列。在队列满了之后，就无法再往队列中插入数据了，哪怕数组中有空位置。要解决这个问题就需要用到环形数组。这部分的实现原理在下一篇文章中将。
