三、进栈、出栈操作

1. 进栈操作

1. 操作逻辑 现有元素a（top=0，指向data[0]），插入元素b时，需先将top+1，再填入元素，即S.top = S.top + 1; S.data[S.top] = x;，等价于S.data[++S.top] = x
2. 注意事项
   • 必须用++S.top而非S.top++，前者先移动指针再存值，后者先存值再移动指针，会导致位置错位
   • 入栈前需判断栈满，栈满不可进栈
3. 进栈代码

// 栈满判断
bool StackFull(SqStack S) {
    if (S.top == MaxSize - 1) {
        return true;
    } else {
        return false;
    }
}

// 新元素入栈
bool Push(SqStack& S, ElemType x) {
    if (StackFull(S)) {
        return false;
    }
    S.top = S.top + 1;     // 指针先加1
    S.data[S.top] = x;     // 新元素入栈
    // 等价于: S.data[++S.top] = x;
    return true;
}

2. 出栈操作

1. 操作逻辑 栈满（10个元素，top=9）时删除栈顶元素k，需先取出栈顶值，再将top-1，即x = S.data[S.top]; S.top = S.top - 1;，等价于x = S.data[S.top--];
2. 注意事项
   • 必须用S.top--而非--S.top，前者先取值再移动指针，后者先移动指针再取值，会取到错误元素
   • 出栈前需判断栈空，空栈不可出栈
   • 出栈仅逻辑删除，元素仍残留于内存中
3. 出栈代码

// 出栈
bool Pop(SqStack& S, ElemType& x) {
    if (StackEmpty(S)) {
        return false;
    }
    x = S.data[S.top];
    S.top = S.top - 1;
    // 等价于: x = S.data[S.top--];
    return true;
}

3. 读栈顶元素

读栈顶元素仅获取值，不改变栈顶指针位置，与出栈操作的核心区别是无top--步骤。

// 读栈顶
bool GetTop(SqStack& S, ElemType& x) {
    if (StackEmpty(S)) return false;
    x = S.data[S.top];
    return true;
}

4. 完整顺序栈代码

C++

#include <iostream>
using namespace std;
using ElemType = int;
#define MaxSize 10
typedef struct {
    ElemType data[MaxSize];
    int top;
}SqStack;
void InitStack(SqStack& S) {
    S.top = -1;
}
// 栈空
bool StackEmpty(SqStack S) {
    if (S.top == -1) {
        return true;
    } else {
        return false;
    }
}
// 栈满
bool StackFull(SqStack S) {
    if (S.top == MaxSize - 1) {
        return true;
    } else {
        return false;
    }
}
// 入栈
bool Push(SqStack& S, ElemType x) {
    if (StackFull(S)) {
        return false;
    }
    S.top = S.top + 1;     // 指针先加1
    S.data[S.top] = x;     // 新元素入栈
    // 等价于: S.data[++S.top] = x;
    return true;
}
// 出栈
bool Pop(SqStack& S, ElemType& x) {
    if (StackEmpty(S)) {
        return false;
    }
    x = S.data[S.top];
    S.top = S.top - 1;
    // 等价于: x = S.data[S.top--];
    return true;
}
// 读栈顶
bool GetTop(SqStack& S, ElemType& x) {
    if (StackEmpty(S)) return false;
    x = S.data[S.top];
    return true;
}
/*----------------  测试  ----------------*/
int main() {
    SqStack S;
    InitStack(S);
    for (int i = 1; i <= MaxSize + 1; ++i)          // 故意多 push 一次
        if (!Push(S, i))
            cout << "第" << i << "次入栈失败（栈满）";
    ElemType x;
    while (Pop(S, x))
        cout << x << " 出栈";
    return 0;
}

#include <iostream> using namespace std; using ElemType = int; #define MaxSize 10 typedef struct { ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack& S) { S.top = -1; } // 栈空 bool StackEmpty(SqStack S) { if (S.top == -1) { return true; } else { return false; } } // 栈满 bool StackFull(SqStack S) { if (S.top == MaxSize - 1) { return true; } else { return false; } } // 入栈 bool Push(SqStack& S, ElemType x) { if (StackFull(S)) { return false; } S.top = S.top + 1; // 指针先加1 S.data[S.top] = x; // 新元素入栈 // 等价于: S.data[++S.top] = x; return true; } // 出栈 bool Pop(SqStack& S, ElemType& x) { if (StackEmpty(S)) { return false; } x = S.data[S.top]; S.top = S.top - 1; // 等价于: x = S.data[S.top--]; return true; } // 读栈顶 bool GetTop(SqStack& S, ElemType& x) { if (StackEmpty(S)) return false; x = S.data[S.top]; return true; } /*---------------- 测试 ----------------*/ int main() { SqStack S; InitStack(S); for (int i = 1; i <= MaxSize + 1; ++i) // 故意多 push 一次 if (!Push(S, i)) cout << "第" << i << "次入栈失败（栈满）"; ElemType x; while (Pop(S, x)) cout << x << " 出栈"; return 0; }

Output:

Click "Run" to see output...

5. 注意问题

1. Push与Pop函数形参&的区别
   • Push(SqStack& S, ElemType x)：仅栈S带引用，因为只需修改栈，x按值传递即可（仅复制进栈，不修改原x）
   • Pop(SqStack& S, ElemType& x)：栈S和元素x都带引用，因为不仅要修改栈，还要将出栈值赋给x并传递回调用者
2. 比较与赋值的区别 判空、判满函数中需用比较运算符==，而非赋值运算符=，例如S.top == -1是判断栈空，S.top = -1是给栈顶指针赋值。

6. 栈顶指针的另一种定义方式

此方式下top指向下一个可插入的位置，初始化时top=0。

1. 进栈逻辑 先将元素填入当前top位置，再移动指针，即S.data[S.top] = x; S.top = S.top + 1;，等价于S.data[S.top++] = x;
2. 出栈逻辑 先移动指针，再取值，即S.top = S.top - 1; x = S.data[S.top];，等价于x = S.data[--S.top];