0 课程地址
https://coding.imooc.com/lesson/207.html#mid=13424
1 重点关注
1.1 循环队列代码实现（出队复杂度为O(1)）
见3.1
2 课程内容
3 Coding
3.1 循环队列代码实现 重点：
/**
* 循环队列入队 队尾插入元素
* @author weidoudou
* @date 2022/10/23 17:49
* @param e 请添加参数描述
* @return void
**/
@Override
public void enQueue(E e) {
//1 判断队列是否是满的，满的话进行扩容
if((tail+1)% data.length==front){
//扩容操作
enSize(getCapacity()*2);
}
//2 队尾插入元素
data[tail] = e;
tail = (tail+1)% data.length;
size++;
}
/**
* 扩容操作
* @author weidoudou
* @date 2022/10/23 17:55
* @param newCapacity 请添加参数描述
* @return void
**/
private void enSize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity+1];
for(int i = 0;i<size;i++){
newData[i] = data[(i+front)% data.length];
}
front = 0;
tail = size;
data = newData;
}
/**
* 循环队列出队 队首删除元素
* @author weidoudou
* @date 2022/10/26 7:50
* @param
* @return E
**/
@Override
public E deQueue() {
//1 判断循环队列是否为空
if(isEmpty()){
throw new IllegalArgumentException("空队列不允许出队");
}
//2 出队
E ret = data[front];
data[front] = null;
front = (front+1)% data.length;
size--;
//3 动态缩容
if(size== getCapacity()/4 && getCapacity()/2!=0){
enSize(getCapacity()/2);
}
return ret;
}
3.2 循环队列代码实现 全量：
- 接口：
package com.company;
/**
* 队列接口
* @author weidoudou
* @date 2022/10/23 11:10
* @return null
**/
public interface Queue<E> {
/**
* 循环队列入队 队尾插入元素
* @author weidoudou
* @date 2022/10/23 11:10
* @param e 请添加参数描述
* @return void
**/
void enQueue(E e);
/**
* 循环队列出队 队首删除元素
* @author weidoudou
* @date 2022/10/23 11:11
* @return E
**/
E deQueue();
/**
* 队首展示元素
* @author weidoudou
* @date 2022/10/23 11:11
* @return E
**/
E getFront();
/**
* 获取size
* @author weidoudou
* @date 2022/10/23 11:12
* @return int
**/
int getSize();
/**
* 是否为空
* @author weidoudou
* @date 2022/10/23 11:12
* @return boolean
**/
boolean isEmpty();
}
- 实现类：
package com.company;
public class LoopQueue<E> implements Queue<E>{
private int front;//队首位置
private int tail;//队尾位置
private int size;//大小
private E[] data;
/**
* 无参构造方法
* @author weidoudou
* @date 2022/10/23 17:36
* @return null
**/
public LoopQueue(){
this(10);
}
public LoopQueue(int capacity){
data = (E[]) new Object[capacity+1];
}
public int getCapacity(){
return data.length-1;
}
/**
* 循环队列入队 队尾插入元素
* @author weidoudou
* @date 2022/10/23 17:49
* @param e 请添加参数描述
* @return void
**/
@Override
public void enQueue(E e) {
//1 判断队列是否是满的，满的话进行扩容
if((tail+1)% data.length==front){
//扩容操作
enSize(getCapacity()*2);
}
//2 队尾插入元素
data[tail] = e;
tail = (tail+1)% data.length;
size++;
}
/**
* 扩容操作
* @author weidoudou
* @date 2022/10/23 17:55
* @param newCapacity 请添加参数描述
* @return void
**/
private void enSize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity+1];
for(int i = 0;i<size;i++){
newData[i] = data[(i+front)% data.length];
}
front = 0;
tail = size;
data = newData;
}
/**
* 循环队列出队 队首删除元素
* @author weidoudou
* @date 2022/10/26 7:50
* @param
* @return E
**/
@Override
public E deQueue() {
//1 判断循环队列是否为空
if(isEmpty()){
throw new IllegalArgumentException("空队列不允许出队");
}
//2 出队
E ret = data[front];
data[front] = null;
front = (front+1)% data.length;
size--;
//3 动态缩容
if(size== getCapacity()/4 && getCapacity()/2!=0){
enSize(getCapacity()/2);
}
return ret;
}
/**
* 查看队首元素
* @author weidoudou
* @date 2022/10/26 8:05
* @param
* @return E
**/
@Override
public E getFront() {
if(isEmpty()){
throw new IllegalArgumentException("空队列不允许查看队首元素");
}
E ert = data[front];
return ert;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return front==size;
}
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append(String.format("LoopQueue:size=%d,capacity=%d\n",size,getCapacity()));
stringBuffer.append("front"); //队列顶在此
stringBuffer.append("[");
for(int i=front;i!=tail;i=(i+1)% data.length){
stringBuffer.append(data[i]);
if((i+1)% data.length!=tail){
stringBuffer.append(",");
}
}
stringBuffer.append("]");
return stringBuffer.toString();
}
}
- 测试类：
public static void main(String[] args) {
Queue<Integer> queue = new LoopQueue<>();
for(int i = 0;i<10 ;i++){
queue.enQueue(i);
System.out.println(queue);
if(i%3==0){
queue.deQueue();
System.out.println(queue);
}
}
}
- 测试结果：
LoopQueue:size=1,capacity=10 front[0] LoopQueue:size=0,capacity=10 front[] LoopQueue:size=1,capacity=10 front[1] LoopQueue:size=2,capacity=10 front[1,2] LoopQueue:size=3,capacity=10 front[1,2,3] LoopQueue:size=2,capacity=5 front[2,3] LoopQueue:size=3,capacity=5 front[2,3,4] LoopQueue:size=4,capacity=5 front[2,3,4,5] LoopQueue:size=5,capacity=5 front[2,3,4,5,6] LoopQueue:size=4,capacity=5 front[3,4,5,6] LoopQueue:size=5,capacity=5 front[3,4,5,6,7] LoopQueue:size=6,capacity=10 front[3,4,5,6,7,8] LoopQueue:size=7,capacity=10 front[3,4,5,6,7,8,9] LoopQueue:size=6,capacity=10 front[4,5,6,7,8,9] Process finished with exit code 0
标签：10,capacity,队列,LoopQueue,玩转,front,return,数据结构,size From： https://www.cnblogs.com/1446358788-qq/p/16830741.html