本文共 2013 字，大约阅读时间需要 6 分钟。

顺序栈的基本概念与实现

顺序栈是计算机科学中的一个重要数据结构，它基于先进后出的原则进行操作。这个概念类似于一群人进入狭窄的死胡同，先进入的人被堵在里面，而后进入的人则可以先出去。理解这一点对于掌握栈的操作至关重要。

栈的基本特性包括先进后出（FILO），以及它能动态调整容量的特性。当栈已满时，继续存入数据会导致上溢；而当栈为空时，继续出栈则会引发下溢。

接下来，我们来看看顺序栈的一些操作。以下是使用C语言实现的栈结构和相关函数。

栈的结构定义如下：

#define STACK_SIZE 100 // 初始的储存空间
#define STACK 10    // 储存空间分配的增量
typedef struct stack {
    int *base;    // 栈的基地址
    int *top;    // 栈顶指针
    int stacksize; // 栈的容量
} *Stack;

初始化栈的函数实现：

Stack initStack(Stack s) {
    s = (Stack)malloc(sizeof(Stack));
    if (!s) {
        exit(0);
    }
    s->base = (int*)malloc(STACK_SIZE * sizeof(int));
    if (!s->base) {
        exit(0);
    }
    s->top = s->base;
    s->stacksize = STACK_SIZE;
    return s;
}

判断栈是否为空的函数：

int IsEmpty(Stack s) {
    if (s->top == s->base) {
        return 1; // 栈为空
    } else {
        return 0; // 栈不为空
    }
}

判断栈是否已满的函数：

int Full(Stack s) {
    if (s->top - s->base == s->stacksize) {
        return 1; // 栈已满
    } else {
        return 0; // 栈未满
    }
}

顺序栈入栈函数：

void Push(Stack s, int e) {
    if (Full(s)) {
        // 栈已满，扩展栈空间
        s->base = (int*)malloc((STACK_SIZE + STACK) * sizeof(int));
        if (!s->base) {
            exit(0);
        }
        s->top = s->base + s->stacksize;
        s->stacksize += STACK;
    }
    *s->top++ = e;
}

顺序栈出栈函数：

int pop(Stack s) {
    if (s->top == s->base) {
        return 0; // 栈为空，无法出栈
    } else {
        return *(--s->top); // 出栈元素并移动栈顶指针
    }
}

访问栈顶函数：

int GetTop(Stack s) {
    if (s->top == s->base) {
        return 0; // 栈为空，栈顶无元素
    } else {
        return *(s->top - 1); // 获取栈顶元素
    }
}

销毁栈函数：

void DestroyStack(Stack s) {
    free(s->base);
    free(s);
}

主函数实现：

int main() {
    Stack s = NULL;
    s = initStack(s);
    int i;
    for (i = 0; i < 5; i++) {
        Push(s, i);
    }
    for (i = 0; i < 5; i++) {
        printf("此时的栈顶为：%d\n", GetTop(s));
        printf("此时出栈的是：%d\n", pop(s));
    }
    DestroyStack(s);
    return 0;
}

通过上述代码，我们可以清晰地看到顺序栈的实现过程。每个函数都设计得很明确，能够有效地完成栈的操作。从初始化栈到入栈、出栈以及销毁栈，每一步都进行了细致的处理，确保程序能够稳定运行。