数据结构stack (笔记)

1. 概念理解

        stack(中文名：堆栈、栈)：虽然它叫堆栈，但是它其实指的是栈，跟堆没啥关系。
        栈的特性：先进后出、后进先出(这个过程就类似于餐厅刷盘子）
(后进先出：LIFO, 即 Last In, First Out)

(上图来源; wiki)



(上图来源：wiki)

易混淆内容

① 数据结构中stack中文翻译成堆栈，那它到底是堆还是栈，或者说堆和栈是一个东西？
② 数据结构中堆和栈的区别与联系
③ 数据结构中的栈和堆与操作系统内存分区中的栈空间和堆空间的区别

④ 【数据结构/操作系统 堆和栈】区别及应用场景、底层原理图解

2. 时间复杂度

1> 因为后进先出，push和pop只针对栈顶元素
① push：O(1)
② pop：O(1)
③ 查看栈顶元素(Peeking at the element on the top of the stack)：O(1)
2> 因为我们需要把该盘子上的其他所有盘子一个一个拿走
④ 遍历或者说查看中间任意一个元素：O(n)

3. 实现方式

① 动态数组。 不考虑数组从中间、头部增删改查的情况。每次只从尾部插入、删除和遍历。
② 单向链表

4. 应用

① Windows记事本或word文档撤销功能(快捷键：Ctrl + Z)：从最新输入的内容开始撤销
② Windows剪切板(快捷键：Win + v)：

剪切板中的顺序(从上到下)：5 4 3 2 1，正好与记事本中的顺序相反
③ 操作系统中的内存管理
④ IDE中的括号匹配功能(vscode等编译软件通常配备)：先把我们输入的左括号压入栈，然后检测它有没有对应的括号
⑤ 浏览器的历史记录

5. 内容出处

frank付费课
学完数据结构不知道怎么用想要的语言实现，原因在于(下述依旧是付费课的内容)：
        没有彻底理解相应数据结构的思想(不知道它是什么、不知道它用在哪、它在内存中是如何操作的)，总之就是核心的东西不了解
        彻底了解数据结构核心后，依然不会实现，说明语言掌握有问题，训练太少，对该语言不熟练，没有真正掌握语言中最常见的流程，语言中共性的东西没有掌握(为什么使用控制流程和循环、为什么在C语言中使用结构体，在高级语言中不用结构体，用更好的方式去实现数据结构)，只知道for、while是循环，if是如果，不知道其背后的逻辑，或者练习太少用的时候想不到
        pop语言(c语言)必须知道：数据结构、指针(链表就涉及指针操作)、数组(最常见的一种数据结构)、函数
        数据结构这门课最重要的就是思想和案例应用。代码实现其实就应该相当于家庭作业的内容
        试着发现数据结构在日常生活或者电脑使用过程中的实际应用，一旦能感受到它们的存在，证明理解就比较深刻了。