数据结构与算法(七)--使用链表实现栈

这篇具有很好参考价值的文章主要介绍了数据结构与算法(七)--使用链表实现栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、前言

之前我们已经学习了链表的所有操作及其时间复杂度分析,我们可以了解到对于链表头的相关操作基本都是O(1)的,例如链表头增加、删除元素,查询元素等等那我们其实有一个数据结构其实可以完美利用到这些操作的特点,都是在某一段进行操作,那就是栈。本章我们通过链表去实现栈。并且比较用数组实现和用链表实现他们之间的差异。

二、用链表实现栈

2.1、代码实现

那么通过链表实现栈就很简单了,我们知道入栈和出栈都是从链表的同一端进行操作,那么我们只需调用链表的addFirst/removeFirst的方法即可,查找同理。
首先我们将链表栈命名为LinkedListStack,并且实现我们Stack的抽象类,然后设置一个内部属性为我们之前实现的链表,通过该链表完成实现需要重写的方法即可,代码如下:

public class LinkedListStack<T> implements Stack<T> {
	private LinkedList<T> linkedList;

	public LinkedListStack() {
		this.linkedList = new LinkedList<>();
	}

	@Override
	public int getSize() {
		return linkedList.getSize();
	}

	@Override
	public boolean isEmpty() {
		return linkedList.isEmpty();
	}

	@Override
	public void push(T t) {
		linkedList.addFirst(t);
	}

	@Override
	public T pop() {
		return linkedList.removeFirst();
	}

	@Override
	public T peek() {
		return linkedList.getFirst();
	}

	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append("Stack: top ");
		stringBuilder.append(linkedList);
		return stringBuilder.toString();
	}
}

测试一下:

public static void main(String[] args) {
		LinkedListStack<Integer> integerArrayStack = new LinkedListStack<>();
		for (int i = 0; i < 5; i++) {
			integerArrayStack.push(i);
			System.out.println(integerArrayStack);
		}
		integerArrayStack.pop();
		System.out.println(integerArrayStack);
	}

结果没有问题,通过链表实现栈就这样简单的实现了。
数据结构与算法(七)--使用链表实现栈,数据结构和算法,链表,数据结构,栈

2.2、和数组栈比较性能

这个代码和之前数组队列和循环队列效率的对比很接近:

public class TestStackCompare {
	private static double testQueue(Stack<Integer> s, int opCount){
		long startTime = System.currentTimeMillis();
		Random random = new Random();
		for (int i = 0; i < opCount; i++) {
			s.push(random.nextInt(Integer.MAX_VALUE));
		}
		for (int i = 0; i < opCount; i++) {
			s.pop();
		}
		long endTime = System.currentTimeMillis();
		return (endTime - startTime)/1000.0;
	}

	public static void main(String[] args) {
		ArrayStack<Integer> integerArrayStack = new ArrayStack<>();
		LinkedListStack<Integer> integerLinkedListStack = new LinkedListStack<>();
		System.out.println("arrayStack,time:"+testQueue(integerArrayStack,1000000)+"s");
		System.out.println("linkedListStack,time:"+testQueue(integerLinkedListStack,1000000)+"s");
	}
}

那么我们运行下,发现两者效率近乎一致:
数据结构与算法(七)--使用链表实现栈,数据结构和算法,链表,数据结构,栈
当然也有可能得到的结果是有差距的,对于arrayStack来说,时不时就需要扩容,这个对于某些操作系统来说比较耗费时间,而对于linkedListStack来说,它每次new Node就需要不断的开辟空间,这个操作又对于某些操作系统来说更耗费时间;而且这两者的差距会随着操作次数的增多不断拉大,因为扩容并不是每次扩容,而new Node确实是需要每次都new一个,例如我将操作次数放大为10000000次,这个时候两者的时间差距就比较大了:
数据结构与算法(七)--使用链表实现栈,数据结构和算法,链表,数据结构,栈

