Day4 栈：浏览器的前进和后退

最新推荐文章于 2025-01-26 10:33:42 发布

打磨时光

最新推荐文章于 2025-01-26 10:33:42 发布

阅读量152

点赞数

分类专栏：数据结构与算法

本文链接：https://blog.csdn.net/wjavadog/article/details/103341057

版权

数据结构与算法专栏收录该内容

30 篇文章

订阅专栏

本文详细介绍了栈这一数据结构的概念及其实现方式，包括使用数组和链表两种方法。探讨了栈的时间复杂度，特别是在动态扩容的情况下。通过具体示例展示了如何使用数组实现栈，并深入讨论了栈在函数调用、表达式求值和括号匹配等场景中的应用。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

主题：使用栈实现浏览器的前进和后退功能

问：什么是栈？
答：栈是一种操作受限的线性表，具有后进先出的功能

问：栈的实现方式有哪些？
答：使用数据实现栈和使用链表实现栈

问：入栈和出栈的时间复杂度？
答：入栈和出栈的时间复杂度均为O(1)，空间复杂度也为O(1)；但是如果是使用数组实现的栈，并且是动态扩容的，其出栈的时间复杂度是不变的为O(1)；其入栈的时间复杂度由于需要将原空间的数据复制到新的数组中，所以最好时间复杂度为O(1)，最坏时间复杂度为O(n), 均摊时间复杂度为 O(1)

问：栈的应用场景？
答：
	1. 函数调用
	2. 表达式求值
	3. 括号匹配

示例使用数组实现栈：

public class ArrayStack {
	private String[] items;
	private int count;
	private int n;
	public ArrayStack(int n) {
		this.items = new String[n];
		this.count = 0;
		this.n = n;
	}

	// 入栈操作
	public boolean push (String item) {
		if (count == n) return false;
		items[count] = item;
		count++;
		return true;
	}

	// 出栈操作
	public String pop () {
		if (count == 0) return null;
		String tmp = items[count-1];
		--count;
		return tmp;
	}
}