教你怎么用Java数组和链表实现栈
作者:活跃的咸鱼 发布时间:2023-10-29 08:13:57
标签:Java,数组,链表,实现栈
一、何为栈?
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
栈可以类比成现实生活中的弹夹或者羽毛球桶
二、用数组实现栈
用数组模拟栈的思路分析如图:
1.定义一个top变量(指针)表示栈顶初始化为-1.
2.定义一个变量来记录栈的大小。
3.入栈操作有数据加入到栈中:top++; arr[top]=value;
4.出栈操作: int value=arr[top]; top–; return value;
下面看完整代码示例:
class Stack{
public int maxsize;//栈的大小
public int top=-1;//栈顶
public int[] arr;
public Stack(int maxsize) {
this.maxsize = maxsize;
arr=new int[maxsize];
}
//判断栈是否为空
public boolean isEmpty(){
return top==-1;
}
//判断栈是否满
public boolean isFull(){
return top==maxsize-1;
}
//添加一个元素
public void push(int value){
if(isFull()){
throw new RuntimeException("栈满");
}
top++;
arr[top]=value;
}
//弹出一个元素
public int pop(){
if(isEmpty())
throw new RuntimeException("栈空");
int value=arr[top];
top--;
return value;
}
//遍历栈中的元素
public void traverse(){
if (isEmpty()){
return;
}
//需要从栈顶开始显示数据
for(int i = top; i >= 0 ; i--) {
System.out.printf("stack[%d]=%d\n", i, arr[i]);
}
}
}
入栈操作 top++;arr[top]=value;其实可以直接改写为arr[++top]=value;
出栈操作可以将 int value=arr[top]; top–;return value;改为return arr[top–];
三、链表实现栈
思路分析:
入栈操作:用一个临时节点保存当前栈顶节点,将入栈的新节点作为栈顶元素,并将next域指向原来的旧节点。 Node temp=top; top.setNext(temp);
出栈操作:先判断栈是否为空,不为空则将top节点的数据返回,并将top指向top的下一个next域:top=top.getNext();
public class LinkedListStack<V> {
static class Node<V>{
private V data;
private Node<V> next;
public V getData() {
return data;
}
public void setData(V data) {
this.data = data;
}
public Node<V> getNext() {
return next;
}
public void setNext(Node<V> next) {
this.next = next;
}
}
public int stackSize;//栈内元素的个数
public Node<V> top;//栈顶元素
public LinkedListStack() {
stackSize = 0;
top = null;
}
//入栈
public void push(V element){
Node<V> temp=top;
top=new Node<>();
top.setData(element);
top.setNext(temp);
stackSize++;
}
//出栈
public V pop(){
if (isEmpty())
throw new RuntimeException("empty stack");
V value=top.getData();
//栈顶指向下一个元素
top=top.getNext();
stackSize--;
return value;
}
//查看栈顶元素
public V peek(){
return top.getData();
}
//判断是否为空
public boolean isEmpty(){
return stackSize==0;
}
//查看栈内元素个数
public int getStackSize(){
return stackSize;
}
}
四、测试
public class Test {
public static void main(String[] args) {
LinkedListStack<String> stack = new LinkedListStack<>();
stack.push("a");
stack.push("b");
stack.push("c");
System.out.println(stack.pop());
System.out.println(stack.peek());
System.out.println(stack.getStackSize());
}
}
测试结果:
c
b
2
来源:https://blog.csdn.net/weixin_44991304/article/details/116713784
0
投稿
猜你喜欢
- java 线程池详解什么是线程池?提供一组线程资源用来复用线程资源的一个池子为什么要用线程池?线程的资源是有限的,当处理一组业务的时候,我们
- 前文本章是关于Java流程控制语句的最全汇总,本篇为汇总上篇。流程是人们生活中不可或缺的一部分,它表示人们每天都在按照一定的流程做事。比如出
- 说明在学习jvm相关知识时,一般会讲到类字节码相关内容,为了更清晰的了解类字码具体内容,一般我们会使用javap命令进行查看,但是仍然不够直
- 上一篇文章谈到音频剪切、混音、拼接与转码,也详细介绍cMake配置与涉及FFmpeg文件的导入: android端采用FFmpeg进行音频混
- 本文实例讲述了Java中对象的比较操作。分享给大家供大家参考,具体如下:一 点睛在Java中,有两种方式可用于对象间的比较:利用"
- Android安全加密专题文章索引Android安全加密:对称加密Android安全加密:非对称加密Android安全加密:消息摘要Mess
- 一.并行LINQSystem.Linq名称空间中包含的类ParallelEnumerable可以分解查询的工作,使其分布在多个线程上。尽管E
- 一、概述在软件开发中,有时需要保存一个对象的状态,以便于允许用户取消相关操作或者从以往的状态中恢复过来。比如一个文档版本管理系统,可以根据需
- 拖曳小球WPF的拖曳效果,基本配置一下,就可以了,但是自绘的话,就得自己控制,按键点击,按键移动和按键松开的事件,与其配合达到目的。这个效果
- Android 侧滑菜单的实现,参考网上的代码,实现侧滑菜单。最重要的是这个动画类UgcAnimations,如何使用动画类来侧滑的封装Fl
- 什么是枚举类型枚举类型(Enumerated Type) 很早就出现在编程语言中,它被用来将一组类似的值包含到一种类型当中。而这种枚举类型的
- 前言最近我跟自定义View杠上了,甚至说有点上瘾到走火入魔了。身为菜鸟的我自然要查阅大量的资料,学习大神们的代码,这不,前两天正好在郭神在微
- 问题描述:解决:检查以上是否版本一致。不行就再检查下面的:如果上面的方法还是不行的话,就建议你改一下pom文件中的maven插件编译级别,可
- 1、SQLite介绍SQLite,是一款轻型的数据库,是遵守的ACID关系型数据库管理系统,它包含在一个相对小的C库中。它的设计目标嵌入式是
- C++ 中const修饰虚函数实例详解【1】程序1#include <iostream>using namespace std;
- 今天在一个 .NET Core 项目中调用一个自己实现的使用 params 可变参数的方法时触发了 null 引用异常,原以为是方法中没有对
- Android 添加系统设置属性的实现及步骤Android源码开发中,常常要用到一些全局标志或者说变量,这时候我们可以给android系统添
- c#调用surfer软件,添加应用的方法:1.在项目文件上右键->添加引用2.选择COM标签页3.找到Surfer 9 type li
- __intSumintSum 函数可用于计算两个或多个整数值的总和。引用名称是可选的, 但它不能是有效的整数。{__intSum(2,5,M
- AsyncTask是一个很常用的API,尤其异步处理数据并将数据应用到视图的操作场合。其实AsyncTask并不是那么好,甚至有些糟糕。本文