本文从通过Java Array 实现一个简单的队列和循环队列，最后对Java Queue 接口及其子类的特点进行一个总结
队列的存储结构
队列与栈不同，是一种先进先出的数据结构，元素从对头读取从队尾写入
示意图如下：
timg.jpeg
本文将使用Java 数组 来实现一个简单队列和一个循环队列，首先定义一个接口
public interface MyQueue<E> {
boolean enqueue(E e);
E dequeue();
}
简单队列
代码逻辑参考注释
public class MyArrayQueue<E> implements MyQueue<E>{
private Object[] elements;
private int capacity;
private int head = 0;
private int tail = 0;
public MyArrayQueue(int capacity){
this.capacity = capacity;
elements = new Object[this.capacity];
}
/**
* 入队 O(n)
* 1. tail == capacity ， 并且 head == 0 代表队列没有可用空间
* 2. 当队列有可用空间时，进行数据搬移
* @param e
* @return
*/
public boolean enqueue(E e) {
if(tail == capacity){
// 队列满了
if(head == 0){
return false;
}
for(int i=head;i<tail;i++){
elements[i-head] = elements[i];
}
tail = tail - head;
head = 0;
}
this.elements[tail] = e;
tail ++;
return true;
}
/**
* 出队 O(1)
* @return
*/
@SuppressWarnings("unchecked")
public E dequeue() {
if(head == tail){
return null;
}
E e = (E)elements[head];
head ++;
return e;
}
}
测试
@Test
public void myArrayQueueTest(){
MyQueue<String> queue = new MyArrayQueue<String>(5);
queue.enqueue("a");
Assert.assertEquals(queue.dequeue(),"a");
queue.enqueue("b");
Assert.assertEquals(queue.dequeue(),"b");
queue.enqueue("c");
Assert.assertEquals(queue.dequeue(),"c");
queue.enqueue("d");
queue.enqueue("e");
queue.enqueue("f");
queue.enqueue("g");
queue.enqueue("h");
Assert.assertFalse(queue.enqueue("s"));
Assert.assertEquals(queue.dequeue(),"d");
Assert.assertEquals(queue.dequeue(),"e");
Assert.assertEquals(queue.dequeue(),"f");
Assert.assertEquals(queue.dequeue(),"g");
Assert.assertEquals(queue.dequeue(),"h");
Assert.assertNull(queue.dequeue());
}
上个队列中，当队列慢时有数据搬移工作，整体效率不够，所有有了循环队列的实现
循环队列
public class MyCircularQueue<E> implements MyQueue<E> {
private Object[] elements;
private int capacity;
private int head = 0;
private int tail = 0;
public MyCircularQueue(int capacity){
this.capacity = capacity;
elements = new Object[capacity];
}
/**
* 入队 O(1)
* 1. (tail+1) % capacity == head 队满，比如 capacity = 5 , tail = 4 , head = 0
* 2. tail 元素添加后 tail 往后移动一位，当等于capacity 重新归 0
* @param e
* @return
*/
public boolean enqueue(E e) {
if((tail+1) % capacity == head){
return false;
}
this.elements[tail] = e;
tail = (tail+1) % capacity;
return true;
}
/**
* 出队 O(1)
* 1. head == tail 空队列
* 2. 去除元素后 head 往后移动一位，当等于capacity 重新归 0
* @return E
*/
@SuppressWarnings("unchecked")
public E dequeue() {
if(head == tail){
return null;
}
E e = (E)elements[head];
head = (head+1) % capacity;
return e;
}
}
测试
@Test
public void myCircularQueueTest(){
MyQueue<String> queue = new MyCircularQueue<String>(5);
queue.enqueue("a");
Assert.assertEquals(queue.dequeue(),"a");
queue.enqueue("b");
Assert.assertEquals(queue.dequeue(),"b");
queue.enqueue("c");
Assert.assertEquals(queue.dequeue(),"c");
queue.enqueue("d");
queue.enqueue("e");
queue.enqueue("f");
queue.enqueue("g");
Assert.assertFalse(queue.enqueue("h"));
Assert.assertEquals(queue.dequeue(),"d");
Assert.assertEquals(queue.dequeue(),"e");
Assert.assertEquals(queue.dequeue(),"f");
Assert.assertEquals(queue.dequeue(),"g");
Assert.assertNull(queue.dequeue(),"h");
}
队列作为一种重要的数据格式，在实际应用开发中占有重要地位，本文实现的队列都比较简单，在Java中根据队列不同的应用场景做了不一样的封装，下面总结一下Java 语言中不同队列的特点
Java Queue 接口
Queue接口在java.util包中可用，并扩展了Collection接口。队列集合用于保存要处理的元素，并提供各种操作。它是一个有序的对象列表，其使用仅限于在列表末尾插入元素并从头开始删除元素列表，即它遵循FIFO或先入先出原则。Queue的特征：
- Queue用于在队列末尾插入元素并从队列的开头删除。它遵循FIFO概念。
- Java Queue支持Collection接口的所有方法，包括插入，删除等。
- LinkedList，ArrayBlockingQueue、PriorityQueue是最常用的实现。
- 如果对BlockingQueues执行任何null操作，则抛出NullPointerException
- 带有 blocking 的队列是线程安全的，比如 ArrayBlockingQueue
- java.util 包中可用的队列是无界队列 ，使用不当容易造成内存泄漏
- java.util.concurrent 包中可用的队列是有界队列
- 除 Deques（双端队列）之外的所有队列分别支持在队列的尾部和头部插入和移除。Deques支撑元件在两端插入和移除
操作方法上的一些差别
- offer，add 入队操作，队满时 add 将抛出异常， offer 返回 false
- poll，remove 出队操作，remove 内部调用的是poll ,不过remove 发现元素为null时会抛出异常，poll 返回 null
- peek，element 用于在队列的头部查询元素，在队列为空时， element 抛出一个异常 , peek 返回 null
本文是学习极客时间数据结构与算法之美结合Java语言的一些笔记，如果你对此课程感兴趣可以在下载极客时间App搜索该课程,也可以点击下面链接查看
数据结构与算法之美
网友评论