Java栈的三种实现方式(完整版)

java什么是栈

系统中的堆、栈和数据结构堆、栈不是一个概念。可以说系统中的堆、栈是真实的内存物理区,数据结构中的堆、栈是抽象的数据存储结构。

栈:实际上就是满足后进先出的性质,是一种数据项按序排列的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除。

栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。

栈的优势是,存取速度比堆要快,仅次于直接位于CPU中的寄存器。但缺点是,存在栈中的数据大小与生存期必须是确定的,缺乏灵活性。

代码:

Stack的基本使用
初始化
Stack stack=new Stack
判断是否为空
stack.empty()
取栈顶值(不出栈)
stack.peek()
进栈
stack.push(Object);
出栈
stack.pop();
实例:
public class Test01 {
 public static void main(String[] args) {
 Stack stack=new Stack();
 //1.empty()栈是否为空
 System.out.println(stack.empty());
 //2.peek()栈顶值  3.进栈push()
 stack.push(new Integer(1));
 stack.push("b");
 System.out.println(stack.peek());
 //4.pop()出栈
 stack.pop();
 System.out.println(stack.peek());
 }
}

栈的主要操作

  1. void push(int data):将data(数据)插入栈
  2. int pop():删除并返回最后一个插入栈的

栈的辅助操作

  1. int top():返回最后一个插入栈的元素,但不删除
  2. int size():返回存储在栈中的元素的个数
  3. int isEmpty():判断栈中是否有元素
  4. int isStackFull():判断栈中是否满元素

实现

栈抽象数据类型有多种实现方式。下面是常用的方法:

  1. 基于简单数组的实现方法
  2. 基于动态数组的实现方法
  3. 基于链表的实现方法

1)基于简单数组实现:

public class Stack{
  private int size;//栈的大小
  private int top;//栈顶元素的下标
  private char[] stackArray;//栈的容器
  public Stack(int size){
  	stackArray = new char[size];
  	top = -1;     //初始化栈的时候由于栈内没有元素,栈顶下标设为-1
  	this.size = size;
  }
  //入栈,栈顶的下标+1
  public void push(char item){
  	stackArray[++top] = item;
  }
  //出栈,删除栈顶元素,栈顶元素的下标-1
  public int pop(){
  	return stackArray[top--];
  }
  //查看栈顶元素,不删除
  public char find(){
  	return stackArray[top];
  }
  //判空
  public boolean isEmpty(){
  	return (top == -1);
  }
  //判满
  public boolean isFull(){
  	return (top == size - 1);
  }
  public static void main(String[] args){
  	Stack stack = new Stack(5);
  	stack.push('a');
  	stack.push('b');
  	stack.push('c');
  	stack.push('d');
  	char ch = stack.find();
  	System.out.println(ch);
  }
}

运行结果:

d

2)基于动态数组实现:

扩容——给我的感觉就像是在搬家,搬完了东西,还得把钥匙给主人

public class Stack {
	public int size;//栈的大小
  public int top;//栈顶元素的下标
  public static char[] stackArray;//栈的容器
  public Stack(int size){
  	stackArray = new char[size];
  	top = -1;     //初始化栈的时候由于栈内没有元素,栈顶下标设为-1
  	this.size = size;
  }
  //入栈,栈顶的下标+1
  public void push(char item){
  		if(isFull()){
  			doubleStack();
  		}
  		stackArray[++top] = item;
  }
  //模拟数组的扩容
  public void doubleStack(){
  	char[] newStackArray = new char[size*2];
  	for(int i = 0;i<size;i++){
  		newStackArray[i] = stackArray[i];
  	}
  	size = size*2;
  	stackArray = newStackArray;
  }
  //出栈,删除栈顶元素,栈顶元素的下标-1
  public int pop(){
  	if(isEmpty()){
  		System.out.println("Stack is Empty");
  		return 0;
  	}else{
  		return stackArray[top--];
  	}
  }
  //查看栈顶元素,不删除
  public char find(){
  	return stackArray[top];
  }
  //判空
  public boolean isEmpty(){
  	return (top == -1);
  }
  //判满
  public boolean isFull(){
  	return (top == size - 1);
  }
  public static void main(String[] args){
  	Stack stack = new Stack(5);
  	stack.push('a');
  	stack.push('b');
  	stack.push('c');
  	stack.push('d');
  	stack.push('e');
  	stack.push('f');
  	stack.push('g');
  	stack.push('h');//一共8个元素
  	char ch = stack.find();
  	System.out.println(ch);
  	System.out.println(stackArray.length);
  }
}

运行结果:

h
10

