数组队列
数组的子集
主要方法addLast( )和removeFirst( )
public interface IQueueDesc<E>{
void enqueue(E e);
E dequeue();
E getFront();
int getSize();
boolean isEmpty();
}
public class QueueMyList<E> implements IQueueDesc<E{
MyArray<E> array;
public QueueMyArray(){
this(10);
}
public QueueMyArray(int capacity){
array = new MyArray<>)(capacity);
}
// 入队
public void enqueue(E e){
array.addLast(e);
}
// 出队
public E dequeue(){
array.removeFirst();
}
// 获取第一个元素
public E getFront(){
array.getValueByInde(0);
}
public int getSize(){
return array.getSize();
}
public boolean isEmpty(){
return array.isEmpty();
}
}
缺点：
①队首出列后，后面的全部向前移动一个补缺
②出队移动补缺麻烦 时间复杂度O(n)
解决方案
不要往前移动，减少复杂度，采用双指针，front和tail，就可以解决这个问题。
此时缺点：
如果不断入队和出队，前面就会空了一大截，前面一大片空间就浪费了。
循环队列
主要是尾指针移到末尾后又会移动到队首。
问题：
1.如何判断队列是空的？
front == tail,可能是空也可能是满，防止歧义，强行规定front == tail就是空！！！
2.如何判断队列是满的？
tail + 1 == front 就是满了，要浪费1个空格子
(tail + 1) % 数组长度 == front 队列为满
3.指针怎么指向
front指向队首，tail指向队尾的下一个存储单元
使用循环队列实现
初始化
public class QueueMyList<E> implements IQueueDesc<E>{
private E[] data;
private int size;
private int front;
private int tail;
public QueueMyArray(){
this(10);
}
public QueueMyArray(int capacity){
// 要随时记得 我们自己定义的循环队列故意浪费了一个坑 所以要capacity+1
this.data = (E[])new Object[capacity+1];
//参数初始化
this.size = 0;
this.front = 0;
this.tail = 0;
}
// 入队
public void enqueue(E e){
// 队列满了
if(((tail+1) % data.length) == front){
// 扩容
resize(getCapacity()*2);
}
// 正常插入队里
data[tail] = e;
// 注意！！！！！！！这个地方容易出错 出界!不能用getCapacity
tail = (tail+1) % data.length;
size++;
}
// 出队
public E dequeue(){
if(isEmpty()){
throw new RunTimeException("队列为空。。。");
}
size--;
int result = data[front];
// 记得处理游离对象！！！！！！！！！！！！！！！！！！！
data[front] = null;
front = (front+1) % data.length;
// 缩容!!变成原来四分之一长度才缩容，要不到2如果缩容就变成 1/2 = 0 就缩没了
// 如果设置一半会和getCapacity()/2 != 0有冲突 还要加判断麻烦
if(size == getCapacity()/4 && getCapacity()/2 != 0){
// 缩成原来一半
resize(getCapacity()/2);
}
return result;
}
// 获取第一个元素
public E getFront(){
if(isEmpty()){
throw new RunTimeException("队列为空。。。");
}
return data[front];
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return tail == front;
}
public int getCapacity(){
// 注意！！！！这点非常容易错
return data.length - 1;
}
private void resize(int capacity){
// 一定要记得+1啊！！！！！！！！！！！
E[] newData = (E[])new Object[capacity+1];
// 拷贝是全部移动到新数组的头部！！而不是原来位置
for(int i=0;i < size;i++){
newData[i] = data[front+i % data.length];
}
data = newData;
front = 0;
tail = size;
}
}数组队列先插10万个数，再出队10万个数耗时4.4秒
循环队列先插10万个数，再出队10万个数耗时0.01秒
改良【不浪费一个坑】
public interface ILoop<T>{
void enqueue(T e);
T dequeue();
T peek();
int getSize();
boolean isEmpty();
boolean isFull();
void resize(int capacity);
}public class MyLoopQueue<E> implements ILoopQueue<E>{
private E[] data;
private int size;
private int capacity;
private int front;
private int tail;
public QueueMyArray(){
this(10);
}
public QueueMyArray(int capacity){
// 这里没有浪费一个空间
this.data = (E[])new Object[capacity];
//参数初始化
this.size = 0;
this.front = 0;
this.tail = 0;
this.capacity = capacity;
}
// 入队
public void enqueue(E e){
// 队列满了 不用指针判断 用个数判断
if(size == capacity){
// 扩容
resize(getCapacity()*2);
}
// 正常插入队里
data[tail] = e;
// 注意！！！！！！！这个地方容易出错 出界!不能用getCapacity
tail = (tail+1) % data.length;
size++;
}
// 出队
public E dequeue(){
if(size == 0){
throw new RunTimeException("队列为空。。。");
}
size--;
int result = data[front];
// 记得处理游离对象！！！！！！！！！！！！！！！！！！！
data[front] = null;
front = (front+1) % data.length;
// 缩容!!变成原来四分之一长度才缩容，要不到2如果缩容就变成 1/2 = 0 就缩没了
// 如果设置一半会和getCapacity()/2 != 0有冲突 还要加判断麻烦
if(size == getCapacity()/2){
// 缩成原来一半
resize(getCapacity()/2);
}
return result;
}
// 获取第一个元素
public E getFront(){
if(isEmpty()){
throw new RunTimeException("队列为空。。。");
}
return data[front];
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return tail == front;
}
public int getCapacity(){
// 注意！！！！这点非常容易错
return data.length - 1;
}
private void resize(int capacity){
this.capacity = capacity;
// 不需要加1
E[] newData = (E[])new Object[capacity];
// 拷贝是全部移动到新数组的头部！！而不是原来位置
for(int i=0;i < size;i++){
newData[i] = data[front+i % data.length];
}
data = newData;
front = 0;
tail = size;
}
}
