顺序栈

定义

概念

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

栈文档之顺序栈

结构体

/** * 顺序栈结构体定义 */
typedef struct {
     
       
    /** * 数据域，数组，用来存储栈中元素 */
    int data[MAXSIZE];
    /** * 指针域，表示栈顶指针，实际上就是数组下标 */
    int top;
} SeqStack;

特点

注意：

栈的判空条件和判满条件可能会跟实际设置不一样，下面是设置 top=-1 为初始化条件，所以判空条件是 top==-1。但有些资料中是将 top=0 作为初始条件，因此判空条件又不一样。

由于顺序栈的入栈操作受数组上界的约束，当栈的使用空间不够时，可能发生栈上溢，此时应该报出错误信息。

所谓的栈上溢就是当栈满后，再继续入栈就会发生上溢。

所谓的栈下溢就是当栈空后，再继续出栈就会发生下溢。

因为规定了 top==-1 表示栈空，所以元素进栈操作必须是先移动指针，再进入元素，因为数组下标不存在 -1。但有可能初始规定 top=0，那么就要元素先入栈，再将栈顶指针加一。其实本质都是一样的，根据实际情况来即可。

进栈操作次序决定了出栈操作次序，由于本文中进栈操作是先变动栈顶指针再存入元素，因此出栈操作必须是先取出元素，再变动指针。如果出栈打算先变动指针再取出元素，则会造成栈顶元素丢失，因为取出的是栈顶下边的元素。

用 top 表示栈顶指针，实际上就是数组下标。初始时（即初始化操作中，也就是空栈）设置 top=-1；而 stack.data[stack.top] 表示获取栈顶元素。
进栈操作，如果栈不满才能进栈，先将栈顶指针加一，再将值填充到栈顶的位置中。
出栈操作，如果栈不为空才能出栈，先取栈顶元素值，再将栈顶指针减一。
栈空条件：stack.top==-1。因为初始条件是 top=-1，并且 top 表示数组下标，不能为 -1，所以如果为 -1 了那么就表示是空栈。
栈满条件：stack.top=MAXSIZE-1。其中 MAXSIZE 是栈能存储的最大元素的个数，则 MAXSIZE-1 为栈满时栈顶元素在数组中的下标位置，因为数组下标是从 0 开始的。
栈长：stack.top+1。因为 top 表示数组下标，所以数组元素实际个数是下标加一。

基本操作

注，完整代码请参考：

SeqStack.c

SeqStack.java

SeqStackTest.java

概述

顺序栈的常见操作如下：

void init(SeqStack *stack)：初始化顺序栈，即将栈顶指针置为 -1 表示是空栈。其中 stack 表示未初始化的顺序栈。
int isEmpty(SeqStack stack)：判断顺序栈是否为空，如果为空则返回 1，否则返回 0。其中 stack 表示顺序栈。如果顺序栈为空则返回 1，否则返回 0。
int push(SeqStack *stack, int ele)：将元素进栈。其中 stack 表示顺序栈；ele 表示新元素。如果新元素入栈成功则返回 1，如果顺序栈已满则返回 0。
int pop(SeqStack *stack, int *ele)：将元素出栈。其中 stack 表示顺序栈；ele 用来保存出栈的元素。如果顺序栈为空则返回 0，如果顺序栈出栈元素成功则返回 1。
int getTop(SeqStack stack, int *ele)：获取栈顶元素，但不会将元素出栈。其中 stack 表示顺序栈；ele 用来存放栈顶元素。如果顺序栈为空则返回 0，如果得到顺序栈的栈顶元素则返回 1。
int size(SeqStack stack)：获取顺序栈中元素个数。其中 stack 表示顺序栈。
void print(SeqStack stack)：打印顺序栈中所有元素。其中 stack 表示顺序栈。
void clear(SeqStack *stack)：清空顺序栈中所有元素。

`init`

初始化栈，只需要将栈顶指针置为 -1 即可。

栈文档之顺序栈
实现步骤：

将栈顶指针 top 置为 -1 即可。

实现代码如下：

/** * 初始化顺序栈，即将栈顶指针指向 -1 表示空栈 * @param stack 顺序栈 */
void init(SeqStack *stack) {
     
       
    // 设定让栈顶指针指向 -1 表示为栈空
    stack->top = -1;
}

`isEmpty`

判断顺序栈是否为空，如果栈顶指针 top==-1 则表示栈空，否则非空。

栈文档之顺序栈

实现步骤：

即判断栈顶指针 top 是否等于 -1 即可。如果等于 -1 则表示空栈，否则不是。

实现代码如下：

/** * 判断顺序栈是否为空 * @param stack 顺序栈 * @return 如果顺序栈为空则返回 1，否则返回 0 */
int isEmpty(SeqStack stack) {
     
       
    // 只需要判断栈顶指针是否等于 -1 即可，如果是空栈则返回 1，不是空栈则返回 0
    if (stack.top == -1) {
     
       
        return 1;
    } else {
     
       
        return 0;
    }
}

