Question

栈和队列的相似点在于，它们都可以把不能立即处理的数据暂时存储起来；不同点在于栈对所存储数据的存取方式是LIFO，而队列对所存储数据的存取方式是FIFI。既然已经了解了栈和队列的概念，接下来开始讲解如何用程序表示这两种数据结构。同样是数组，处理手段不同，得到的数据结构也会不同，数组有时可以转化为栈，有时可以转化为队列。

在实现栈这种数据结构时，首先要定义一个数组和一个变量，数组中所包含的元素个数就是栈的大小（栈中最多能存放多少个数据）。变量中则存储着一个索引，指向存储在栈中最顶端的数据，该变量被称为”栈顶指针“。栈的大小可以根据程序的需求任意指定。假设最多有100个数据，那么定义一个能把它们都存储下来的栈就可以了，这样的话就可以定义一个元素数为100的数组，这个数组就是栈的基础。接下来编写两个函数，一个函数用于把数据存入栈（压入栈中）；另一个函数用于从栈中把数据取出来（从栈中弹出）。在这两个函数中，都需要更新栈中所存储的数据的总数以及更新栈顶指针的位置。也就是说通过使用由数组、栈顶指针以及入栈函数和出栈函数所构成的集合，就能实现栈这种数据结构了（如代码清单6.6和图6.8所示）

代码清单6.6 使用数组、栈顶指针、入栈函数和出栈函数实现栈

char Stack[100];                 /*作为栈本质的数组*/

char StackPointer=0;          /*栈顶指针*/

/*入栈函数*/

void Push(char Data){

/*把数据存储到栈顶指针所指的位置上*/

Stack[StackPointer]=Data;

/*更新栈顶指针的值*/

StackPointer++;

}

/*出栈函数*/

char Pop(){

/*更新栈顶指针的值*/

StackPointer--;

/*把数据从栈顶指针所指的位置中取出来*/

return Stack[StackPointer];

}

图6.8 数组变成了“数据的小山”

为了实现队列这种数据结构，以下元素是必不可少的：（1）一个任意大小的数组；（2）一个用于存放排在队首的数据对应的索引的变量；（3）一个用于存放排在队尾的数据压的索引变量；（4）一对函数，分别用于把数据存入到队列和从队列中把数据取出来。如果数据一直存放在数组的末尾，那么下一个存储位置就会折回数组的开头。这样就相当于数组的末尾就和开头连接上了，于是虽然数组的物理结构是“直线”，但其逻辑结构已经变成了“圆环”（如代码清单6.7和图6.9所示）

代码清单6.7 使用一个数组、两个变量和两个函数实现队列

char Queue[100];                    /*作为队列本质的数组*/

char SetIndex=0;                    /*标识数据存储位置的索引*/

char GetIndex=0;                    /*标识数据读取位置的索引*/

/*存储数据的函数*/

void Set(char Data){

/*存入数据*/

Queue[SetIndex]=Data;

/*更新标识数据存储位置的索引*/

SetIndex++;

/*如果已到达数组的末尾则折回到开头*/

if (SetIndex>=100){

SetIndex=0;

}

}

/*读取数据的函数*/

char Get(){

char Data;

/*读出数据*/

Data=Queue[GetIndex];

/*更新标识数据读取位置的索引*/

GetIndex++;

/*如果已到达数组的末尾则折加开头*/

if (GetIndex>=100){

GetIndex=0;

}

/*返回读出的数据*/

return Data;

}

图6.9 数组变成了“数据环”