第十周软件工程学习知识总结（《数据结构与算法》）

一.栈和队列

1.抽象数据类型 (Abstract Data Type 简称ADT) 是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。

最常被提起的抽象数据类型就是栈 (stack) 和 队列 (queue)。从数学模型的观点来看，栈与队列都是一个放置相同物件的「容器」(container)，而且每个容器都只有四个操作：

加入一个物件，取出一个物件，检查一个「特定」的物件，和检查容器内有没有物件。

栈和队列的「容器」各有其特性：

栈的物件是先进后出 (first-in-last-out, FILO) 或后进先出 (last-in-first-out, LIFO)；队列的物件是先进先出 (first-in-first-out, FIFO) 或后进后出 (last-in-last-out, LILO)。 栈就如同一条单一出入口，且宽度只容一部汽车的停车道，先停进去的车，要最后离开。 队列就如同排队买电影票的人，先排进队伍的人，买到票后，就先离开队伍

计算机科学或软件工程的领域对栈与队列的四个操作有特定的名称：

栈：

push: 加入一个物件，入栈、推入、…；

pop: 取出一个物件，出栈、弹出、…；

top: 检查一个「特定」的对象，顶部、头部、…，

isEmpty: 和检查容器内有没有物件，为空、…。

队列：

enqueue: 加入一个物件，入队；

dequeue: 取出一个物件，出队；

head: 检查一个「特定」的对象，头部；

isEmpty: 和检查容器内有没有对象，为空。

栈和队列都是一种具有某些特性的线性表 (linear list)，它们可使用固定数组、动态数组、单链线性表、或双链线性表来实现。

在 C 程序语言可使用动态数组 (dynamic array) 实现栈：

数据结构：

 基本操作介面：

主程序中进行多回的入栈/出栈操作，测试回数为 trial_count，最多 10 回。每回连续入栈 push_count 个元素，然后出栈 pop_count 个元素；每回入栈最多 100 个元素，出栈最多是目前栈的元素个数。参数 trial_count, push_count 和 pop_count 都是随机数。

1.头文件

 2.c档

 3.主程序

4.运行结果

2.单向链接表的栈

在 C 程序语言也可使用单向链结表 (single-linked list) 实现栈：

将尾节点当成顶部，每次入栈都将新加入的元素放置在尾节点；底部一直都是在头节点；每次出栈都是移除尾节点的元素。

数据结构：

 1.头文件

 2.c档

 3.主程序

 4.运行结果

 2.动态数组的队列

在 C 程序语言可使用动态数组 (dynamic array) 实现队列： 队列的初始状态是一段 (SEGMENT) 元素的容量，队列为空时，它的头部与尾部索引都是 -1。

当第一个元素入队后，队列的头部与尾部索引都是 0；之后每当队列的头部与尾部索引相同时，队列只有一个元素。如果队列最后的单一元素出队后，队列成为空的，将头部与尾部索引重设为 -1，且容量设为 SEGMENT 的长度。

队列的头部索引修改是循环地向左移动，也就是说当一个元素出队时，头部索引 head 被设成 (head+1)%capacity. 例如，假设目前队列有 50 个元素，即 capacity==50, 若 head 为 25，一个元素出队后，head 成为 26；若 head 为 0，一个元素出队后，head 成为 0。

队列的尾部索引修改是循环地向右移动，也就是说当一个元素入队时，尾部索引 tail 被设成 (tail+1)%capacity. 例如，假设目前队列有 50 个元素，即 capacity==50, 若 tail 为 25，一个元素入队后，tail 成为 26；若 tail 为 49，一个元素入队后，tail 成为 0.

队列的头部和尾部索引各为 head 和 tail 时，队列的元素个数为 size = (tail-head+capacity)%capacity+1.

队列随时会有空的位置准备接受下一个入队的元素，而且一个元素出队后空位不能超过或等于两段的元素长度。也就是说元素入队后，若 capacity-size==0, 则队列容量要扩增一段元素；元素出队后，若 capacity-szie≥SEGMENT*2, 则队列容量要缩减一段元素。请注意，队列容量扩增或缩减时，原有的队列元素需要重新搬动，调整位置。

数据结构：

 1.头文件

 2.c档

 3.主程序

 4.运行结果