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
1700415349
Stack[StackPointer]=Data;
1700415350
1700415351
/*更新栈顶指针的值*/
1700415352
1700415353
StackPointer++;
1700415354
1700415355
}
1700415356
1700415357
/*出栈函数*/
1700415358
1700415359
char Pop(){
1700415360
1700415361
/*更新栈顶指针的值*/
1700415362
1700415363
StackPointer—;
1700415364
1700415365
/*把数据从栈顶指针所指的位置中取出来*/
1700415366
1700415367
return Stack[StackPointer];
1700415368
1700415369
}
1700415370
1700415371
图6.8 数组变成了“数据的小山”
1700415372
1700415373
1700415374
1700415375
1700415376
为了实现队列这种数据结构，以下元素是必不可少的：（1）一个任意大小的数组；（2）一个用于存放排在队首的数据对应的索引的变量；（3）一个用于存放排在队尾的数据压的索引变量；（4）一对函数，分别用于把数据存入到队列和从队列中把数据取出来。如果数据一直存放在数组的末尾，那么下一个存储位置就会折回数组的开头。这样就相当于数组的末尾就和开头连接上了，于是虽然数组的物理结构是“直线”，但其逻辑结构已经变成了“圆环”（如代码清单6.7和图6.9所示）
1700415377
1700415378
代码清单6.7 使用一个数组、两个变量和两个函数实现队列
1700415379