数据结构和算法一-队列的简单实现
1 队列常用的APIadd：将指定的元素插入到此队列中（如果立即可行且不会违反容量限制），在成功时返回 true，如果当前没有可用空间，则抛出 IllegalStateException。offer：将指定元素插入到此队列的尾部（如果立即可行且不会超出此队列的容量），在成功时返回 true，如果此队列已满，则返回 false。可以指定超时时间put：将指定元素插入到此队列的尾部，如有必要，则等待空
·
1 队列常用的API
add：将指定的元素插入到此队列中（如果立即可行且不会违反容量限制），在成功时返回 true，如果当前没有可用空间，则抛出 IllegalStateException。
offer：将指定元素插入到此队列的尾部（如果立即可行且不会超出此队列的容量），在成功时返回 true，如果此队列已满，则返回 false。可以指定超时时间
put：将指定元素插入到此队列的尾部，如有必要，则等待空间变得可用。
remove：若队列为空，抛出NoSuchElementException异常。
poll：若队列为空，返回null。可以指定超时时间
take：若队列为空，发生阻塞，等待有元素
本文只实现简单队列，不考虑put和take方法
2 定义一个抽象类Queue
/**
* @author huwenlong
* @date 2019/12/7 10:36
*/
public abstract class Queue<T> {
/**
* 添加一个元素,成功返回true,若队列已满抛异常
* @param t
* @return
*/
public boolean add(T t) {
if (offer(t)) {
return Boolean.TRUE;
}
throw new RuntimeException("queue is full");
}
/**
* 添加一个元素,成功返回true,若队列已满返回false
* @param t
* @return
*/
abstract boolean offer(T t);
/**
* 移除并返回队列头部元素,如果为空则抛异常
* @return
*/
public T remove() {
T t = poll();
if (Objects.nonNull(t)) {
return t;
}
throw new RuntimeException("queue is empty");
}
/**
* 移除并返回队列头部元素,如果为空则返回空
* @return
*/
abstract T poll();
/**
* 获取但不移除队列头部元素,如果队列为空则抛异常
* @return
*/
public T element() {
T t = peek();
if (Objects.nonNull(t)) {
return t;
}
throw new RuntimeException("queue is empty");
}
/**
* 获取但不移除队列头部元素,如果队列为空则返回空
* @return
*/
abstract T peek();
abstract int length();
abstract boolean isFull();
abstract boolean isEmpty();
abstract void reverse();
}3 通过数组实现队列
/**
* @author huwenlong
* @date 2019/12/1 15:00
* 约定:
* firstIndex:第一个元素下标
* lastIndex:最后一个元素下标。
* 如果队列为空或者队列只有1个元素，lastIndex == firstIndex
* 队列为空条件:eles[firstIndex] == null;
* 队列为满条件:firstIndex == lastIndex + 1 || firstIndex == 0 && lastIndex == size - 1
*/
public class CycleArrayQueue2<T> extends Queue<T> {
/**
* 有效数据最大值
*/
private int size;
/**
* 第一个元素下标,初始值为0
*/
private int firstIndex;
/**
* 最后一个元素下标,初始值为0
*/
private int lastIndex;
private Object[] eles;
public CycleArrayQueue2(int size) {
this.size = size;
eles = new Object[this.size];
}
@Override
public boolean offer(T t) {
if (isFull()) {
return Boolean.FALSE;
}
if (!isEmpty()) {
// 如果数组不为空则lastIndex后移
lastIndex = (lastIndex + 1) % size;
}
// 放置元素
eles[lastIndex] = t;
return Boolean.TRUE;
}
@Override
public T poll() {
if (isEmpty()) {
return null;
}
T t = (T) eles[firstIndex];
// gc
eles[firstIndex] = null;
if (firstIndex != lastIndex) {
// 如果元素多于一个则firstIndex后移
firstIndex = (firstIndex + 1) % size;
}
return t;
}
@Override
public T peek() {
return (T) eles[firstIndex];
}
@Override
public int length() {
if (isEmpty()) {
return 0;
}
return lastIndex < firstIndex? lastIndex + 1 - firstIndex + size: lastIndex + 1 - firstIndex;
}
@Override
public boolean isFull() {
return firstIndex == lastIndex + 1 || firstIndex == 0 && lastIndex == size - 1;
}
@Override
public boolean isEmpty() {
return Objects.isNull(eles[firstIndex]);
}
@Override
void reverse() {
// 新建一个数组
Object[] temp = new Object[size];
int length = length();
int newLastIndex = length - 1;
// 数据迁移到新数组中
while (!isEmpty()) {
temp[-- length] = poll();
}
// 修改firstIndex和lastIndex
firstIndex = 0;
lastIndex = newLastIndex;
// eles更新
eles = temp;
}
}4 通过链表实现
public class LinkedQueue<T> extends Queue<T> implements Iterable<T> {
private Node<T> first;
private int size;
public LinkedQueue(int size) {
this.size = size;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node<T> node = first;
@Override
public boolean hasNext() {
return node != null;
}
@Override
public T next() {
if(Objects.isNull(node)) {
return null;
}
T t = node.data;
node = node.next;
return t;
}
};
}
@Override
public boolean offer(T t) {
if (isFull()) {
return Boolean.FALSE;
}
Node<T> node = new Node<>();
node.setData(t);
Node temp = first;
if (Objects.isNull(temp)) {
// 如果首节点为空则把新元素设置为首节点
first = node;
}else {
// 如果首节点不为空则把新元素追加到尾节点
while (Objects.nonNull(temp.next)) {
temp = temp.next;
}
temp.next = node;
}
return Boolean.TRUE;
}
@Override
public T poll() {
if(Objects.isNull(first)) {
return null;
}
// 直接返回首元素
T t = first.data;
first = first.next;
return t;
}
@Override
public T peek() {
return Objects.isNull(first)? null: first.data;
}
@Override
public int length() {
// 遍历链表获取长度
int index = 0;
Node temp = first;
while (Objects.nonNull(temp)) {
index ++;
temp = temp.next;
}
return index;
}
@Override
public boolean isFull() {
return length() == size;
}
@Override
public boolean isEmpty() {
return length() == 0;
}
/**
* 定义一个Node,有一个next指向下个元素
* @param <T>
*/
@Data
private class Node<T> {
private T data;
private Node<T> next;
}
@Override
public void reverse() {
if (Objects.isNull(first)) {
return;
}
// 当前节点
Node<T> current = first;
// 反转后当前节点的下一个节点，初始时候为空
Node<T> reverseNext = null;
while (Objects.nonNull(current)) {
// 定义一个节点指向当前节点下个节点
Node<T> next = current.next;
// 当前节点下个节点指向reverseNext
current.next = reverseNext;
// reverseNext往后走
reverseNext = current;
// 当前节点往后走
current = next;
}
first = reverseNext;
}
}5 测试代码
5.1 测试添加删除
@Test
public void testQueue() {
int size = 10;
System.out.println("--------------test CycleArrayQueue--------------");
testQueue(new CycleArrayQueue2<>(size), size);
System.out.println("--------------test LinkedQueue--------------");
testQueue(new LinkedQueue<>(size), size);
}
private void testQueue(Queue<Integer> queue, int size) {
for (int i = 0; i < size + 1; i ++) {
System.out.println("add " + i + ", result:" + queue.offer(i) + ", length:" + queue.length());
}
System.out.println("-------------------");
for (int i = 0; i < size / 2; i ++) {
System.out.println("remove " + queue.poll() + ", length:" + queue.length());
}
System.out.println("-------------------");
for (int i = 0; i < size + 1; i ++) {
System.out.println("add " + i + ", result:" + queue.offer(i) + ", length:" + queue.length());
}
System.out.println("-------------------");
for (int i = 0; i < size + 1; i ++) {
System.out.println("remove " + queue.poll() + ", length:" + queue.length());
}
}4.2 测试反转
private void testReverse(Queue<Integer> queue, int size) {
for (int i = 0; i < size / 2; i ++) {
System.out.println("add " + i + ", result:" + queue.offer(i) + ", length:" + queue.length());
}
System.out.println("-----------reverse------------");
queue.reverse();
for (int i = 0; i < size + 1; i ++) {
System.out.println("remove " + queue.poll() + ", length:" + queue.length());
}
for (int i = 0; i < size + 1; i ++) {
System.out.println("add " + i + ", result:" + queue.offer(i) + ", length:" + queue.length());
}
System.out.println("-----------reverse------------");
queue.reverse();
for (int i = 0; i < size + 1; i ++) {
System.out.println("remove " + queue.poll() + ", length:" + queue.length());
}
}
@Test
public void testReverse() {
int size = 10;
System.out.println("--------------test CycleArrayQueue--------------");
testReverse(new CycleArrayQueue2<>(size), size);
System.out.println("--------------test LinkedQueue--------------");
testReverse(new LinkedQueue<>(size), size);
}
CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！
更多推荐
0
0- 0
已为社区贡献3条内容
所有评论(0)