Java语言实现数据结构栈代码详解
作者:SilentKnight 发布时间:2021-12-09 16:15:05
标签:java,栈,数据结构
近来复习数据结构,自己动手实现了栈。栈是一种限制插入和删除只能在一个位置上的表。最基本的操作是进栈和出栈,因此,又被叫作“先进后出”表。
首先了解下栈的概念:
栈是限定仅在表头进行插入和删除操作的线性表。有时又叫LIFO(后进先出表)。要搞清楚这个概念,首先要明白”栈“原来的意思,如此才能把握本质。
"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈、出栈的说法。
实现方式是这样的:首先定义了一个接口,然后通过这个接口实现了线性栈和链式栈,代码比较简单,如下:
package com.peter.java.dsa.interfaces;
/**
* 栈操作定义
*
* @author Peter Pan
*/
public interface Stack<T> {
/* 判空 */
Boolean isEmpty();
/* 清空栈 */
void clear();
/* 弹栈 */
T pop();
/* 入栈 */
Boolean push(T data);
/* 栈的长度 */
int length();
/* 查看栈顶的元素,但不移除它 */
T peek();
/* 返回对象在栈中的位置 */
int search(T data);
}
线性栈:以数组的方式实现。
package com.peter.java.dsa.common;
import com.peter.java.dsa.interfaces.Stack;
/**
* 线性栈
*
* @author Peter Pan
*/
public class LinearStack<T> implements Stack<T> {
@SuppressWarnings("unchecked")
private T[] t = (T[]) new Object[16];
private int size = 0;
@Override
public Boolean isEmpty() {
// TODO Auto-generated method stub
return size == 0;
}
@Override
public void clear() {
// TODO Auto-generated method stub
for (int i = 0; i < t.length; i++) {
t[i] = null;
}
size = 0;
}
@Override
public T pop() {
// TODO Auto-generated method stub
if (size == 0) {
return null;
}
T tmp = t[size - 1];
t[size - 1] = null;
size--;
return tmp;
}
@Override
public Boolean push(T data) {
// TODO Auto-generated method stub
if (size >= t.length) {
resize();
}
t[size++] = data;
return true;
}
@Override
public int length() {
// TODO Auto-generated method stub
return size;
}
@Override
public T peek() {
// TODO Auto-generated method stub
if (size == 0) {
return null;
} else {
return t[size - 1];
}
}
/* return index of data, return -1 if no data */
@Override
public int search(T data) {
// TODO Auto-generated method stub
int index = -1;
for (int i = 0; i < t.length; i++) {
if (t[i].equals(data)) {
index = i;
break;
}
}
return index;
}
@SuppressWarnings("unchecked")
private void resize() {
T[] tmp = (T[]) new Object[t.length * 2];
for (int i = 0; i < t.length; i++) {
tmp[i] = t[i];
t[i] = null;
}
t = tmp;
tmp = null;
}
/* from the left to the right is from the top to the bottom of the stack */
@Override
public String toString() {
// TODO Auto-generated method stub
StringBuffer buffer = new StringBuffer();
buffer.append("Linear Stack Content:[");
for (int i = t.length - 1; i > -1; i--) {
buffer.append(t[i].toString() + ",");
}
buffer.append("]");
buffer.replace(buffer.lastIndexOf(","), buffer.lastIndexOf(",") + 1, "");
return buffer.toString();
}
}
链式栈:通过单链表进行实现。
package com.peter.java.dsa.common;
import com.peter.java.dsa.interfaces.Stack;
public class LinkedStack<T> implements Stack<T> {
private Node top;
private int size;
@Override
public Boolean isEmpty() {
// TODO Auto-generated method stub
return size == 0;
}
@Override
public void clear() {
// TODO Auto-generated method stub
top = null;
size = 0;
}
@Override
public T pop() {
// TODO Auto-generated method stub
T topValue = null;
if (top != null) {
topValue = top.data;
Node oldTop = top;
top = top.prev;
oldTop.prev = null;
size--;
}
return topValue;
}
@Override
public Boolean push(T data) {
// TODO Auto-generated method stub
Node oldTop = top;
top = new Node(data);
top.prev = oldTop;
size++;
return true;
}
@Override
public int length() {
// TODO Auto-generated method stub
return size;
}
@Override
public T peek() {
// TODO Auto-generated method stub
T topValue = null;
if (top != null) {
topValue = top.data;
}
return topValue;
}
@Override
public int search(T data) {
// TODO Auto-generated method stub
int index = -1;
Node tmp = top;
for (int i = size - 1; i > -1; i--) {
if (tmp.data.equals(data)) {
index = i;
break;
} else {
tmp = tmp.prev;
}
}
tmp = null;
return index;
}
@Override
public String toString() {
// TODO Auto-generated method stub
StringBuffer buffer = new StringBuffer();
buffer.append("Linked Stack Content:[");
Node tmp = top;
for (int i = 0; i < size - 1; i++) {
buffer.append(tmp.toString() + ",");
tmp = tmp.prev;
}
tmp = null;
buffer.append("]");
buffer.replace(buffer.lastIndexOf(","), buffer.lastIndexOf(",") + 1, "");
return super.toString();
}
private class Node {
T data;
Node prev;
public Node(T data) {
// TODO Auto-generated constructor stub
this.data = data;
}
}
}
学习还在进行中,以后会继续更新代码。
就是本文关于Java语言实现数据结构栈代码详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
来源:http://www.cnblogs.com/littlepanpc/p/3436419.html
0
投稿
猜你喜欢
- 比如在类上使用该注解 @Alias("dDebtEntity")则在mapper.xml文件中resultType=&q
- 本文实例讲述了Java基于享元模式实现五子棋游戏功能。分享给大家供大家参考,具体如下:一、模式定义享元模式,以共享的方式高效地支持大量的细粒
- 配置文件中设置通常在公司级别的项目中,我们可能会写多个application- dev/prod.yml ,然后我们通常会在applicat
- 引言:编写高效简洁的C语言代码,是许多软件工程师追求的目标。本文就工作中的一些体会和经验做相关的阐述,不对的地方请各位指教。第1招:以空间换
- instanceof判断某个对象是否是某个类的实例或者某个类的子类的实例。它的判断方式大概是这样的:public<T> bool
- 背景众所周知,所有被打开的系统资源,比如流、文件或者Socket连接等,都需要被开发者手动关闭,否则随着程序的不断运行,资源泄露将会累积成重
- 一、数组创建1.1 声明并赋值int[] a = {1,2,3};1.2 声明数组名开辟空间并且赋值int[] a;a = new int[
- package 移位运算;public class 移位运算 { public static void main(String[] args
- 说道线程,肯定会想到使用 java.lang.Thread.java这个类那么创建线程也主要有2种方式第一种方式:public class
- 本文实例讲述了Android中TextView显示插入的图片实现方法。分享给大家供大家参考,具体如下:Android系统默认给TextVie
- 前言博主上个礼拜,已经实现了quarkus的native image应用的上线,经过两天的监控下来,一切运行指标良好,就是内存升到了100M
- 您已经看到很多包含视频内容的应用程序,比如带有视频教程的食谱应用程序、电影应用程序和体育相关的应用程序。您是否想知道如何将视频内容添加到您的
- 做Java编程,难免会遇到多线程的开发,但是JDK8这个CompletableFuture类很多开发者目前还没听说过,但是这个类实在是太好用
- springboot读取配置文件到静态工具类通常我们读取配置文件可以用@Value注解和@Configuration,@Configurat
- 前言spring中解析元素最重要的一个对象应该就属于 BeanDefinition了;这个Spring容器中最基本的内部数据结构;它让xml
- 一、引入pom<?xml version="1.0" encoding="UTF-8"?>
- ShardingSphere的路由引擎类型本篇文章源码基于4.0.1版本上篇文章我们了解到了ShardingSphere在路由流程过程中,根
- 现在很多的网站都提供有用户注册功能, 通常我们注册成功之后就会收到一封来自注册网站的邮件。邮件里面的内容可能包含了我们的注册的用户名和密码以
- 在style中如下面那样定义:<style name="mystyle"> <item name=&
- 对接支付宝支付接口,官方文档已经写的很清楚了,但是也有很多像我一样的小白,第一次对接支付宝支付接口,会有些迷茫,所以我在此写下这篇文章,给我