`push`

将元素入栈。如果栈满则不能入栈则返回 0 表示入栈失败；否则将元素入栈，并返回 1 表示入栈成功。以 stack=[11, 22, 33]; ele=44 为例如图：

栈文档之顺序栈

实现步骤：

参数校验，判断是否栈满，如果栈满则不能入栈，返回 0 表示入栈失败。
先修改栈顶指针，将其加一。
再将新元素填充入栈顶指针所表示的位置中。
返回 1 表示入栈成功。

实现代码如下：

/** * 将元素入栈 * @param stack 顺序栈 * @param ele 元素值 * @return 如果栈满则返回 0 表示入栈失败；如果插入成功则返回 1 */
int push(SeqStack *stack, int ele) {
     
       
    // 1.参数校验，如果栈满则不能入栈元素
    if (stack->top == MAXSIZE - 1) {
     
       
        // 如果栈满，则返回 0，表示不能入栈
        return 0;
    }
    // 2.先将栈顶指针加一，指向新空数组位置
    stack->top++;
    // 3.将新元素值填充到新位置中
    stack->data[stack->top] = ele;
    return 1;
}

`pop`

将栈顶元素出栈，用 ele 保存出栈元素的值。以 stack=[11, 22, 33, 44] 为例如图所示：

栈文档之顺序栈

实现步骤：

参数校验，如果栈空则不能出栈，否则产生下溢。
用 ele 保存栈顶元素。
将栈顶指针减去一，表示删除掉栈顶元素。

实现代码如下：

/** * 将元素出栈 * @param stack 顺序栈 * @param ele 用来保存出栈的元素 * @return 如果栈空则返回 0 表示出栈失败；否则返回 1 表示出栈成功 */
int pop(SeqStack *stack, int *ele) {
     
       
    // 1.参数校验，栈空不能出栈
    if (stack->top == -1) {
     
       
        // 栈空，没有元素可出栈
        return 0;
    }
    // 2.用 ele 来保存顺序栈栈顶元素
    *ele = stack->data[stack->top];
    // 3.然后栈顶指针减一，表示出栈一个元素
    stack->top--;
    return 1;
}

`getTop`

取出栈顶元素，但并不出栈。以 stack=[11, 22, 33, 44] 为例如图：

栈文档之顺序栈

实现步骤：

参数校验，如果栈空则不能出栈。
直接取出栈顶元素，用 ele 保存。

实现代码如下：

/** * 获取栈顶元素，但不出栈 * @param stack 顺序栈 * @param ele 用来保存出栈元素 * @return 如果栈空则返回 0 表示出栈失败；否则返回 1 表示出栈成功 */
int getTop(SeqStack stack, int *ele) {
     
       
    // 1.参数校验，如果栈空则不能出栈
    if (stack.top == -1) {
     
       
        // 栈空，没有元素可出栈
        return 0;
    }
    // 2.保存栈顶元素返回
    *ele = stack.data[stack.top];
    return 1;
}

`size`

获取栈中元素个数。

栈文档之顺序栈

实现步骤：

返回栈顶指针加一即可，即使是空栈。

实现代码如下：

/** * 获取顺序栈中元素个数 * @param stack 顺序栈 * @return 顺序栈中元素个数 */
int size(SeqStack stack) {
     
       
    // top 表示栈顶指针，实际上就是数组 data 的下标，所以实际元素个数就是下标加一
    // 即使是空栈 top=-1，那么最后也会返回 0 表示元素个数为零个
    return stack.top + 1;
}

`print`

从栈顶到栈底打印顺序中所有元素。

栈文档之顺序栈

实现步骤：

从栈顶扫描到栈底所有元素。

实现代码如下：

/** * 打印顺序栈中所有元素 * @param stack 顺序栈 */
void print(SeqStack stack) {
     
       
    printf("[");
    for (int i = stack.top; i >= 0; i--) {
     
       
        if (i != stack.top) {
     
       
            printf(", ");
        }
        printf("%d", stack.data[i]);
    }
    printf("]\n");
}

`clear`

清空顺序栈。

实现步骤：

将栈顶指针指向 -1 即可。

实现代码如下：

/** * 清空顺序栈中所有元素 * @param stack 顺序栈 */
void clear(SeqStack *stack) {
     
       
    // 将栈顶指针指向 -1 即可，不需要重置一遍栈中元素
    stack->top = -1;
}

练习题

以下是一些顺序栈的练习题：

Example001-判断一个算术表达式中的括号是否正确配对
Example002-求后缀式的数值
Example004-顺序栈 s0 和 s1 共享一个存储区 elem，设计共享栈关于入栈和出栈操作的算法
Example005-检查一个程序中的花括号、方括号和圆括号是否配对
Example006-判定给定的由 I 和 O 组成的入栈和出栈组成的操作序列是否合法
Example007-利用栈判定单链表是否中心对称