数据结构-队列
1 队列概念
队列是一个能够实现先进先出的存储结构；只允许在队列一端插入，另一端删除。队列分为链式队列和固定队列；固定队列一般用数组来实现，可分为普通队列、环形队列；链式队列是用链表来实现队列的。
1.1 普通队列
- 每次出队操作，列头位置发生变化，其他元素位置不受影响，队尾位置到达队列大小时，即时队列不满，新的元素也无法添加进来，列头前位置将会被浪费
- 每次出队操作，列头位置不会发生变化，即后面元素统一向前移动一位，队尾位置也会受到影响；
- **比如：***我们生活中排队买票，每完成一次购票，前一个人离开后，后面的人依次向前移动；或者售票员依次把票给每位排队乘客，乘客另外票离开，但是剩余乘客位置不动。
- 这种方式在程序中资源损耗将很严重，缺点比较明显，通常是不建议使用的。*
1.2 环形队列
大小固定，效率高等优点。数据结构由数组构成，通过算法将数组首尾相连构成环形。每一次出队列操作，列头位置发生变化，其他元素位置不受影响；每一次新元素加入队列，队尾位置发生变化，且不影响队列其他元素。在队列大小固定情况下建议使用环形队列。
1.3 链式队列
容量上线，需要的时候再申请分配内存空间，可最大程度上实现灵活性。缺点是链式结构的链接字段需要消耗一定的内存，在链式结构中访问一个特定元素的效率不如数组。
2 实现原理
2.1 基本数据结构
// 列头位置,队尾位置,队列容量
int head,tail,capacity;
// 队列容器
Object[] items;
2.2 基本操作
// 新增元素入队
boolean add(T item);
// 移出队列
boolean remove();
//队列是否已满
boolean isFull();
//队列是否为空
boolean isEmpty();
3 实现方式
实现方式偏向于实际应用，所以会加一些基础结构之外的内容
3.1 接口定义
- 队列接口定义
public interface Queue<T>{
/**
* 参照 2.2基本操作
*/
//获取队列长度
int getLength();
//获取队列容量
int getCapacity();
//获取头元素，并移出队列
T get();
// 清空队列
void clear();
//遍历队列，通过钩子函数实现对元素的操作
void traverse(Collback<T> collback);
}
- 钩子函数定义
public interface Collback<T> {
void doCollBack(T t);
}
- 抽象类
public abstract class AbstractQueue<T> implements Queue<T> {
/** 列头元素位置*/
protected int head;
/** 队尾元素位置*/
protected int tail;
/** 队列项*/
protected Object[] items;
/** 队列实际大小*/
protected int length;
/** 队列容量*/
protected int capacity;
/** 默认队列容量*/
protected final static int DEFAULT_CAPACITY = 10;
@Override
public boolean isFull() {
return length >= capacity;
}
@Override
public boolean isEmpty() {
return length <= 0;
}
@Override
public int getLength() {
return length;
}
@Override
public int getCapacity() {
return capacity;
}
public void clear() {
head = 0;
length = 0;
tail = 0;
}
protected void init(int capacity) {
this.capacity = capacity;
clear();
items = new Object[capacity];
}
}
3.2 普通队列实现
这里只针对普通队列第一种情况实现，另一种情况无非每次出队时将所有数组下标减1，改变tail。
public class ArrayQueue<T> extends AbstractQueue<T> {
public ArrayQueue(){
init(DEFAULT_CAPACITY);
}
public ArrayQueue(int capacity){
init(capacity);
}
@Override
public boolean add(T item) {
if (isFull())
return false;
if (!isEmpty()) {
tail ++;
}
items[tail] = item;
length ++;
return true;
}
@Override
public boolean remove() {
if (isEmpty())
return false;
head ++;
length --;
return true;
}
@SuppressWarnings("unchecked")
@Override
public T get() {
if (isEmpty())
return null;
T item = (T) items[head];
clear();
return item;
}
@Override
public boolean isFull() {
return (tail + 1) >= capacity;
}
@SuppressWarnings("unchecked")
@Override
public void traverse(Collback<T> collback) {
for (int i = 0; i < length; i++) {
collback.doCollBack((T) items[i + head]);
}
}
}
3.3 环形队列实现
public class AnnularQueue<T> implements AbstractQueue<T> {
public AnnularQueue(){
init(DEFAULT_CAPACITY);
}
public AnnularQueue(int capacity){
init(capacity);
}
public boolean add(T item){
if (isFull())
return false;
if (!isEmpty()) {
tail ++;
if(tail == capacity)
tail = 0;
}
items[tail] = item;
length ++;
return true;
}
public boolean remove(){
if (isEmpty())
return false;
head ++;
if (head == capacity)
head = 0;
length --;
return true;
}
public T get(){
if (isEmpty())
return null;
T item = (T) items[head];
remove();
return item;
}
public void traverse(Collback<T> collback){
int i = head;
for (int j = 0; j < capacity; j++) {
i = (j + head) % capacity ;
collback.doCollBack((T) items[i]);
if (i == tail)
break;
}
}
}
3.3 链式队列实现
链式队列可以通过单项链表方式实现，通过下面代码可以很清楚的看到链式队列的优点
public class LinkedQueue<T> extends AbstractQueue<T> {
private Node root;
@Override
public boolean add(T item) {
if (root == null) {
root = new Node(item);
} else {
root.add(item);
}
return true;
}
@Override
public boolean remove() {
if(root == null){
return false;
}
root = root.getNext();
return true;
}
@Override
public T get() {
if (root == null) {
return null;
}
T t = root.get();
remove();
return t;
}
@Override
public void traverse(Collback<T> collback) {
Node next = root;
while (next != null) {
collback.doCollBack(next.get());
next = next.getNext();
}
}
private class Node {
private T t;
private Node next;
Node(T t) {
this.t = t;
}
private void add(T item) {
if (next == null) {
next = new Node(item);
} else {
next.add(item);
}
}
public T get() {
return t;
}
public Node getNext() {
return next;
}
}
}
4 测试
public class QueueTest {
public static void main(String[] args) {
Queue<Integer> linkedQueue = new LinkedQueue<Integer>();
for (int i = 0; i < 4; i++) {
linkedQueue.add(i);
}
for (int i = 0; i < 3; i++) {
linkedQueue.remove();
}
linkedQueue.traverse(new Collback<Integer>() {
@Override
public void doCollBack(Integer t) {
System.out.println(t);
}
});
/*Queue<Integer> arrayQueue = new ArrayQueue<Integer>(4);
for (int i = 0; i < 4; i++) {
arrayQueue.add(i);
}
for (int i = 0; i < 3; i++) {
arrayQueue.remove();
}
arrayQueue.traverse(new Collback<Integer>() {
@Override
public void doCollBack(Integer t) {
System.out.println(t);
}
});*/
/*Queue<Integer> annularQueue = new AnnularQueue<Integer>(4);
for (int i = 0; i < 4; i++) {
annularQueue.add(i);
}
for (int i = 0; i < 3; i++) {
annularQueue.remove();
}
for (int i = 0; i < 2; i++) {
annularQueue.add(i + 4);
}
annularQueue.traverse(new Collback<Integer>() {
@Override
public void doCollBack(Integer t) {
System.out.println(t);
}
});*/
}
}
