Page 91 - 高中 信息技术 选择性必修1 数据与数据结构

 3.4 用栈组织后进先出数据

可以用一维数组来实现用于存储顺序栈中数据元素的存储区域，首先定义一个足够大
（Maxsize）的一维数组，将数组下标为0的一端设为栈底，top指针指向栈顶元素的具体位
置有两种方法：一种是让top指针始终指向栈顶元素所在的位置，当top= -1时表示空栈

（如图3-20所示）；另一种是让top指针指向栈顶元素的下一个位置，当top= 0时表示空栈
（如图3-21所示）。

广东教育出版社

（a）空栈 （b）3个元素的栈 （a）空栈 （b）3个元素的栈

图3-20 Top指针指向栈顶元素 图3-21 Top指针指向栈顶元素的下一个位置

由于栈是一个动态结构，而数组是一个静态结构，所以在顺序栈的操作过程中会有
“溢出”情况的出现。当栈满时，如果再有元素入栈，将会产生“上溢（Overflow）”；

当栈空时，如果再执行出栈操作，将会产生“下溢（Underflow）”。为了避免发生栈溢出
情况，在进行入栈和出栈操作前应先检测栈是否已满或已空。
顺序栈的程序定义如下：
typedef struct

{
string items[maxsize];
int top;

}CarStack;
其中，maxsize为栈中允许存放元素个数的最大值，top是栈顶标志，指示存放数组的
下标，不是真正的指针，当top= -1时表示空栈，当top= maxsize -1时表示满栈。

顺序栈的操作可用如表3-6所示的程序代码实现。

表3-6 顺序栈的操作代码

功能 程序段

void InitStack(CarStack &st)
{
初始化栈。
st.top=-1; //把栈顶指针置为-1
}

83 83

21X2204.indd 83 2019/9/26 13:53:19