Java中使用数组实现栈数据结构实例
栈是Java语言中最重要的数据结构之一,它的实现,至少应该包括以下几个方法:
1.pop()出栈操作,弹出栈顶元素。
2.push(Ee)入栈操作
3.peek()查看栈顶元素
4.isEmpty()栈是否为空
另外,实现一个栈,还应该考虑到几个问题:
1.栈的初始大小以及栈满以后如何新增栈空间
2.对栈进行更新时需要进行同步
简单示例,使用数组实现栈,代码如下:
publicclassStack<E>{
//Java不支持泛型数组,如需使用,请使用Java提供的容器 privateObject[]stack;
//栈的默认初始大小 privatestaticfinalintINIT_SIZE=2;
//栈顶索引 privateintindex;
publicStack(){ stack=newObject[INIT_SIZE]; index=-1; }
/** *构造方法 * *@paraminitSize * 栈的初始大小 */ publicStack(intinitSize){ if(initSize<0){ thrownewIllegalArgumentException(); } stack=newObject[initSize]; index=-1; }
/** *出栈操作 * *@return栈顶对象 */ publicsynchronizedEpop(){ if(!isEmpty()){ Etemp=peek(); stack[index--]=null; returntemp; } returnnull; }
/** *入栈操作 * *@paramobj * 等待入栈的对象 */ publicsynchronizedvoidpush(Eobj){ if(isFull()){ Object[]temp=stack; //如果栈满,则创建空间为当前栈空间两倍的栈 stack=newObject[2*stack.length]; System.arraycopy(temp,0,stack,0,temp.length); } stack[++index]=obj; }
/** *查看栈顶对象 * *@return栈顶对象 */ publicEpeek(){ if(!isEmpty()){ return(E)stack[index]; } returnnull; }
/** *查看栈是否为空 * *@return如果栈为空返回true,否则返回false */ publicbooleanisEmpty(){ returnindex==-1; }
/** *查看栈是否满 * *@return如果栈满返回true,否则返回false */ publicbooleanisFull(){ returnindex>=stack.length-1; } }