Skip to Main Content
计算机科学导论:跨学科方法
book

计算机科学导论:跨学科方法

by 罗伯特 塞奇威克, 凯文 韦恩
August 2021
Beginner to intermediate content levelBeginner to intermediate
450 pages
19h
Chinese
Pearson
Content preview from 计算机科学导论:跨学科方法

4.3 栈和队列

在本节,我们将介绍两个相互关联的数据类型:栈和队列,它们都可以来处理任意大小的对象集合。栈和队列都是集合的一些具体实现。我们将集合中的对象称为数据项(item)。一个集合具有四个基本操作:创建一个集合、插入一个项、删除一个项,以及测试集合是否为空。

当我们将一个项插入一个集合中时,目的是明确的。但是当删除一个项时,应该删除哪一个呢?每种类型的集合的删除规则决定了它的特征,并且每种集合也有针对不同性能要求的实现。在现实生活中,你已经遇到过很多种不同的集合和数据项的删除方式,只是你还没有意识到。

例如,队列的删除规则是总是删除集合中存在最长时间的项。这种策略称为“先进先出”(First In First Out,FIFO)。人们排队买票就是遵循这一原则:队列按到达顺序排列,因此离开队列的人比其他人排队的时间长。

栈的删除规则则是一个完全不同的策略:总是删除进入集合时间最短的项。这个策略被称为“后进先出”(Last In First Out,LIFO)。例如,当进入和离开飞机客舱时遵循的策略接近于后进先出:靠近船舱前部的人登机最晚但离开最早。

栈和队列的应用十分广泛,因此,熟悉其基本属性以及每种适用的场景十分重要。它们都是可以用来解决更高级别编程任务的基本数据结构。它们被广泛应用于系统和应用程序设计,在本节和4.5节的几个例子中会涉及。

下推栈 下推栈(或者简称为栈)是一种基于后进先出(LIFO)策略的集合。

下推栈操作示意图

LIFO策略是经常使用的几个计算机应用程序的基础。例如,许多人把电子邮件作为一个栈来组织,当接收到一个新邮件时,会把它放在最上面,位于最上面的邮件先被处理,即最近的日期优先(后进先出)。这个策略的优点是我们可以尽快看到新的邮件,缺点是如果不清空堆栈,一些旧的邮件可能永远不会被阅读。 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

数据科学之编程技术:使用R进行数据清理、分析与可视化

数据科学之编程技术:使用R进行数据清理、分析与可视化

迈克尔 弗里曼, 乔尔 罗斯
C语言核心技术(原书第2版)

C语言核心技术(原书第2版)

Peter Prinz, Tony Crawford

Publisher Resources

ISBN: 9787111641414