1700415299
1700415300
在牧场中，把干草堆积在地上就会形成一座小山。为了把干草堆成山就要从下往上不断地堆积。在程序中干草就相当于数据。而在给家畜喂食的时候，要从上往下把堆积的干草（数据）取下来，也就是说，数据的使用顺序与堆积顺序是相反的，通常把这种存取方式称为LIFO（Last In First Out，后进先出），即最后被存入 的数据最先被处理的。在那些作为程序处理对象的实际业务中，可以用栈来模拟诸如堆积在桌子上的文件等场景，既然无法马上处理，就暂且先都堆放在栈里吧
1700415301
1700415302
队列（Queue）就是等待做某事而排成的队（如图6.5所示）
1700415303
1700415304
图6.5 队列示意图
1700415305
1700415306
1700415307
1700415308
1700415309
队列与栈正相反，排在队首的乘客最先接受服务，通常把这种形式称为FIFI（First In First Out，先进先出），即最先被存入的数据最先被处理。当无法一下处理完数据的时候，就可以暂且先把这些数据排队。之后会介绍队列的数据结构，其实现方式一般是把数组的首尾相连，形成一个圆环
1700415310
1700415311
“链表”的概念相当于几个人手拉手排成一排（如图6.6所示）
1700415312
1700415313
图6.6 链表示意图
1700415314
1700415315
1700415316
1700415317
1700415318
某个人只要松开拉住的那只手，再去拉住另一只手，这一排人（相当于数据）的排列顺序就改变了。而只要松开拉住的手，再让一个新人加入进来并拉住他的手，就相当于完成了数据的插入操作
1700415319
1700415320
二叉树的概念正如其名，相当于一棵树，不过这棵树与自然界中的树稍有不同，二叉树从树干开始分杈，树枝上又有分杈，但每次都只会分成两杈，在每个分杈点上有一片叶子（相当于数据）（如图6.7所示）。稍后就会了解到二叉树其实是链表的特殊形态
1700415321
1700415322
图6.7 二叉树示意图
1700415323
1700415324
1700415325
1700415326
1700415327
1700415328
1700415329
1700415330
计算机是怎样跑起来的 [:1700412674]
1700415331
计算机是怎样跑起来的 6.5 要点5：了解栈和队列的实现方法
1700415332
1700415333
栈和队列的相似点在于，它们都可以把不能立即处理的数据暂时存储起来；不同点在于栈对所存储数据的存取方式是LIFO，而队列对所存储数据的存取方式是FIFI。既然已经了解了栈和队列的概念，接下来开始讲解如何用程序表示这两种数据结构。同样是数组，处理手段不同，得到的数据结构也会不同，数组有时可以转化为栈，有时可以转化为队列。
1700415334
1700415335
在实现栈这种数据结构时，首先要定义一个数组和一个变量，数组中所包含的元素个数就是栈的大小（栈中最多能存放多少个数据）。变量中则存储着一个索引，指向存储在栈中最顶端的数据，该变量被称为”栈顶指针“。栈的大小可以根据程序的需求任意指定。假设最多有100个数据，那么定义一个能把它们都存储下来的栈就可以了，这样的话就可以定义一个元素数为100的数组，这个数组就是栈的基础。接下来编写两个函数，一个函数用于把数据存入栈（压入栈中）；另一个函数用于从栈中把数据取出来（从栈中弹出）。在这两个函数中，都需要更新栈中所存储的数据的总数以及更新栈顶指针的位置。也就是说通过使用由数组、栈顶指针以及入栈函数和出栈函数所构成的集合，就能实现栈这种数据结构了（如代码清单6.6和图6.8所示）
1700415336
1700415337
代码清单6.6 使用数组、栈顶指针、入栈函数和出栈函数实现栈
1700415338
1700415339
char Stack[100]; /*作为栈本质的数组*/
1700415340
1700415341
char StackPointer=0; /*栈顶指针*/
1700415342
1700415343
/*入栈函数*/
1700415344
1700415345
void Push(char Data){
1700415346
1700415347
/*把数据存储到栈顶指针所指的位置上*/
1700415348