Page 77 - 高中 信息技术 选择性必修1 数据与数据结构

 3.3 用队列组织先进先出数据

（7）查找子串操作s1.find(s2)：找出主串s1中是否包含子串s2，包含则返回该子串位
置，不包含则返回空值。
（8）判断两个字符串是否相等s1.compare(s2)：比较s1、s2两个字符串是否相等，相等
返回T，否则返回F。

字符串相等，是指两个字符串长度相等且对应位置的元素一一相等。例如，字符串
s1="693450213"，s2="693450213"，s3="693550213"，其中串s2与s1相等，s3与s1不等。
顾客若要求查询编号为“693450213”的商品销量，则需将此字符串与销售记录中的
商品编号逐一比较，找到该字符串第一次出现的记录。

广东教育出版社
项目实施

各小组根据项目选题及拟订的项目方案，结合3.1节和3.2节所学知识，对所选定的模
拟实验进行系统分析和数据建模。
1. 分析实验过程中，哪些活动或问题可以利用字符串这一数据结构来解决。

2. 尝试编程实现。

3.3 用队列组织先进先出数据

我们在生活中到处都能看见排队的现象，排队购物、排队就诊、排队取号等。在这
些排队现象中，事物的进出顺序都有共同的特征，那就是先进先出。当我们要用计算机
程序来解决生活中排队的问题，实现排队事物的先进先出时，可以借助“队列”这种数
据结构。

3.3.1 队列

队列（Queue）是一种特殊的线性表，它只允许在表的一端进行插入，在表的另一端
进行删除。在队列中，可以插入的一端称为队尾，可以删除的一端称为队头。把一个数据
元素插入队列中的操作叫作进队，从队列中删除一个数据元素的操作叫作出队。队列中没
有元素时，称为空队列。

在日常生活中，售票窗外或服务台前，顾客按到达的先后次序排成一队。排在队头的
首先得到服务，然后离队。所有顾客一律平等，严格遵守秩序，不允许插队现象。也就是
说，队列中总是排在最前面的对象首先离队。
因此，队列符合这个规律：先放入队列中的数据元素首先取出。故队列又被称为先进

先出（FIFO：First In First Out）线性表。
69 69

21X2204.indd 69 2019/9/26 13:53:16