所以仍然取决于你测试使用的操作系统,配置,jvm版本等等。但是其实我想强调的是,对于数组栈和链表栈来说,他们的各项操作的时间复杂度其实是一致的。他们之间没有复杂度之间的巨大差异。不像数组队列和循环队列,一个6s,一个0.01s,这之间的差距是非常大的。文章来源地址https://www.toymoban.com/news/detail-727453.html

到了这里,关于数据结构与算法(七)--使用链表实现栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构和算法】实现带头双向循环链表(最复杂的链表)

    前文,我们实现了认识了链表这一结构,并实现了无头单向非循环链表,接下来我们实现另一种常用的链表结构,带头双向循环链表。如有仍不了解单向链表的,请看这一篇文章(7条消息) 【数据结构和算法】认识线性表中的链表,并实现单向链表_小王学代码的博客-CSDN博客

    2024年01月17日
    浏览(76)
  • C++数据结构与算法详解:链表、栈、队列、树、二叉树和图结构的实现与应用

    链表是一种常见的数据结构由一系列节点按顺序连接而成,一般每个节点包含一个数据元素和一个指向下一个节点的引用。 链表有多种类型: 单向链表:每个节点只有一个指向下一个节点的引用 双向链表:每个节点有一个指向前一个节点和一个指向后一个节点的引用 循环链

    2024年02月04日
    浏览(47)
  • 数据结构----链表介绍、模拟实现链表、链表的使用

    ArrayList底层使用连续的空间,任意位置插入或删除元素时,需要将该位置后序元素整体往前或者往后搬移,故时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后

    2024年02月21日
    浏览(50)
  • 【数据结构与算法】- (带尾指针)单循环链表 - 详细实现步骤及代码(C/C++)

    前三篇文章分别介绍了 “带头结点单链表实现”、“不带头结点单链表实现”、“带头结点单循环链表实现”。 这篇文章主要介绍 带尾指针 的单循环链表以及详细的实现步骤,最后提供我自己根据理解实现带尾指针单循环链表的C语言代码 。跟着后面实现思路看下去,应该

    2024年02月16日
    浏览(38)
  • 【数据结构与算法】链表

    对于顺序表存在一些缺陷: 中间/头部的插入删除,时间复杂度为O(N) 。头部插入需要挪动后面的元素 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插

    2023年04月09日
    浏览(44)
  • 【算法与数据结构】链表

    链表是由一串节点串联在一起的,链表的每个节点存储两个信息:数据+下一个节点的地址 分清楚两个概念:什么是内存内部,什么是程序内部 内存内部: 信息存储在内存空间里的 程序内部: 通过什么信息,去操作结构 如果想操作链表的话,我们依靠的是程序内部的信息,

    2024年02月03日
    浏览(43)
  • 数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现,含注释

      头文件和源文件分开有很多好处:可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性,同时也可以使代码结构更清晰,方便代码的管理和维护。 LinkList.h test.cpp                  (下面所有函数都默认在类中实现)   我们以

    2024年02月07日
    浏览(54)
  • 02-链表 (数据结构和算法)

    3.1 链表的基本概念 前面我们在学习顺序表时,线性表的顺序存储结构的特点是逻辑关系上相邻的两个数据元素在物理位置上也是相邻的。我们会发现虽然顺序表的查询很快,时间复杂度为O(1),但是增删的效率是比较低的,因为每一次增删操作都伴随着大量的数据元素移动。为

    2024年02月16日
    浏览(43)
  • Python数据结构与算法-数据结构(列表、栈、队列、链表)

    数据结构是指相互之间存在这一种或者多种关系的数据元素的集合和该集合中元素之间的关系组成。 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字典等都是一种数据结构。 N.Wirth:“程序=数据结构+算法” 数据结构按照其 逻辑结

    2024年02月08日
    浏览(53)
  • 【数据结构与算法】双向链表

    作者:旧梦拾遗186 专栏:数据结构成长日记   带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。 现在我们来通

    2024年02月11日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包