3)基于链表实现

使用链表实现栈,通过在链表的表头插入元素的方式实现push操作,删除链表的表头结点实现pop操作。表头结点即栈顶结点

import java.util.EmptyStackException;
class Link{
	public char data;
	public Link next;
	public void show(){
		System.out.println(data + " ");
	}
	public Link(char data){
		this.data = data;
	}
}
public class Stack2 {
	Link head;
  public int size;//栈的大小
  public int top;//栈顶元素的下标
  public static char[] stackArray;//栈的容器
  public void push(char data){
  	if(head == null){
  		head = new Link(data);
  	}else{
  		Link node = new Link(data);
  		node.next = head;
  		head = node;
  	}
  }
  public void pop(){
  	if(head == null){
  		throw new EmptyStackException();
  	}else{
  		char dat = head.data;
  		head.show();
  		head = head.next;
  	}
  }
  public int top(){
  	if(head == null){
  		return 0;
  	}else{
  		return head.data;
  	}
  }
  public boolean isEmpty(){
  	if(head == null) return true;
  	return false;
  }
  public static void main(String[] args){
  	Stack2 stack = new Stack2();
  	stack.push('A');
  	stack.push('B');
  	stack.push('C');
  	stack.push('D');
  	stack.push('E');
  	stack.push('F');
  	stack.pop();
  }
}

运行结果:

F

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

(0)

