当前位置：首页 > news >正文

pc网站怎么建设流程/360手机优化大师安卓版

news 2025/7/1 3:45:42

pc网站怎么建设流程,360手机优化大师安卓版,竞价托管外包公司,三丰云免费云服务器文章目录前言：浏览器与栈的纠缠如何理解“栈”？如何实现一个“栈”？基于数组的顺序栈基于链表的链式栈解答开篇🐱‍🐉作者简介：大家好，我是黑洞晓威，一名大二学生，希望和…

文章目录

- 前言：浏览器与栈的纠缠
- 如何理解“栈”？
- 如何实现一个“栈”？
- - 基于数组的顺序栈
  - 基于链表的链式栈
- 解答开篇

🐱‍🐉作者简介：大家好，我是黑洞晓威，一名大二学生，希望和大家一起进步。
👿本文收录于算法，本专栏是针对大学生、初学算法的人准备，解析常见的数据结构与算法，同时备战蓝桥杯。

前言：浏览器与栈的纠缠

浏览器的前进、后退功能，我想你肯定很熟悉吧？

当你依次访问完一串页面a-b-c之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面b和a。当你后退到页面a，点击前进按钮，就可以重新查看页面b和c。但是，如果你后退到页面b后，点击了新的页面d，那就无法再通过前进、后退功能查看页面c了。

假设你是浏览器的开发工程师，你会如何实现这个功能呢？

这就要用到我们今天要讲的“栈”这种数据结构。带着这个问题，我们来学习今天的内容。

如何理解“栈”？

关于“栈”，我有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。 后进者先出，先进者后出，这就是典型的“栈”结构。

在这里插入图片描述

从栈的操作特性上来看， 栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

我第一次接触这种数据结构的时候，就对它存在的意义产生了很大的疑惑。因为我觉得，相比数组和链表，栈带给我的只有限制，并没有任何优势。那我直接使用数组或者链表不就好了吗？为什么还要用这个“操作受限”的“栈”呢？

事实上，从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。

如何实现一个“栈”？

从刚才栈的定义里，我们可以看出，栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。理解了栈的定义之后，我们来看一看如何用代码实现一个栈。

实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作 顺序栈，用链表实现的栈，我们叫作 链式栈。

基于数组的顺序栈

我这里实现一个基于数组的顺序栈。

// 基于数组实现的顺序栈
public class ArrayStack {private String[] items;  // 数组private int count;       // 栈中元素个数private int n;           //栈的大小// 初始化数组，申请一个大小为n的数组空间public ArrayStack(int n) {this.items = new String[n];this.n = n;this.count = 0;}// 入栈操作public boolean push(String item) {// 数组空间不够了，直接返回false，入栈失败。if (count == n) return false;// 将item放到下标为count的位置，并且count加一items[count] = item;++count;return true;}// 出栈操作public String pop() {// 栈为空，则直接返回nullif (count == 0) return null;// 返回下标为count-1的数组元素，并且栈中元素个数count减一String tmp = items[count-1];--count;return tmp;}
}

基于链表的链式栈

基于链表实现的链式栈的代码:

/** 用链表作为栈的底层*/
public class SingleLinkedListStack {
//  用链表作为栈的底层public SingleLinkedList<E> list;public SingleLinkedListStack() {list = new SingleLinkedList();
}@Overridepublic void push(E e) {// TODO Auto-generated method stublist.addFirst(e);}@Overridepublic E pop() {// TODO Auto-generated method stubreturn (E) list.removeFirst();}@Overridepublic E peek() {// TODO Auto-generated method stubreturn  list.getfirst();}@Overridepublic int getSize() {// TODO Auto-generated method stubreturn list.getSize();}@Overridepublic boolean isEmpty() {// TODO Auto-generated method stubreturn list.isEmpty();}@Overridepublic String toString() {StringBuilder sb=new StringBuilder(); sb.append("stack ");sb.append("push:>");for(int i=0;i<list.getSize();i++) {sb.append(list.get(i));sb.append("->");}sb.append("null");return sb.toString();}}