数据结构学习笔记-栈（JAVA）
栈是限制在表的一端，进行插入和删除操作的线性表，栈是后进先出
栈的操作：
构造栈
销毁栈
清空栈
计算栈长度
取栈顶元素
元素压栈
元素弹栈
代码：
packagecom.alg.stack;
importjava.util.ConcurrentModificationException;
importjava.util.Iterator;
importjava.util.NoSuchElementException;
//栈是限制在表的一端，进行插入和删除操作的线性表，栈是后进先出
//栈的操作：构造栈销毁栈清空栈计算栈长度取栈顶元素元素压栈元素弹栈
//Iterable实现这个可以使用for(Tt:stack)循环
publicclassStack<T>implementsIterable<T>
{
//统计数组内保存的元素数量
privateintelementCount;
//保存数据的数组
protectedObject[]elementData=null;
//数组的每次增长幅度
protectedintcapacityIncrement;
//默认数组大小
privatestaticfinalintDEFAULT_SIZE=10;
//操作数
privateintmodCount;
publicStack()
{
this(DEFAULT_SIZE,0);
}
publicStack(intcapacity)
{
this(capacity,0);
}
publicStack(intcapacity,intcapacityIncrment)
{
elementData=newElementArray(capacity);
elementCount=0;
this.capacityIncrement=capacityIncrment;
}
//取栈顶元素
@SuppressWarnings("unchecked")
publicTpeek()
{
return(T)elementData[elementCount-1];
}
//出栈
@SuppressWarnings("unchecked")
publicTpop()
{
finalintindex=--elementCount;
Tt=(T)elementData[index];
elementData[index]=null;
modCount++;
returnt;
}
//入栈
publicvoidpush(Tobject)
{
//栈满，增加栈容量
if(elementCount==elementData.length)
{
growByOne();
}
elementData[elementCount++]=object;
modCount++;
}
//清空栈
publicvoidclear()
{
for(inti=0;i<elementCount;i++)
{
elementData=null;
}
modCount++;
elementCount=0;
}
@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;
}
publicintsize()
{
returnelementCount;
}
@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);
}
@SuppressWarnings("unchecked")
publicsynchronizedTelementAt(intlocation)
{
if(location<elementCount)
{
return(T)elementData[location];
}
thrownewArrayIndexOutOfBoundsException(location);
}
//有这个可以对java新特性for循环的支持
publicIterator<T>iterator()
{
returnnewSimpleIterator();
}
//简单了实现迭代器
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
{
Stack.this.remove(lastPosition);
}
catch(IndexOutOfBoundsExceptione)
{
thrownewConcurrentModificationException();
}
expectedModCount=modCount;
if(pos==lastPosition)
{
pos--;
}
lastPosition=-1;
}
}
}