Java 实现栈的三种方式

2023-07-08 18:34:09 82

栈：LIFO（后进先出），自己实现一个栈，要求这个栈具有push()、pop()（返回栈顶元素并出栈）、peek()（返回栈顶元素不出栈）、isEmpty()这些基本的方法。

一、采用数组实现栈

提示：每次入栈之前先判断栈的容量是否够用，如果不够用就用Arrays.copyOf()进行扩容

importjava.util.Arrays;
/**
*数组实现栈
*@param
*/
classMystack1{
//实现栈的数组
privateObject[]stack;
//数组大小
privateintsize;

Mystack1(){
stack=newObject[10];//初始容量为10
}

//判断是否为空
publicbooleanisEmpty(){
returnsize==0;
}

//返回栈顶元素
publicTpeek(){
Tt=null;
if(size>0)
t=(T)stack[size-1];
returnt;
}

publicvoidpush(Tt){
expandCapacity(size+1);
stack[size]=t;
size++;
}

//出栈
publicTpop(){
Tt=peek();
if(size>0){
stack[size-1]=null;
size--;
}
returnt;
}

//扩大容量
publicvoidexpandCapacity(intsize){
intlen=stack.length;
if(size>len){
size=size*3/2+1;//每次扩大50%
stack=Arrays.copyOf(stack,size);
}
}
}

publicclassArrayStack{
publicstaticvoidmain(String[]args){
Mystack1stack=newMystack1<>();
System.out.println(stack.peek());
System.out.println(stack.isEmpty());
stack.push("java");
stack.push("is");
stack.push("beautiful");
stack.push("language");
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
System.out.println(stack.peek());
}
}

二、采用链表实现栈

/**
*链表实现栈
*
*@param
*/
classMystack2{
//定义链表
classNode{
privateTt;
privateNodenext;
}

privateNodehead;

//构造函数初始化头指针
Mystack2(){
head=null;
}

//入栈
publicvoidpush(Tt){
if(t==null){
thrownewNullPointerException("参数不能为空");
}
if(head==null){
head=newNode();
head.t=t;
head.next=null;
}else{
Nodetemp=head;
head=newNode<>();
head.t=t;
head.next=temp;
}
}

//出栈
publicTpop(){
Tt=head.t;
head=head.next;
returnt;
}

//栈顶元素
publicTpeek(){
Tt=head.t;
returnt;
}

//栈空
publicbooleanisEmpty(){
if(head==null)
returntrue;
else
returnfalse;
}
}

publicclassLinkStack{
publicstaticvoidmain(String[]args){
Mystack2stack=newMystack2();
System.out.println(stack.isEmpty());
stack.push("Java");
stack.push("is");
stack.push("beautiful");
System.out.println(stack.peek());
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
}
}

三、采用LinkedList实现栈

push-----addFirst()
pop-------removeFirst()
peek-----getFirst()
isEmpty-isEmpty()

importjava.util.LinkedList;

/**
*LinkedList实现栈
*
*@param
*/
classListStack{
privateLinkedListll=newLinkedList<>();

//入栈
publicvoidpush(Tt){
ll.addFirst(t);
}

//出栈
publicTpop(){
returnll.removeFirst();
}

//栈顶元素
publicTpeek(){
Tt=null;
//直接取元素会报异常，需要先判断是否为空
if(!ll.isEmpty())
t=ll.getFirst();
returnt;
}

//栈空
publicbooleanisEmpty(){
returnll.isEmpty();
}
}

publicclassLinkedListStack{
publicstaticvoidmain(String[]args){
ListStackstack=newListStack();
System.out.println(stack.isEmpty());
System.out.println(stack.peek());
stack.push("java");
stack.push("is");
stack.push("beautiful");
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
System.out.println(stack.peek());
}
}

接着分享java使用两种方式实现简单栈

两种栈的不同点

基于数组实现的栈需要指定初始容量，栈的大小是有限的（可以利用动态扩容改变其大小），基于链表实现的栈则是没有大小限制的。

