专栏首页星月小站Java实现基本数据结构(二)——栈

Java实现基本数据结构(二)——栈

文章目录

前言

  阅读本文前,最好先学习顺序表的基本操作和实现原理,也就是弄清楚数组的原理,点击Java实现基本数据结构(一)——数组学习前置内容。学习效果更好哦!

栈的概念

  在数据结构中,栈和数组类似,也是一种线性表的结构。不同的地方在于栈是一种操作受限的线性表,它只允许数据从一端进行插入和删除,这一过程也就是我们经常说的进栈(push)和出栈(pop),这一端经常被称作为栈顶。根据这一种操作限制,可以得知栈每次删除的元素,都是最后进栈的元素。所以栈也被称作为后进先出表(LIFO:Last In First Out)。如图1所示,展示了一个栈的结构示意,和栈顶元素进栈或者出栈的操作示意:

                图1 栈的示意图

初识栈的应用

  栈在计算机系统中是一个应用非常广泛的数据结构,甚至可以说栈在计算机的世界中有着不可替代,不可思议的作用。

使用栈实现撤销操作

  比如,我们在使用word文档或者很多别的文档编辑器时,难免会出现编辑错字的情况,这个时候只需要点击一下撤销按键,或者使用Ctrl+z快捷键,就可以撤销上一步进行的操作。 当计算机进行这种Undo(撤销)操作时,其实在应用程序的底层,就是使用了栈来记录我们每一步的操作,并对其进行出栈操作来撤销,具体过程如下图所示:   (1)假设我们在使用word,现在想要输入一段“沉迷学习无法自拔”,在输入的时候,我们打错了字,输入了一段“沉迷学习不法”。其实我们在输入的时候,应用程序的底层是把我们每一步操作按顺序压入栈中,如下图所示,将我们输入的:“沉迷”,“学习”,“不法”依次进栈。

  (2)我们发现输入出错之后,就及时按下Ctrl+z,在word中的文字就从“沉迷学习不法”变回了“沉迷学习”。在撤销的过程中,其实就是应用程序将从栈中将我们最后一步操作的元素进行出栈,这样“不法”就从栈中被删除,我们就回到了上一步操作,这就是栈在撤销中的应用。

  在栈这种数据结构的具体实现上,一般有两种实现方式:线性存储和链接存储(链表)。也就是使用数组和链表这两种数据结构都可以实现栈。   下面我们分别对这两种方法进行实现。

在Java中使用线性存储实现栈结构

  在Java语言中,使用线性存储实现栈,实际上就是使用数组这样一种结构去实现栈。前面已经说过,栈是一种限制操作的线性表,也就是说实际上,对比数组,栈对应的操作其实就是数组的子集。 也就是说,我们实际上可以把栈这种结构看成一个特殊的数组,这个数组只能从一段添加元素,也只能从一端取出元素,这一端就称为栈顶。   和数组一样,线性存储的栈在使用时是静态分配的,就是使用的时候,内存已经以数组的形式开辟了一段空间,所以在初始化的时候,我们需要给定一个节点长度。

设计栈的功能

  根据栈这种数据结构的特点,在栈的实现上,我们只需要设计以下几个功能即可:   (1)进栈(push)操作:将一个元素压入栈中,实际上就是放进数组的头部。   (2)出栈(pop)操作:将栈顶的元素出栈,实际上就是将数组头部的元素删除,并返回这个元素。   (3)查看栈顶元素(peek)操作:将栈顶的元素返回给用户,实际上就是返回数组头部元素。   (4)返回栈的元素个数。   (5)判断栈是否为空。   其中比较重要的操作就是进栈和出栈,为了更容易理解这一过程,下面用图示的方法,展示一下进栈和出栈的过程:

  因为我们前面说过,栈这种数据结构可以有两种实现方式,一种是线性存储,即通过数组实现;一种是链接存储,即通过链表实现。为了方便后续的实现,我们首先定义一个Stack接口,后面分别用数组和链表来实现这个接口即可。

定义栈的接口

  按照上一小节的设计,我们直接在接口中约定这些功能即可。

public interface Stack<E> {  // 支持泛型
	int getSize();
	boolean isEmpty();
	void push(E e);
	E pop();
	E peek();
}

通过数组实现Stack接口

  为了更好的让本系列文章之间更好的串联知识点,本节实现的线性存储栈,将不使用JDK提供的ArrayList,使用Java实现基本数据结构(一)——数组中已经实现好的ArrayList类作为栈的存储结构。实际上,使用JDK提供的ArrayList类实现栈的方法是一样的,大家可以自行练习。   由于栈的功能比较简单,这里直接对栈进行代码实现,相关细节在注释中体现。

public class ArrayStack<E> implements Stack<E> {
	
	// 定义一个私有的成员变量array,用来存储数据
	private ArrayList<E> array;

	// 无参构造,直接使用ArrayList类中定义的无参默认值
	public ArrayStack() { 
		array = new ArrayList<>();
	}
	
