Java栈实现[通俗易懂]

Java栈实现[通俗易懂]数组实现的栈一:优点:插入和删除很快,缺点:长度有限publicclassStack{ privateinttop=-1; privateObject[]objs; publicStack()throwsException{ this(10); } publicStack(intcapacity)throwsExceptio

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

栈数组实现一:优点:入栈和出栈速度快,缺点:长度有限(有时候这也不能算是个缺点)

public class Stack {
	private int top = -1;
	private Object[] objs;
	
	public Stack(int capacity) throws Exception{
		if(capacity < 0)
			throw new Exception("Illegal capacity:"+capacity);
		objs = new Object[capacity];
	}
	
	public void push(Object obj) throws Exception{
		if(top == objs.length - 1)
			throw new Exception("Stack is full!");
		objs[++top] = obj;
	}
	
	public Object pop() throws Exception{
		if(top == -1)
			throw new Exception("Stack is empty!");
		return objs[top--];
	}
	
	public void dispaly(){
		System.out.print("bottom -> top: | ");
		for(int i = 0 ; i <= top ; i++){
			System.out.print(objs[i]+" | ");
		}
		System.out.print("\n");
	}
	
	public static void main(String[] args) throws Exception{
		Stack s = new Stack(2);
		s.push(1);
		s.push(2);
		s.dispaly();
		System.out.println(s.pop());
		s.dispaly();
		s.push(99);
		s.dispaly();
		s.push(99);
	}
}
bottom -> top: | 1 | 2 | 
2
bottom -> top: | 1 | 
bottom -> top: | 1 | 99 | 
Exception in thread "main" java.lang.Exception: Stack is full!
	at Stack.push(Stack.java:17)
	at Stack.main(Stack.java:44)

数据项入栈和出栈的时间复杂度都为常数O(1)

栈数组实现二:优点:无长度限制,缺点:入栈慢

import java.util.Arrays;

public class UnboundedStack {
	private int top = -1;
	private Object[] objs;
	
	public UnboundedStack() throws Exception{
		this(10);
	}
	
	public UnboundedStack(int capacity) throws Exception{
		if(capacity < 0)
			throw new Exception("Illegal capacity:"+capacity);
		objs = new Object[capacity];
	}
	
	public void push(Object obj){
		if(top == objs.length - 1){
			this.enlarge();
		}
		objs[++top] = obj;
	}
	
	public Object pop() throws Exception{
		if(top == -1)
			throw new Exception("Stack is empty!");
		return objs[top--];
	}
	
	private void enlarge(){
		int num = objs.length/3;
		if(num == 0)
			num = 1;
		objs = Arrays.copyOf(objs, objs.length + num);
	}
	
	public void dispaly(){
		System.out.print("bottom -> top: | ");
		for(int i = 0 ; i <= top ; i++){
			System.out.print(objs[i]+" | ");
		}
		System.out.print("\n");
	}
	
	public static void main(String[] args) throws Exception{
		UnboundedStack us = new UnboundedStack(2);
		us.push(1);
		us.push(2);
		us.dispaly();
		System.out.println(us.pop());
		us.dispaly();
		us.push(99);
		us.dispaly();
		us.push(99);
		us.dispaly();
	}
}
bottom -> top: | 1 | 2 | 
2
bottom -> top: | 1 | 
bottom -> top: | 1 | 99 | 
bottom -> top: | 1 | 99 | 99 | 

由于该栈是由数组实现的,数组的长度是固定的,当栈空间不足时,必须将原数组数据复制到一个更长的数组中,考虑到入栈时或许需要进行数组复制,平均需要复制N/2个数据项,故入栈的时间复杂度为O(N),出栈的时间复杂度依然为O(1)

栈单链表实现:没有长度限制,并且出栈和入栈速度都很快

public class LinkedList {
	private class Data{
		private Object obj;
		private Data next = null;
		
		Data(Object obj){
			this.obj = obj;
		}
	}
	
	private Data first = null;
	
	public void insertFirst(Object obj){
		Data data = new Data(obj);
		data.next = first;
		first = data;
	}
	
	public Object deleteFirst() throws Exception{
		if(first == null)
			throw new Exception("empty!");
		Data temp = first;
		first = first.next;
		return temp.obj;
	}
			
	public void display(){
		if(first == null)
			System.out.println("empty");
		System.out.print("top -> bottom : | ");
		Data cur = first;
		while(cur != null){
			System.out.print(cur.obj.toString() + " | ");
			cur = cur.next;
		}
		System.out.print("\n");
	}
}
public class LinkedListStack {
	private LinkedList ll = new LinkedList();
	
	public void push(Object obj){
		ll.insertFirst(obj);
	}
	
	public Object pop() throws Exception{
		return ll.deleteFirst();
	}
	
	public void display(){
		ll.display();
	}
	
	public static void main(String[] args) throws Exception{
		LinkedListStack lls = new LinkedListStack();
		lls.push(1);
		lls.push(2);
		lls.push(3);
		lls.display();
		System.out.println(lls.pop());
		lls.display();
	}
}
top -> bottom : | 3 | 2 | 1 | 
3
top -> bottom : | 2 | 1 | 

数据项入栈和出栈的时间复杂度都为常数O(1)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/196768.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ssd1315驱动oled屏_oled屏幕的手机有哪些

    ssd1315驱动oled屏_oled屏幕的手机有哪些淘宝隔壁老王家的OLED运动手环,非常的便宜2RMB一个。###Part0:可用器件列表0x00:OLDE屏幕:0.91inch,分辨率:12832,主控:SSD1306,接口:SPI,颜色:

  • 网络编程API-下 (I/O复用函数)[通俗易懂]

    网络编程API-下 (I/O复用函数)

  • XXE初探

    XXE初探最近经常看到XXE出没,以为是最近才出现的一种类型,后来发现14年,乌云上面就有好多的案例,实在是我太lo了~@Time:2018/11/15在jarvisoj上面有着一道xxe的练习题,感兴趣的大佬可以去玩玩https://www.jarvisoj.com/challenges在写题之前,我们先科普一下,什么是xxe?xxe是xml外部实体注入,这里有一段xml的解释XM…

  • iOS抓包工具Charles的使用

    iOS抓包工具Charles的使用首先,设置手机的网络连接电脑共享wifi,同时设置端口号; 其次,涉及到https抓包时,需要设置手机安装和信任ssl证书,以及设置Charles中ssl的配置。一、下载与安装Charles:charles-proxy-3.10.2.dmgjavaSDK:javaforosx.dmg二、网络环境与手机的配置1、开启电脑共享wifi,同时设置主机代理与端口号(1)系统偏好设置——>共享——>互联网共享;(2)系统偏好设置——>网络——>以太网——>高级——&

  • 优化SqlServer–数据压缩

    优化SqlServer–数据压缩

    2021年11月25日
  • html session修改,session.setattribute

    html session修改,session.setattribute关于JSP的session.setAttribute()方法是做什么用session对象的方法setAttribute()有什么具体作用啊,请详细点,不设置行吗?session.setAttribute(“username”,username);session.setAttribute(“username”,username);将后者的username内容放到前者username中并保存起来…

    2022年10月17日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号