栈的顺序存储结构

顺序栈的实现

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。

栈的顺序存储类型可描述为：

#define MaxSize 50             //定义栈中元素的最大个数
typedef struct {
    ElemType data[MaxSize];    //存放栈中元素
    int top;                   //栈顶指针
} SqStack;                     // 重命名为 SqStack（Sq：sequence —— 顺序）

【注】 顺序栈的一个显著缺点：栈的空间是固定的，不能动态扩展。

顺序栈的基本操作

初始化

void InitStack(SqStack &S) {
    S.top = -1; //初始化栈顶指针
}

入栈

第一种实现方式

bool Push(SqStack &S, ElemType x) {
    if (S.top == MaxSize - 1) //栈满，报错
        return false;
    S.data[++S.top] = x; //指针先加1，再入栈
    return true;
}

第二种实现方式

bool Push(SqStack &S, ElemType x) {
    if (S.top == MaxSize - 1) //栈满，报错
        return false;
    S.top = S.top + 1;   // 指针先加 1 
    S.data[S.top] = x;   // 新元素入栈
    return true;
}

出栈

第一种实现方式

bool Pop(SqStack &S, ElemType &x) {
    if (S.top == -1) //栈空，报错
        return false;
    x = S.data[S.top--]; //先出栈，指针再减1
    return true;
}

第二种实现方式

bool Pop(SqStack &S, ElemType &x) {
    if (S.top == -1) //栈空，报错
        return false;
    x = S.data[S.top]; //记录栈顶元素
    S.top = S.top - 1; //指针再减1
    return true;
}

【注】 执行出栈操作后，被出栈的数据依然残留在内存中，只是逻辑上被删除了。

读栈顶元素

bool GetTop(SqStack S, ElemType &x) {
    if (S.top == -1) //栈空，报错
        return false;
    x = S.data[S.top]; //记录栈顶元素
    return true;
}

判栈空

bool StackEmpty(SqStack S) {
    if (S.top == -1) //栈空
        return true;
    else //不空
        return false;
}

注意区分两种不同的初始化方式

当 S.top=-1 时 top 指的是栈顶元素。

• 入栈操作： S.data[++S.top]=x
• 出栈操作： x=S.data[S.top--]

---

当 S.top=0 时 top 指的是栈顶元素的下一位置。

• 入栈操作： S.data[S.top++]=x
• 出栈操作： x=S.data[--S.top]

共享栈

利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如图所示。

#define MaxSize 10             //定义栈中元素的最大个数
typedef struct {
    ElemType data[MaxSize];    //存放栈中元素
    int top0;                  // 0 号栈栈顶指针
    int top1;                  // 1 号栈栈顶指针
} SqStack;

// 初始化栈
void InitStack(SqStack &S) {
    S.top0 = -1;
    S.top1 = MaxSize;
}

两个栈的栈顶指针都指向栈顶元素，top0=-1 时 0 号栈为空， top1=MaxSize 时 1 号栈为空；仅当两个栈顶指针相邻（top1－top0＝1）时，判断为栈满。当 0 号栈入栈时 top0 先加 1 再赋值，1 号栈入栈时 top1 先减 1 再赋值；出栈时则刚好相反。

共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为 $O(1)$ ，所以对存取效率没有什么影响。