	// 有参构造,用户可以定义栈的初始容量,实例化时调用ArrayList中的有参构造
	public ArrayStack(int capacity) {
		array = new ArrayList<>(capacity);
	}

	// 返回栈的元素个数,其实就是返回array的元素个数,调用array中的getSize()方法即可
	@Override
	public int getSize() {
		return array.getSize();
	}
	
	// 返回栈的总体容量大小,同上,就是返回array的容量空间
	public int getCapacity() {
		return array.getCapacity();
	}

	// 返回栈是否为空,其实就是返回array是否为空,调用array中的isEmpty()方法即可
	@Override
	public boolean isEmpty() {
		return array.isEmpty();
	}
	
	/* 
	 * 向栈顶添加元素,实际上就是向数组中添加元素,由于只能从数组一端添加.
	 * 为了高效,就限定只能从数组尾部添加即可。
	 * 用户调用push时,就永远只能从数组尾部插入数据,满足了栈的条件。
	 */
	@Override
	public void push(E e) {
		array.addLast(e);
	}

	/*
	 * 从栈顶出栈元素,其实就是将栈顶元素删除并返回。
	 * 由于添加的时候是从数组尾部添加的,所以这里只需要从数组尾部删除元素即可。
	 * array中的删除函数,我们已经完成了将删除的元素返回,直接使用即可。
	 */
	@Override
	public E pop() {
		return array.removeLast();
	}

	/*
	 * 从栈顶查看元素,就是将数组尾部的元素返回即可。
	 * 由于ArrayList中我们没有定义一个直接返回数组尾部的函数。
	 * 所以需要使用array.get()函数,再将尾部下标传入即可。
	 */
	@Override
	public E peek() {
		return array.get(getSize()-1);
	}
	
	// 覆盖toString函数,便于输出栈的信息
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append("Stack: [");
		for (int i = 0; i < array.getSize(); i++) 
		{
			res.append(array.get(i));
			// 如果不是最后一个数,就加个逗号
			if (i != array.getSize() - 1) 
				res.append(",");
		}
		// 标记一下栈顶的位置
		res.append("] Top");
		return res.toString();
	}

}

  可以看到,栈的代码其实就是对数组的限制应用,下面我们写一个测试,对我们实现的栈进行验证。

public class Main {

	public static void main(String[] args) {
	
		ArrayStack<Integer> stack = new ArrayStack<Integer>();
		for (int i = 0; i < 10; i++) 
			stack.push(i);
		System.out.println(stack.toString());
		
		int a = stack.pop();
		System.out.println(a);
		
		int b = stack.peek();
		System.out.println(b);
		
		stack.push(100);
		System.out.println(stack);
		
	}

}

  输出结果如下:

  可以看出,我们实现的栈是满足栈的定义的。至此,线性存储的栈就被我们实现了。下面我们分析下线性存储栈各个操作的时间复杂度,如下图所示:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java实现基本数据结构(三)——队列

    阅读本文前,最好先学习顺序表和栈的基本操作和实现原理,也就是弄清楚数组和栈的原理,点击Java实现基本数据结构(一)——数组,Java实现基本数据结构(二)——...

    星如月勿忘初心
  • Spring框架源码分析(IoC):BeanFactory和ApplicationContext容器家族

    组件扫描:自动发现应用容器中需要创建的Bean。 自动装配:自动满足Bean之间的依赖。

    星如月勿忘初心
  • Java后端面试学习知识总结

    本系列文章是在学习Java后端知识中进行总结与考证的结晶,梳理了Java后端面试与学习的核心知识体系,并对核心知识进行了讲解,属于BFS型知识讲解,在总结的过程...

    星如月勿忘初心
  • 二维数组与语法糖

    距离上一篇稿子大约又有一周多的时间了。在这一周多的时间里,我还是蛮感动的,因为有好多人还一直惦记着这个专栏~有一位头像贼眼熟的小姐姐还特意在我的CSDN博客下留...

    谭庆波
  • 每日一题 剑指offer(调整数组顺序)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • PHP array_reduce()函数的应用解析

    array_reduce() 函数向用户自定义函数发送数组中的值,并返回一个字符串。

    砸漏
  • 初学者必备的数组相关知识点

    作者是一名在读的大二学生,在我看来,是一个非常励志的小伙子,虽然他总觉得自己并不是读的名校,有点小小的不自信,但我相信这么早就意识到学习重要性的小伙子未来可期。

    AI算法与图像处理
  • array_shift() 函数

    似水的流年
  • array_shift() 函数

    实例 删除数组中的第一个元素(red),并返回被删除元素的值: <?php $a=array("a"=>"red","b"=>"green","c"=...

    似水的流年
  • 【Numpy】数值计算工具Numpy的基本操作

    (1)Scipy库简介 Scipy库是基于Python生态的一款开源数值计算、科学与工程应用的开源软件,包括常用的Numpy、pandas、matplotli...

    魏晓蕾

扫码关注云+社区

领取腾讯云代金券