数据结构学习笔记-队列（JAVA）
概念：队列是一种运算受限的线性表，它先进先出
队列的操作有：
构造队列、销毁队列、清空队列、计算队列长度、取队头元素、元素入队和元素出对
代码：
packagecom.alg.queue;
importjava.util.ConcurrentModificationException;
importjava.util.Iterator;
importjava.util.NoSuchElementException;
//用数组实现队列
//队列是一种运算受限的线性表，它先进先出
//队列的操作有：构造队列、销毁队列、清空队列、计算队列长度、取队头元素、元素入队和元素出对
//Iterable为对for循环的支持
publicclassQueue<T>implementsIterable<T>
{
protectedObject[]elementData=null;
//默认数组大小
privatestaticfinalintDEFAULT_SIZE=10;
//数组的每次增长幅度
protectedintcapacityIncrement;
//操作数
privateintmodCount;
//统计数组内保存的元素数量
privateintelementCount;
publicQueue()
{
this(DEFAULT_SIZE,0);
}
publicQueue(intcapacity)
{
this(capacity,0);
}
publicQueue(intcapacity,intcapacityIncrment)
{
elementData=newElementArray(capacity);
elementCount=0;
this.capacityIncrement=capacityIncrment;
}
//清空队
publicvoidclear()
{
for(inti=0;i<elementCount;i++)
{
elementData[i]=null;
}
modCount++;
elementCount=0;
}
//取队头元素
@SuppressWarnings("unchecked")
publicTpeek()
{
Tt=null;
if(elementCount>0)
{
t=(T)elementData[0];
}
returnt;
}
//出队
@SuppressWarnings("unchecked")
publicTdequeue()
{
Tt=null;
if(elementCount>0)
{
t=(T)elementData[0];
System.arraycopy(elementData,1,elementData,0,--elementCount);
modCount++;
}
returnt;
}
//入队
publicvoidenqueue(Tobject)
{
//栈满，增加栈容量
if(elementCount==elementData.length)
{
growByOne();
}
elementData[elementCount++]=object;
modCount++;
}
@SuppressWarnings({"unused","unchecked"})
privateT[]newElementArray(intsize)
{
return(T[])newObject[size];
}//如果从节省空间角度考虑capacityIncrement最好设置
privatevoidgrowByOne()
{
intadding=0;
//没有设置增量的情况
if(capacityIncrement<=0)
{//如果elementData长度为0，就加1，否则就增加elementData.length的一倍
if((adding=elementData.length)==0)
{
adding=1;
}
}
else
{
adding=capacityIncrement;
}
T[]newData=newElementArray(elementData.length+adding);
System.arraycopy(elementData,0,newData,0,elementCount);
elementData=newData;
}
@SuppressWarnings("unchecked")
publicsynchronizedTremove(intlocation)
{
if(location<elementCount)
{
Tresult=(T)elementData[location];
elementCount--;
intsize=elementCount-location;
//把location+1到最后整个拷贝到从location开始到最后
if(size>0)
{
System.arraycopy(elementData,location+1,elementData,location,size);
}
//因为中间的某个删除的位置被覆盖，所以需要把最后一位直空
elementData[elementCount]=null;
modCount++;
returnresult;
}
thrownewArrayIndexOutOfBoundsException(location);
}
//增加了对for循环的支持
publicIterator<T>iterator()
{
returnnewSimpleIterator();
}
@SuppressWarnings("unchecked")
publicsynchronizedTelementAt(intlocation)
{
if(location<elementCount)
{
return(T)elementData[location];
}
thrownewArrayIndexOutOfBoundsException(location);
}
publicintsize()
{
returnelementCount;
}
//简单了实现迭代器
privateclassSimpleIteratorimplementsIterator<T>
{
intpos=-1;
intexpectedModCount;
intlastPosition=-1;
SimpleIterator()
{
super();
expectedModCount=modCount;
}
publicbooleanhasNext()
{
returnpos+1<size();
}
publicTnext()
{
if(expectedModCount==modCount)
{
try
{
Tresult=elementAt(pos+1);
lastPosition=++pos;
returnresult;
}
catch(IndexOutOfBoundsExceptione)
{
thrownewNoSuchElementException();
}
}
thrownewConcurrentModificationException();
}
publicvoidremove()
{
if(this.lastPosition==-1)
{
thrownewIllegalStateException();
}
if(expectedModCount!=modCount)
{
thrownewConcurrentModificationException();
}
try
{
Queue.this.remove(lastPosition);
}
catch(IndexOutOfBoundsExceptione)
{
thrownewConcurrentModificationException();
}
expectedModCount=modCount;
if(pos==lastPosition)
{
pos--;
}
lastPosition=-1;
}
}
}
packagecom.alg.queue;
publicclassQueueMain
{
publicstaticvoidmain(String[]args)
{
Queue<String>queue=newQueue<String>();
queue.enqueue("a");
queue.enqueue("b");
queue.enqueue("c");
queue.enqueue("d");
queue.enqueue("e");
System.out.print("入队:");
for(Stringq:queue)
{
System.out.print(q+"");
}
System.out.println("出队元素："+queue.dequeue());
System.out.print("出队后:");
for(Stringq:queue)
{
System.out.print(q+"");
}
System.out.println("取队头元素:"+queue.peek());
queue.clear();
System.out.println("清空队:"+queue.size());
}
}
运行结果：
入队:abcde出队元素：a
出队后:bcde取队头元素:b
清空队:0