基于数组实现栈

数组实现栈的主要方法就是标识栈顶在数组中的位置，初始化时可以将栈顶指向为-1的虚拟位置，元素入栈则栈顶元素加1，出栈则栈顶元素减一，栈的元素容量为栈顶指针当前位置加1，且不能超过底层数组的最大容量。

/**
*以数组为底层实现栈
*@param
*/
publicclassMyStackOfArray{
privateObject[]data;//底层数组
privateintmaxSize=0;//栈存储的最大元素个数
privateinttop=-1;//初始时栈顶指针指向-1

//默认初始化容量为10的栈
publicMyStackOfArray(){
this(10);
}

//初始化指定大小的栈
publicMyStackOfArray(intinitialSize){
if(initialSize>=0){
this.maxSize=initialSize;
data=newObject[initialSize];
top=-1;
}else{
thrownewRuntimeException("初始化容量不能小于0"+initialSize);
}
}

//入栈，栈顶指针先加一再填入数据
publicbooleanpush(Telement){
if(top==maxSize-1){
thrownewRuntimeException("当前栈已满，无法继续添加元素");
}else{
data[++top]=element;
returntrue;
}
}

//查看栈顶元素
publicTpeek(){
if(top==-1)
thrownewRuntimeException("栈已空");
return(T)data[top];
}

//出栈，先弹出元素再将栈顶指针减一
publicTpop(){
if(top==-1)
thrownewRuntimeException("栈已空");
return(T)data[top--];
}

//判断当前栈是否为空，只需判断栈顶指针是否等于-1即可
publicbooleanisEmpty(){
returntop==-1;
}

publicintsearch(Telement){
inti=top;
while(top!=-1){
if(peek()!=element)
top--;
else
break;
}
intresult=top+1;
top=i;
returntop;
}

publicstaticvoidmain(String[]args){
MyStackOfArraymyStackOfArray=newMyStackOfArray<>(10);
for(inti=0;i<10;i++){
myStackOfArray.push(i);
}
System.out.println("测试是否执行");
for(inti=0;i<10;i++){
System.out.println(myStackOfArray.pop());
}
}
}

基于链表实现栈

基于链表实现栈只要注意控制栈顶指针的指向即可。

/**
*链表方式实现栈
*@param
*/
publicclassMyStack{
/**
*内部节点类
*@param
*/
privateclassNode{
Ee;
Nodenext;

publicNode(){}

publicNode(Ee,Nodenext){
this.e=e;
this.next=next;
}
}

privateNodetop;//栈顶指针
privateintsize;//栈容量

publicMyStack(){
top=null;
}

//入栈，将新节点的next指针指向当前top指针，随后将top指针指向新节点
publicbooleanpush(Ee){
top=newNode(e,top);
size++;
returntrue;
}

//判断栈是否为空
publicbooleanisEmpty(){
returnsize==0;
}

//返回栈顶节点
publicNodepeek(){
if(isEmpty())
thrownewRuntimeException("栈为空");
returntop;
}

//出栈，先利用临时节点保存要弹出的节点值，再将top指针指向它的下一个节点，并将弹出的节点的next指针赋空即可
publicNodepop(){
if(isEmpty())
thrownewRuntimeException("栈为空");
Nodevalue=top;
top=top.next;
value.next=null;
size--;
returnvalue;
}

//返回当前栈的大小
publicintlength(){
returnsize;
}

publicstaticvoidmain(String[]args){
MyStackmyStack=newMyStack<>();
for(inti=0;i<10;i++){
myStack.push(i);
}
for(inti=0;i<10;i++){
System.out.println(myStack.pop().e);
}
}
}

到此这篇关于Java实现栈的三种方式的文章就介绍到这了,更多相关Java实现栈内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

Java 实现栈的三种方式

接着分享java使用两种方式实现简单栈

热门推荐

随机推荐