【基础篇】6 # 栈:如何实现浏览器的前进和后退功能?

简介: 【基础篇】6 # 栈:如何实现浏览器的前进和后退功能?

说明

【数据结构与算法之美】专栏学习笔记



什么是栈?


栈是一种“操作受限”的线性表,只允许在一端插入和删除数据,其特性就是后进先出、先进后出。

栈既可以用数组来实现,也可以用链表来实现。


  • 用数组实现的栈叫作顺序栈
  • 用链表实现的栈叫作链式栈



支持动态扩容的顺序栈


如果要实现一个支持动态扩容的顺序栈,就需要底层依赖一个支持动态扩容的数组,当数组空间不够时,重新申请一块更大的内存,将原来数组中数据统统拷贝过去。


支持动态扩容的顺序栈的入栈、出栈操作的时间复杂度:


   对于出栈操作:不会涉及内存的重新申请和数据的搬移,时间复杂度是 O(1)。


   对于入栈操作:当栈中有空闲空间时,入栈操作的时间复杂度是 O(1)。当空间不够时,就需要重新申请内存和数据搬移,时间复杂度是 O(n)。


下面用摊还分析法分析入栈操作的时间复杂度:


先做一些假设和定义:


   栈空间不够时,重新申请一个是原来大小两倍的数组;


   只有入栈操作没有出栈操作;


   定义不涉及内存搬移的入栈操作为 simple-push 操作,时间复杂度为 O(1)。


如果当前栈大小为 K,并且已满,当再有新的数据要入栈时,就需要重新申请 2 倍大小的内存,并且做 K 个数据的搬移操作,然后再入栈。后面的 K-1 次入栈操作,都不需要再重新申请内存和搬移数据,所以这 K-1 次入栈操作都只需要一个 simple-push 操作就可以完成。入栈操作的均摊时间复杂度就为 O(1)。



栈在函数调用中的应用


比较经典的一个应用场景就是函数调用栈


操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。


为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗?


   其实,我们不一定非要用栈来保存临时变量,只不过如果这个函数调用符合后进先出的特性,用栈这种数据结构来实现,是最顺理成章的选择。从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域。所以根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。




栈在表达式求值中的应用


栈的另一个常见的应用场景,编译器如何利用栈来实现表达式求值。


编译器就是通过两个栈来实现的。其中一个保存操作数的栈,另一个是保存运算符的栈。从左向右遍历表达式,当遇到数字,就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较。如果当前操作符的优先级比栈顶的要高,说明这一操作符需要先执行,但是数据还没有准备好,因此先将操作符保存起来,等数据准备好了再执行; 如果当前操作符的优先级比栈顶的要低,说明栈中的操作符需要先执行,那么先从数据栈中弹出两个数据,从操作符栈中弹出一个操作符,将这个结果先计算,并将计算出来的结果再入栈




栈在括号匹配中的应用


还可以用栈来检查表达式中的括号是否匹配。


如何检查包含三种括号(圆括号 ()、方括号[]、花括号{})的任意嵌套表达式字符串是否合法呢?


可以使用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号。当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式。




如何实现一个栈?

下面是基于链表实现的栈:https://github.com/wangzheng0822/algo/blob/master/javascript/08_stack/StackBasedOnLinkedList.js

class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}
export class StackBasedLinkedList {
    constructor() {
        this.top = null
    }
    push(value) {
        const node = new Node(value)
        if (this.top === null) {
            this.top = node
        } else {
            node.next = this.top
            this.top = node
        }
    }
    pop() {
        if (this.top === null) {
            return -1
        }
        const value = this.top.element
        this.top = this.top.next
        return value
    }
    // 为了实现浏览器前进后退
    clear() {
        this.top = null
    }
    display() {
        if (this.top !== null) {
            let temp = this.top
            while (temp !== null) {
                console.log(temp.element)
                temp = temp.next
            }
        }
    }
}

测试一下:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>06.如何实现一个栈</title>
</head>
<body>
    <script type="module">
        import { StackBasedLinkedList } from "./js/06/StackBasedOnLinkedList.js";
        const newStack = new StackBasedLinkedList();
        newStack.push(1);
        newStack.push(2);
        newStack.push(3);
        console.log('-------------')
        console.log(newStack)
        console.log('-------------')
        console.log(newStack.pop());
        console.log(newStack.pop());
        console.log(newStack.pop());
        console.log(newStack.pop());
    </script>
</body>
</html>



abf041dedf034124854d8abc89ff9f37.png



如何实现浏览器的前进和后退功能?

使用前后栈实现浏览器的前进后退:https://github.com/wangzheng0822/algo/blob/master/javascript/08_stack/SampleBrowser.js

import * as Stack from "./StackBasedOnLinkedList.js"
export class SampleBrowser {
    constructor() {
        this.normalStack = new Stack['StackBasedLinkedList']()
        this.backStack = new Stack['StackBasedLinkedList']()
    }
    // 正常浏览页面
    pushNormal(name) {
        this.normalStack.push(name)
        this.backStack.clear()
    }
    // 后退
    back() {
        const value = this.normalStack.pop()
        if (value !== -1) {
            this.backStack.push(value)
        } else {
            console.log('无法后退')
        }
    }
    // 前进
    front() {
        const value = this.backStack.pop()
        if (value !== -1) {
            this.normalStack.push(value)
        } else {
            console.log('无法前进')
        }
    }
    // 打印栈内数据
    displayAllStack() {
        console.log('---后退页面---')
        this.backStack.display()
        console.log('---浏览页面---')
        this.normalStack.display()
    }
}


测试代码:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>06.如何实现浏览器的前进和后退功能</title>
</head>
<body>
    <script type="module">
        import { SampleBrowser } from "./js/06/SampleBrowser.js";
        const browser = new SampleBrowser()
        browser.pushNormal("A页面")
        browser.pushNormal("B页面")
        browser.pushNormal("C页面")
        console.log(browser)
        browser.displayAllStack()
        console.log("-------------------------------------")
        browser.back()
        browser.back()
        browser.front()
        browser.displayAllStack()
        console.log("-------------------------------------")
        browser.pushNormal("N页面")
        browser.displayAllStack()
    </script>
</body>
</html>

f86cac6aa0a34f24b926af60bb8073e1.png


目录
相关文章
|
11月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
880 9
|
11月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
223 59
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
52 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
334 77
|
8月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
168 11
|
8月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
9月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
244 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
141 9
|
9月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
192 7