资料存取的先後顺序:Stack 和 Queue

题组回顾与观念统整

Stack 和 Queue 绝对是资料结构中不可以错过的一种容器,不只用於资料结构中这两个字更广泛出现在整个电脑科学的应用当中,从记忆体的组成、网路间的沟通到各种程序框架中或多或少都会看到他的影子。这两种容器主要的特性是在於他们存取资料时隐含的先後顺序不一样(如下图所示),Stack 提供同一个入口与出口,先被加入的元素会比较晚被取出,这种特性称为「FILO(First In Last Out)」。Queue 是与前者相反的「FIFO(First In First Out)」的特性,也就是说它提供分别两个入口与出口,从入口先被加入的元素会从出口比较早被取出。

Algorithms - Stacks and Queues

更多细节可以参考 Algorithms - Stacks and Queues 内文。在前三天的刷题实战中,我们一起体验几题关於 Stack 和 Queue 的练习:

➤ 利用 Stack 优化「206. Reverse Linked List」、「700. Search in a Binary Search Tree」和「144. Binary Tree Preorder Traversal」

这三题是延续至前一段的题目,他们都根据链结串列(Linked List)或树(Tree)的特性采取的常用的递回法。从「递回法」的概念延伸,导入「堆叠(Stack)」的抽象资料结构,将原本一层一层的递回呼叫转化为 FILO(First In Last Out) 的储存顺序。为什麽会这样想呢?其实递回法本来的呼叫概念就是执行到一半,先跳到下一层完成後再回来继续执行,本质上也是一种 FILO 的顺序。差别只是把原本由作业系统管理的递回,我们利用 Stack 性质来管理而已。

➤「102. Binary Tree Level Order Traversal」

二元树因为其非线性的结构,因爲每一个节点可能会有左/右分支而有不同的先後顺序找法,这个过程称为遍历(Traverse)。这个题目定义的一种以阶层为主的遍历,因此我们必须要探访每一个点的同时也满足题目要求的先後顺序。因此在这个题目中,我们分别示范如何用「穷举迭代」、「用 Stack 暂存资料」和「用 Queue 暂存资料」三种方法时实现。

➤ Stack 与 Queue 的相互实作的「225. Implement Stack using Queues」与「232. Implement Queue using Stacks」

这两题是一组经典的题组,要求用 Queue 和 Stack 互相实作。这两种是存取方向不同的抽象资料结构,不会限定内内部如何实作,只要最终结果能够符合该结构的性质与方法即可,常见的方法可以利用阵列、阵列串链来实作。而这个题目比较特别的是,要求只能够用 Stack 与 Queue 两个结构相互实作,在实作上就需要对这他们有更多的熟悉才能够进一步运用。

经典的资料结构

资料结构(Data Structure)是由「资料」与「结构」两个字组成,「资料」是指由多个元素所组成的有限集合,这些元素的组合关系称为「结构」。换句话说,就是「一组资料在程序当中的储存/组织方式」,有时候我们也会称为容器(Container)或集合(Collection)。

你可能会从不同的来源看到不同的资料结构分类:

以上三张图分别来源:Fundamental Data Structures and Algorithms in C#Data Structure Interview QuestionsDS introduction,有兴趣也可以去看看原文。

从内建容器到善用资料结构特性

除了「阵列与列表」、「物件与字典」这些基本的容器之外,在不同的程序语言也都有提供其他的资料结构可以使用,或是你可以利用现有的容器组装出不同的资料结构。我们在前几天用到的「Set(集合)」和「Map」就是,过去我们可能会强调逻辑运算的思维(也就是比较复杂的回圈跟判断),不过当你掌握不同语言提供的容器、善用资料结构特性也能够让你写出更精简更优化的程序码。

线性与非线性的资料结构

从链结串列(Linked List)到树(Tree)或二元搜寻树(BST,Binary Search Tree),是一种从线性到非线性的概念。线性指的是只会有下一个可能,终究只会有一条路径;非线性的话则可能有不同的分岔,可能会产生出两条以上的可能路径。比起大部分程序语言内建的阵列或物件来说,链结串列和树更容易卡关,也增加了对於资料结构的一丝恐惧感。对於一个容器「建立」、「新增」、「删除」或「查询」都是基本的操作,不过当遇到复杂的链结串列或树结构,就多了一层的挑战。

Stack 与 Queue

最後回到 Stack 与 Queue 这两种资料结构容器,他们不同於前面几种关注在「存」的资料结构,Stack 与 Queue 更在意的是「存取」当中的先後顺序。如果有一连串的元素组成,先存入的元素,应该先被取出还是後取出呢?这就是 Stack 跟 Queue 所考虑的点,搭配上这两种结构更能用应用於不同的使用情境。

Stack 与 Queue

最後一段稍微来讨论关於 Stack 与 Queue 的定义与实作:

堆叠(Stack)

根据 维基百科 的定义:Stack(堆叠,又称为栈或堆栈),是电脑科学中一种特殊的串列形式的抽象资料型别,其特殊之处在於只能允许在连结串列或阵列的一端加入资料和输出资料的运算。由於堆叠资料结构只允许在一端进行操作,因而按照後进先出(LIFO, Last In First Out)的原理运作。

Stack 的应用情境

  • Procedure Call/Recursive Call之处理
  • Reversing Data (反转资料)
  • 中序式 (Infix) 与前序式 (Prefix)/後序式 (Postfix)间互转
  • 後序式的计算

伫列(Queue)

根据 维基百科 的定义:Queue(伫列,又称为队列),是先进先出(FIFO, First-In-First-Out)的线性容器,伫列只允许在後端进行插入操作,在前端进行删除操作。伫列的操作方式和堆叠类似,唯一的区别在於伫列只允许新数据在後端进行添加。

Queue 的应用情境

  1. 日常生活的排队行为。
  2. 在作业系统中的job scheduling,在相同的priority下, 利用queue来完成先到先作的策略。
  3. 有许多的I/O工作同时要处理。将所有的I/O要求,利用 queue来达成先到先作的策略。
  4. 用於模拟 (Simulation) 方面,如伫列理论 (Queuing Theory)。

嗨,大家好!我是维元,一名擅长网站开发与资料科学的双栖工程师,斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师,同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验,持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享,邀请你加入 订阅 接收最新资讯。


<<:  Day-17 你在专案中负责什麽项目?遇到什麽困难?怎麽解决?

>>:  认识CSS(七):CSS list-style

LeetCode解题 Day16

54. Spiral Matrix https://leetcode.com/problems/sp...

Day 18 : 模型前的资料处理 (2)

接着昨天的资料处理继续说明,今天来看看类别资料转换、资料降维、资料切割、交叉验证以及不不均衡的对应方...

[生日优惠-3] 汉来海港餐厅Buffet #当日寿星6折

早上去经济部的中区服务中心处理一点事情,回程时,想顺便解决午餐,开启我的寿星优惠口袋List,首选就...

Day 17 - Error Handling 错误处理

前言 错误处理往往是最容易被忽略的一块,因为 程序运行顺利,那当然不用考虑 error case 程...

[Re:PixiJS - Day43] pixi-particles 粒子效果 1/2:plugin 安装与开始使用

来到这次系列最後想讲的主体:粒子效果 PixiJS 实现粒子效果有两种方式: ParticleCon...