# Java队列实现
# 队列简介
队列是一种特殊的线性数据结构，遵循先进先出（FIFO）原则，队尾添加元素，从队头取出元素，就像排队买东西。队列运用范围很广，最典型的就是生产者消费者模式。
# 队列基本操作
- 入队：往队尾添加元素
- 出队：从队首取出元素
# 队列实现
- 顺序存储：基于数组
- 非顺序存储：基于链表
# 自己动手实现代码
- 先定义一个队列操作的接口：
public interface Queue<E> {
/**
* 添加元素到队尾
* @return
*/
boolean offer(E ele);
/**
* 从队首取出元素
* @return
*/
E poll();
/**
* 方便测试
*/
void print();
}
- 利用数组实现顺序存储的队列
实现思路1： 定义一个队尾的索引，每次添加元素存放在该索引上，然后索引自增1，当索引值达到容量值，表示队列满了。取的时候直接取第一个，然后把数组后面的元素往前移动。
public class ArrayQueue<E> implements Queue<E> {
/**
* 存放队列元素
*/
final Object[] eles;
/**
* 队尾索引
*/
int tail;
/**
* 最大容量
*/
int capacity;
public ArrayQueue(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException();
}
this.capacity = capacity;
this.tail = 0;
this.eles = new Object[capacity];
}
@Override
public boolean offer(E ele) {
if (ele == null) {
throw new NullPointerException();
}
if (tail == capacity) {
System.out.println("队列已满");
return false;
}
eles[tail] = ele;
tail++;
return true;
}
@Override
public E poll() {
if (tail == 0) {
System.out.println("队列中没有数据");
return null;
}
E e = (E) eles[0];
for (int i = 0; i < tail - 1; i++) {
eles[i] = eles[i + 1];
}
eles[tail - 1] = null;
tail--;
return e;
}
@Override
public void print() {
System.out.println(Arrays.toString(eles));
}
}
实现思路2：
public class ArrayQueue2<E> implements Queue<E> {
/**
* 存放队列元素
*/
final Object[] eles;
/**
* 队首索引
*/
int head;
/**
* 队尾索引
*/
int tail;
/**
* 最大容量
*/
int capacity;
public ArrayQueue2(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException();
}
this.capacity = capacity;
this.tail = 0;
this.head = 0;
this.eles = new Object[capacity];
}
@Override
public boolean offer(E ele) {
if (ele == null) {
throw new NullPointerException();
}
if (tail == capacity) {
if (head == 0) {
System.out.println("队列已满");
return false;
} else {
for (int i = head; i < tail; i++) {
eles[i - head] = eles[i];
eles[i] = null;
}
tail = tail - head;
head = 0;
}
}
eles[tail] = ele;
tail++;
return true;
}
@Override
public E poll() {
if (head == tail) {
System.out.println("队列中没有数据");
return null;
}
E e = (E) eles[head];
eles[head] = null;
head++;
return e;
}
@Override
public void print() {
System.out.println(Arrays.toString(eles));
}
}
实现思路3： 循环队列
public class ArrayQueue3<E> implements Queue<E> {
/**
* 存放队列元素
*/
final Object[] eles;
/**
* 队首索引
*/
int head;
/**
* 队尾索引
*/
int tail;
/**
* 最大容量
*/
int capacity;
/**
* 当前队列元素数量
*/
int count;
public ArrayQueue3(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException();
}
this.capacity = capacity;
this.tail = 0;
this.head = 0;
this.count = 0;
this.eles = new Object[capacity];
}
@Override
public boolean offer(E ele) {
if (ele == null) {
throw new NullPointerException();
}
if(count == capacity){
System.out.println("队列已满");
return false;
}
eles[tail] = ele;
tail = (tail + 1) % capacity;
count++;
return true;
}
@Override
public E poll() {
if (count == 0) {
System.out.println("队列中没有数据");
return null;
}
E e = (E) eles[head];
eles[head] = null;
head = (head + 1) % capacity;
count--;
return e;
}
@Override
public void print() {
System.out.println(Arrays.toString(eles));
}
}
- 利用链表实现队列
链表实现没有容量限制，定义head和tail节点，通过两个节点的指针变化来实现出队和入队。入队时，创建新节点追加到tail节点，再将tail节点指针后移；出队时，直接取head节点，并将head节点指针后移。
public class LinkedQueue<E> implements Queue<E> {
Node<E> head;
Node<E> tail;
@Override
public boolean offer(E ele) {
if (ele == null) {
throw new NullPointerException();
}
if (head == null) {
head = new Node(ele);
tail = head;
} else {
Node tmp = tail;
tail = new Node<>(ele);
tmp.next = tail;
}
return true;
}
@Override
public E poll() {
if (head == null) {
System.out.println("队列为空");
return null;
}
E e = head.getE();
if (head.next != null) {
head = head.next;
} else {
head = null;
}
return e;
}
@Override
public void print() {
for (Node<E> x = head; x != null; x = x.next) {
System.out.print(x.getE() + ",");
}
System.out.println();
}
class Node<E> {
E e;
Node<E> next;
public Node(E e) {
this.e = e;
}
public E getE() {
return e;
}
public void setE(E e) {
this.e = e;
}
}
}