相关推荐

  • Java 实现栈的三种方式

    栈:LIFO(后进先出),自己实现一个栈,要求这个栈具有push().pop()(返回栈顶元素并出栈).peek() (返回栈顶元素不出栈).isEmpty()这些基本的方法. 一.采用数组实现栈 提示:每次入栈之前先判断栈的容量是否够用,如果不够用就用Arrays.copyOf()进行扩容 import java.util.Arrays; /** * 数组实现栈 * @param <T> */ class Mystack1<T> { //实现栈的数组 private Object

  • Java中堆和栈的区别详解

    当一个人开始学习Java或者其他编程语言的时候,会接触到堆和栈,由于一开始没有明确清晰的说明解释,很多人会产生很多疑问,什么是堆,什么是栈,堆和栈有什么区别?更糟糕的是,Java中存在栈这样一个后进先出(Last In First Out)的顺序的数据结构,这就是java.util.Stack.这种情况下,不免让很多人更加费解前面的问题.事实上,堆和栈都是内存中的一部分,有着不同的作用,而且一个程序需要在这片区域上分配内存.众所周知,所有的Java程序都运行在JVM虚拟机内部,我们这里介绍的自然

  • 详解Java的堆内存与栈内存的存储机制

    堆与内存优化     今天测了一个项目的数据自动整理功能,对数据库中几万条记录及图片进行整理操作,运行接近到最后,爆出了java.lang.outOfMemoryError,java heap space方面的错误,以前写程序很少遇到这种内存上的错误,因为java有垃圾回收器机制,就一直没太关注.今天上网找了点资料,在此基础上做了个整理.  一.堆和栈 堆-用new建立,垃圾回收器负责回收 1.程序开始运行时,JVM从OS获取一些内存,部分是堆内存.堆内存通常在存储地址的底层,向上排列. 2.堆

  • java中stack(栈)的使用代码实例

    java中stack类继承于vector,其特性为后进先出(lastinfirstout). 入栈和出栈实例图: 实例图的java代码实例: package com.lanhuigu.java.ListTest; import java.util.Stack; public class StackTest { public static void main(String[] args) { Stack<String> staffs = new Stack<String>(); //

  • java堆栈类使用实例(java中stack的使用方法)

    JAVA 中,使用 java.util.Stack 类的构造方法创建对象. public class Stack extends vector 构造方法 : public Stack() 创建一个空 Stack. 方法:  1. public push  (item )  把项 压入栈顶.其作用与 addElement (item ) 相同. 参数 item 压入栈顶的项 . 返回: item 参数 : 2. public pop () 移除栈顶对象,并作为函数的值 返回该对象. 返回:栈顶对象

  • Java栈的三种实现方式(完整版)

    java什么是栈 系统中的堆.栈和数据结构堆.栈不是一个概念.可以说系统中的堆.栈是真实的内存物理区,数据结构中的堆.栈是抽象的数据存储结构. 栈:实际上就是满足后进先出的性质,是一种数据项按序排列的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除. 栈区(stack)- 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等.其操作方式类似于数据结构中的栈. 栈的优势是,存取速度比堆要快,仅次于直接位于CPU中的寄存器.但缺点是,存在栈中的数据大小与生存期必须是确定的,缺乏灵

  • java数组的三种扩容方式以及程序实现详解

    因为数组是在内存中连续的一段存储空间,所以数组一旦被创建,空间就固定了,长度是不能扩增的. 数组的长度是固定的,如果需要扩充**,必须创建新数组,原数组的长度要复制到新数组中 .** java中,数组类型的变量传值的时候,事实上传递的是数组的地址 . Java数组扩容的原理 1)Java数组对象的大小是固定不变的,数组对象是不可扩容的. 2)利用数组复制方法可以变通的实现数组扩容. 3)System.arraycopy()可以复制数组. 4)Arrays.copyOf()可以简便的创建数组副本.

  • Java spring的三种注入方式详解流程

    目录 设置Spring的作用域 自动注入 @Primary Qualifier @ComponentScan不同的配置对性能的影响 懒加载 三种注入方式 字段注入(IDEA 会提示不推荐) 字段注入的bean类外部不可见 循环依赖问题 构造器注入(官方推荐) set方法注入 设置Spring的作用域 或者使用枚举值设置 单例和多里使用场景 自动注入 @Primary 一个接口有多个实现被spring管理吗,在依赖注入式,spring会不知道注入哪个实现类就会抛出NoUniqueBeanDefin

  • Java线程的三种创建方式

    目录 1.Thread 2.Runnable和Thread 3.Runnable和Thread 4.三者对比 5.注意项 1.Thread 继承Thread类,并重写run方法 class ThreadDemo1 extends Thread { @Override public void run() { log.info("{}", Thread.currentThread().getName()); } } 线程启动方式: ThreadDemo1 t1 = new ThreadDe

  • Java定时任务的三种实现方式

    前言 现代的应用程序早已不是以前的那些由简单的增删改查拼凑而成的程序了,高复杂性早已是标配,而任务的定时调度与执行也是对程序的基本要求了. 很多业务需求的实现都离不开定时任务,例如,每月一号,移动将清空你上月未用完流量,重置套餐流量,以及备忘录提醒.闹钟等功能. Java 系统中主要有三种方式来实现定时任务: Timer和TimerTask ScheduledExecutorService 三方框架 Quartz 下面我们一个个来看. Timer和TimerTask 先看一个小 demo,接着我

  • Java倒计时三种实现方式代码实例

    写完js倒计时,突然想用java实现倒计时,写了三种实现方式 一:设置时长的倒计时: 二:设置时间戳的倒计时: 三:使用java.util.Timer类实现的时间戳倒计时 代码如下: package timer; import java.util.Calendar; import java.util.Date; import java.util.Timer; import java.util.TimerTask; /** * java演示倒计时 * */ public class TimeTes

  • Java基础之多线程的三种实现方式

    一.前言 Java多线程实现的三种方式有继承Thread类,实现Runnable接口,使用ExectorService.Callable.Future实现有返回结果的多线程.其中前两种方式线程执行完后都没有返回值,只有最后一种是带返回值的. 二.继承Thread类实现多线程 1.Thread本质上也是实现了Runnable接口的一个实例,它代表一个线程的实例,并且,启动线程的唯一方法就是通过Thread类的start()实例方法. 2.start()方法是一个native方法,它将启动一个新线程

  • Java中关于线程安全的三种解决方式

    三个窗口卖票的例子解决线程安全问题 问题:买票过程中,出现了重票.错票-->出现了线程的安全问题 问题出现的原因:当某个线程操作车票的过程中,尚未操作完成时,其他线程参与进来,也操作车票 如何解决:当一个线程a在操作ticket的时候,其他线程不能参与进来,知道线程a操作完ticket时,其他线程才可以开始操作ticket,这种情况即使线程a出现了阻塞,也不能被改变 在Java中,我们通过同步机制,来解决线程的安全问题.(线程安全问题的前提:有共享数据) 方式一:同步代码块 synchroniz

  • java中进程与线程_三种实现方式总结(必看篇)

    一:进程与线程 概述:几乎任何的操作系统都支持运行多个任务,通常一个任务就是一个程序,而一个程序就是一个进程.当一个进程运行时,内部可能包括多个顺序执行流,每个顺序执行流就是一个线程. 进程:进程是指处于运行过程中的程序,并且具有一定的独立功能.进程是系统进行资源分配和调度的一个单位.当程序进入内存运行时,即为进程. 进程的三个特点: 1:独立性:进程是系统中独立存在的实体,它可以独立拥有资源,每一个进程都有自己独立的地址空间,没有进程本身的运行,用户进程不可以直接访问其他进程的地址空间. 2:

随机推荐