图解栈(Stack)与队列(Queue)

数据结构

身为程序猿或者攻城狮，你肯定知道数据结构这个东西的。而数据结构却有好几种类型，我简单罗列下：

1. 数组(Array)
   

2. 栈(Stack)

3. 队列(Queue)

4. 链表(Linked List)

5. 树(Tree)

6. 图(Graph)

7. 堆(Heap)

8. 散列(Hash)

以上，数据结构一般有以下几种常用运算：

1. 检索。检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。

2. 插入。往数据结构中增加新的节点。

3. 删除。把指定的结点从数据结构中去掉。

4. 更新。改变指定节点的一个或多个字段的值。

5. 排序。把节点按某种指定的顺序重新排列。例如递增或递减。

栈和队列的结构特点

对于这几种数据结构，在嵌入式软件开发中最为常用的是数组、栈和队列。其中数组最为简单了，是一种基础数据结构。如果我今天讲解数组，也许觉得太简单了浪费你的时间，可能会拍我砖头。于是，我今天打算图解栈和队列。

• 栈
  栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。

• 队列
  队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。

为了直观地表达这两种结构的特性，我们来两个图示：

栈：

队列：

从上面两个图可以看出，栈的出入口只有一个，而队列的入口和出口是分开的。我们就用两个专业名称来说明这两个特性，后进先出（LIFO）和先进先出（FIFO）。

很明显，栈是LIFO，而队列是FIFO。

对于栈，我们姑且将放入数据称为Push（压栈），取出数据称为Pop（出栈）；

为了区别栈的方式，对于队列，我们将放入数据称为EnQueue，取出数据称为DeQueue

以下详细分解图示来讲解下：

栈

以下是放入数据的过程：

1. Push第1个数据1

2. Push第2个数据2

3. Push第3个数据3

以下是取出数据的过程：

1. Pop第1个数据4

2. Pop第2个数据2

3. Pop第3个数据1

栈的实用案例

从结构特点看来，栈数据结构没毛作用（那是因为不会用）。假设产品需要显示一个存储设备上文件列表，你会怎么做呢？

有两条路：

• 深度优先BFS(Breadth-First-Search)
  即先搜索第1个文件夹的最深层文件夹（子文件夹的子文件夹的……）里面的文件，然后再返回上一层文件夹搜索。例如上图的，先搜索文件夹Folder11里的文件，在返回到Folder1里面搜索其下面的第2个文件夹，以此类推。

• 广度优先DFS(Depth-First-Search)
  即先搜索第1个文件夹下的文件，再搜索其下面子文件夹的文件。例如上图的，先搜索FolderRoot下面的文件，再搜索Folder1的文件，然后Folder2……

先不讨论哪条路比较好，姑且要按深度优先来，怎么做？

递归，其实这种方法很直观，反正遇到文件夹下面有文件夹就打开搜，直到没有文件夹为止。但是在嵌入式软件上开发，递归是非常低效的，对系统的栈内容要求非常大。

那么还有其他方法吗？有，那就栈数据结构。

以上图文件结构为例：

1. 以FolderRoot为起始（设置为当前搜索路径），搜索其下面的内容

2. 从当前搜索路径开始，搜索其内容，并判断每个条目

3. 遇到文件夹就将其Push到栈

4. 遇到文件就做相应处理

5. 直到搜索并判断完当前目录下所有条目

6. 将栈内容Pop出来，重复 第2点， 如没有，就结束。

具体过程如下：

Push Folder: FolderRoot
Pop Folder : FolderRoot
Get File   : FolderRoot/File1
Get File   : FolderRoot/File2
Push Folder: FolderRoot/Folder1
Push Folder: FolderRoot/Folder2
Push Folder: FolderRoot/Folder3
Pop Folder : FolderRoot/Folder3
Push Folder: FolderRoot/Folder3/Folder31
Pop Folder : FolderRoot/Folder3/Folder31
Get File   : FolderRoot/Folder3/Folder31/File311
Pop Folder : FolderRoot/Folder2
Get File   : FolderRoot/Folder2/File21
Get File   : FolderRoot/Folder2/File22
Pop Folder : FolderRoot/Folder1
Get File   : FolderRoot/Folder1/File11
Get File   : FolderRoot/Folder1/File12
Get File   : FolderRoot/Folder1/File13
Push Folder: FolderRoot/Folder1/Folder11
Push Folder: FolderRoot/Folder1/Folder12
Pop Folder : FolderRoot/Folder1/Folder12
Get File   : FolderRoot/Folder1/Folder12/File121
Pop Folder : FolderRoot/Folder1/Folder11
Get File   : FolderRoot/Folder1/Folder11/File111

队列

队列有好几种，如内存地址连续的线性队列和地址不连续的链式队列，队列又可以做成环形队列（或者叫循环队列）

线性队列：

链式队列：

环形队列：

这图长得太挫了，看这个：

在实际运用中，最多的应该是这个环形队列，如果队列的缓冲区大小能很好地平衡收入和取出的数据，就给人一种取之不尽用之不竭的感觉。

以下是放入数据的过程：

1. EnQueue第1个数据1

2. EnQueue第2个数据2

3. EnQueue第3个数据3

以下是取出数据的过程：

1. DeQueue第1个数据1

2. DeQueue第2个数据2

3. DeQueue第3个数据3

实际上队列里面一个元素并不是只限制一个字节数据，可以使一块数据

队列里面的数据还可以动态大小，要注意在数据块里面能找到计算方式即可，例如定义一个length

队列的实用案例

队列使用的更加广泛，例如：

1. FreeRTOS里面Task之间的数据传输用的就是队列

   
   

2. 通信过程中数据接收可以用队列做缓存

   
   

3. 

4. 上一章节的文件搜索例子，如果是广度优先搜索可以使用队列
   这个不画图了，读者自己思考下？

什么？你想要看源码？这个我还真没准备。

1. 实现个简单的Stack和Queue并不难，实际应用的还要考虑互斥等

2. 网上很多，各种版本都有，但建议你严加测试再使用

想获取更多内容，请关注微信公众号“嵌入式软件实战派”