...
1，队列是一致先进先出结构（first in first out）FIFO
2，基于数据的方法实现队列，数组的具体类
package com.dream21th.algorithmicdatastructure.quene;
/**
* @Auther: hp
* @Date: 2019/9/7 15:42
* @Description:
*/
public class MyExtendArray<E> {
private E[] datas;
private int size;
/**
* 创建有参构造函数，初始化数组容量
* @param capacity
*/
public MyExtendArray(int capacity){
datas=(E[])new Object[capacity];
size=0;
}
/**
* 构造无参函数，初始化数组容量
*/
public MyExtendArray(){
this(10);
}
public int getSize(){
return this.size;
}
public boolean isEmpty(){
return this.size==0;
}
/**
* 在指定索引位置加值
* @param index
* @param e
*/
public void add(int index,E e){
if(index<0 || index>this.size){
throw new IllegalArgumentException("index must between 0 and size");
}
if(this.size==datas.length){
resize(2*datas.length);
}
for(int position=size-1;position>=index;position--){
this.datas[position+1]=this.datas[position];
}
this.datas[index]=e;
this.size++;
}
private void resize(int newCapacity) {
E[] newDatas= (E[]) new Object[newCapacity];
for(int i=0;i<this.size;i++){
newDatas[i]=this.datas[i];
}
this.datas=newDatas;
}
/**
* 在第一个位置加入元素
* @param e
*/
public void addFirst(E e){
this.add(0,e);
}
/**
* 在最后一个位置添加元素
* @param e
*/
public void addLast(E e){
this.add(size,e);
}
public E get(int index){
if(index<0 || index>=this.size){
throw new IllegalArgumentException("index must between 0 and size");
}
return this.datas[index];
}
public void set(int index,E e){
if(index<0 || index>=this.size){
throw new IllegalArgumentException("index must between 0 and size");
}
this.datas[index]=e;
}
public boolean contain(E e){
for(int i=0;i<size;i++){
if(this.datas[i].equals(e)){
return true;
}
}
return false;
}
public int find(int e){
for(int i=0;i<size;i++){
if(this.datas[i].equals(e)){
return i;
}
}
return -1;
}
public E remove(int index){
if(index<0 || index>=this.size){
throw new IllegalArgumentException("index must between 0 and size");
}
E ret=this.datas[index];
for(int i=index+1;i<size;i++){
this.datas[i-1]=this.datas[i];
}
size--;
this.datas[size]=null;
if(this.size==this.datas.length/4 && this.datas.length/2!=0){
resize(this.datas.length/2);
}
return ret;
}
public E removeFirst(){
return remove(0);
}
public E removeLast(){
return remove(size-1);
}
public E getLast(){
return get(this.size-1);
}
public E getFirst(){
return get(0);
}
public int getCapacity(){
return this.datas.length;
}
@Override
public String toString() {
StringBuilder builder=new StringBuilder();
builder.append(String.format("Array: size = %d,capacity = %d \n",this.size,this.datas.length));
builder.append("[");
for(int i=0;i<size;i++){
builder.append(this.datas[i]);
if(i!=size-1){
builder.append(",");
}
}
builder.append("]");
return builder.toString();
}
}
|
3，数组实现队列
package com.dream21th.algorithmicdatastructure.quene;
/**
* @Auther: hp
* @Date: 2019/9/8 15:40
* @Description:
*/
public interface Queue<E> {
int getSize();
void enquene(E e);
E dequene();
E getfornt();
boolean isEmpty();
}
|
package com.dream21th.algorithmicdatastructure.quene;
/**
* @Auther: hp
* @Date: 2019/9/8 15:42
* @Description:
*/
public class ArrayQuene<E> implements Queue<E> {
private MyExtendArray<E> myExtendArray;
public ArrayQuene(int capacity){
myExtendArray=new MyExtendArray();
}
public ArrayQuene(){
this(10);
}
@Override
public int getSize() {
return myExtendArray.getSize();
}
@Override
public void enquene(E e) {
myExtendArray.addLast(e);
}
@Override
public E dequene() {
return myExtendArray.removeFirst();
}
@Override
public E getfornt() {
return myExtendArray.getFirst();
}
@Override
public boolean isEmpty() {
return myExtendArray.isEmpty();
}
public int getCapacity(){
return myExtendArray.getCapacity();
}
@Override
public String toString() {
StringBuilder builder=new StringBuilder();
builder.append(String.format("Stack: size = %d, capacity = %d \n",getSize(),getCapacity()));
builder.append("fornt [");
for(int i=0;i<getSize();i++){
builder.append(myExtendArray.get(i));
if(i!=getSize()-1){
builder.append(",");
}
}
builder.append("] tail");
return builder.toString();
}
}
|
4，复杂度分析
进入队列从末尾进入，复杂度为O(1)
出队列从头部出，后面数据都要向前移动一位，复杂度为O(n)
5,基于环形数组实现队列
package com.dream21th.algorithmicdatastructure.quene;
/**
* @Auther: hp
* @Date: 2019/9/8 16:20
* @Description:
*/
public class LoopQueue<E> implements Queue<E> {
private E[] datas;
private int front;
private int tail;
private int size;
public LoopQueue(int capacity){
datas= (E[]) new Object[capacity+1];
front=0;
tail=0;
size=0;
}
public LoopQueue(){
this(10);
}
@Override
public int getSize() {
return this.size;
}
public int getCapacity(){
return this.datas.length-1;
}
@Override
public void enquene(E e) {
if((tail+1)%this.datas.length==front){
resize(getCapacity()*2);
}
this.datas[tail]=e;
tail++;
size++;
}
private void resize(int capacity){
E[] newDatas= (E[]) new Object[capacity+1];
/* for(int i=0;i<size;i++){
newDatas[i]=datas[(front+i)%datas.length];
}*/
int j=0;
for(int i=front;i!=tail;i=(i+1)%this.datas.length){
newDatas[j++]=this.datas[i];
}
datas=newDatas;
front=0;
tail=size;
}
@Override
public E dequene() {
if(isEmpty()){
throw new IllegalArgumentException("queue is empty");
}
E data = this.datas[front];
if(this.size==this.getCapacity()/4 && this.getCapacity()/2!=0){
resize(this.getCapacity()/2);
}
this.datas[front]=null;
front++;
size--;
return data;
}
@Override
public E getfornt() {
return this.datas[front];
}
@Override
public boolean isEmpty() {
return front==tail;
}
@Override
public String toString() {
StringBuilder builder=new StringBuilder();
builder.append(String.format("Stack: size = %d, capacity = %d \n",getSize(),getCapacity()));
builder.append("Queue front [");
for(int i=front;i!=tail;i=(i+1)%this.datas.length){
builder.append(this.datas[i]);
if((i+1)%this.datas.length!=tail){
builder.append(",");
}
}
builder.append("] tail");
return builder.toString();
}
}
|
6，复杂度分析
出队列和入队列复杂度都为O（1）
7，两种方式对比
package com.dream21th.algorithmicdatastructure.quene;
/**
* @Auther: hp
* @Date: 2019/9/8 15:48
* @Description:
*/
public class Test {
public static void main(String[] args) {
/*ArrayQuene<Integer> arrayQuene=new ArrayQuene<>();
for(int i=0;i<10;i++){
arrayQuene.enquene(i);
System.out.println(arrayQuene);
if(i%3==2){
arrayQuene.dequene();
System.out.println(arrayQuene);
}
}*/
/* LoopQueue<Integer> arrayQuene=new LoopQueue<>();
for(int i=0;i<20;i++){
arrayQuene.enquene(i);
System.out.println(arrayQuene);
}
for(int i=0;i<16;i++){
arrayQuene.dequene();
System.out.println(arrayQuene);
}*/
ArrayQuene<Integer> arrayQuene=new ArrayQuene<>();
System.out.println(testTime(arrayQuene,100000));
LoopQueue<Integer> loopQuene=new LoopQueue<>();
System.out.println(testTime(loopQuene,100000));
}
public static double testTime(Queue<Integer> queue,int total){
long beginTime=System.nanoTime();
for(int i=0;i<total;i++){
queue.enquene(i);
}
for (int i=0;i<total;i++){
queue.dequene();
}
long endTime=System.nanoTime();
return (endTime-beginTime)/1000000000.0;
}
}
|
结果
13.559065063
0.013770266
相差1000倍