队列概述
队列是一种先进先出的线性表 (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();
- }
- }
总结
前文中已经提到这种方式存在严重的问题, 这是一个一次性的队列. 在队列满了之后, 就无法再往队列中插入数据了, 哪怕数组中有空位置. 要解决这个问题就需要用到环形数组. 这部分的实现原理在下一篇文章中将.
来源: http://www.jianshu.com/p/513d65f8206f