Java语言实现数据结构栈代码详解

2023-09-20 08:02:05 51

近来复习数据结构，自己动手实现了栈。栈是一种限制插入和删除只能在一个位置上的表。最基本的操作是进栈和出栈，因此，又被叫作“先进后出”表。

首先了解下栈的概念：

栈是限定仅在表头进行插入和删除操作的线性表。有时又叫LIFO（后进先出表）。要搞清楚这个概念，首先要明白”栈“原来的意思，如此才能把握本质。

"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。

实现方式是这样的：首先定义了一个接口，然后通过这个接口实现了线性栈和链式栈，代码比较简单，如下：

packagecom.peter.java.dsa.interfaces;
/**
*栈操作定义
*
*@authorPeterPan
*/
publicinterfaceStack{
	/*判空*/
	BooleanisEmpty();
	/*清空栈*/
	voidclear();
	/*弹栈*/
	Tpop();
	/*入栈*/
	Booleanpush(Tdata);
	/*栈的长度*/
	intlength();
	/*查看栈顶的元素，但不移除它*/
	Tpeek();
	/*返回对象在栈中的位置*/
	intsearch(Tdata);
}

线性栈：以数组的方式实现。

packagecom.peter.java.dsa.common;
importcom.peter.java.dsa.interfaces.Stack;
/**
*线性栈
*
*@authorPeterPan
*/
publicclassLinearStackimplementsStack{
	@SuppressWarnings("unchecked")
	privateT[]t=(T[])newObject[16];
	privateintsize=0;
	@Override
	publicBooleanisEmpty(){
		//TODOAuto-generatedmethodstub
		returnsize==0;
	}
	@Override
	publicvoidclear(){
		//TODOAuto-generatedmethodstub
		for(inti=0;i=t.length){
			resize();
		}
		t[size++]=data;
		returntrue;
	}
	@Override
	publicintlength(){
		//TODOAuto-generatedmethodstub
		returnsize;
	}
	@Override
	publicTpeek(){
		//TODOAuto-generatedmethodstub
		if(size==0){
			returnnull;
		}else{
			returnt[size-1];
		}
	}
	/*returnindexofdata,return-1ifnodata*/
	@Override
	publicintsearch(Tdata){
		//TODOAuto-generatedmethodstub
		intindex=-1;
		for(inti=0;i-1;i--){
			buffer.append(t[i].toString()+",");
		}
		buffer.append("]");
		buffer.replace(buffer.lastIndexOf(","),buffer.lastIndexOf(",")+1,"");
		returnbuffer.toString();
	}
}

链式栈：通过单链表进行实现。

packagecom.peter.java.dsa.common;
importcom.peter.java.dsa.interfaces.Stack;
publicclassLinkedStackimplementsStack{
	privateNodetop;
	privateintsize;
	@Override
	publicBooleanisEmpty(){
		//TODOAuto-generatedmethodstub
		returnsize==0;
	}
	@Override
	publicvoidclear(){
		//TODOAuto-generatedmethodstub
		top=null;
		size=0;
	}
	@Override
	publicTpop(){
		//TODOAuto-generatedmethodstub
		TtopValue=null;
		if(top!=null){
			topValue=top.data;
			NodeoldTop=top;
			top=top.prev;
			oldTop.prev=null;
			size--;
		}
		returntopValue;
	}
	@Override
	publicBooleanpush(Tdata){
		//TODOAuto-generatedmethodstub
		NodeoldTop=top;
		top=newNode(data);
		top.prev=oldTop;
		size++;
		returntrue;
	}
	@Override
	publicintlength(){
		//TODOAuto-generatedmethodstub
		returnsize;
	}
	@Override
	publicTpeek(){
		//TODOAuto-generatedmethodstub
		TtopValue=null;
		if(top!=null){
			topValue=top.data;
		}
		returntopValue;
	}
	@Override
	publicintsearch(Tdata){
		//TODOAuto-generatedmethodstub
		intindex=-1;
		Nodetmp=top;
		for(inti=size-1;i>-1;i--){
			if(tmp.data.equals(data)){
				index=i;
				break;
			}else{
				tmp=tmp.prev;
			}
		}
		tmp=null;
		returnindex;
	}
	@Override
	publicStringtoString(){
		//TODOAuto-generatedmethodstub
		StringBufferbuffer=newStringBuffer();
		buffer.append("LinkedStackContent:[");
		Nodetmp=top;
		for(inti=0;i
学习还在进行中，以后会继续更新代码。
就是本文关于Java语言实现数据结构栈代码详解的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

Java语言实现数据结构栈代码详解

热门推荐

随机推荐