C语言顺序栈完整实现：从定义到核心操作详解

顺序栈的逻辑定义

在数据结构中，栈是一种限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶（Top），另一端称为栈底（Bottom）。当栈中没有数据元素时，称为空栈。

顺序栈是指利用顺序存储结构实现的栈。通常使用一个一维数组作为栈的存储空间，并设一个整型变量 top 作为栈顶指针，指示当前栈顶元素在数组中的位置。其基本状态如下：

• 空栈状态：当 top == -1 时，表示栈为空。
• 栈满状态：当 top == MAXSIZE - 1 时，表示栈已满，无法再进行插入操作。

环境准备与基础定义

为了实现完整的顺序栈功能，首先需要定义相关的宏常量、类型别名以及核心结构体。这部分代码确立了栈的最大容量和数据元素的类型。

第1步：定义宏与类型别名

这一步用于统一状态返回值和数据类型，方便后续维护。例如将 int 定义为 Status 或 SElemType。

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

第2步：定义顺序栈结构体

结构体包含了存放数据的数组和指向栈顶的索引指针。注意，这里使用的是静态数组，若需动态内存管理可结合 malloc 使用。

/* 顺序栈结构 */
typedef struct
{
    SElemType data[MAXSIZE];
    int top; /* 用于栈顶指针 */
}SqStack;

核心操作实现细节

顺序栈的操作主要围绕栈顶指针 top 的变化展开。以下是各功能模块的具体实现代码。

第3步：初始化栈

构造一个空栈，关键是将栈顶指针初始化为 -1。

/* 构造一个空栈S */
Status InitStack(SqStack *S)
{ 
    S->top=-1;
    return OK;
}

第4步：清空栈

清空栈并不意味着释放内存，而是将栈重置为空的状态，即恢复 top 为 -1。

/* 把S置为空栈 */
Status ClearStack(SqStack *S)
{ 
    S->top=-1;
    return OK;
}

第5步：判断栈是否为空

检查 top 是否等于 -1，是则返回真。

/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
Status StackEmpty(SqStack S)
{ 
    if (S.top==-1)
        return TRUE;
    else
        return FALSE;
}

第6步：获取栈长度

由于数组下标从0开始，而栈内元素个数是从1计数，因此长度为 top + 1。

/* 返回S的元素个数，即栈的长度 */
int StackLength(SqStack S)
{ 
    return S.top+1;
}

第7步：获取栈顶元素

在不移动栈顶指针的前提下读取数据。需先判断栈是否为空，防止读取非法内存。

/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
Status GetTop(SqStack S, SElemType* e)
{
    if (S.top == -1) {
        return ERROR;
    }
    else {
        *e = S.data[S.top];
        return OK;
    }
}

第8步：入栈操作 (Push)

入栈前必须检查栈是否已满。若未满，先将栈顶指针加1，再存入新元素。

/* 插入元素e为新的栈顶元素 */
Status Push(SqStack* S, SElemType e)
{
    if (S->top == MAXSIZE - 1) /* 栈满 */
    {
        return ERROR;
    }
    S->top++;                 /* 栈顶指针增加一 */
    S->data[S->top] = e;      /* 将新插入元素赋值给栈顶空间 */
    return OK;
}

第9步：出栈操作 (Pop)

出栈前先判断栈是否为空。若非空，将栈顶元素值赋给输出变量，再将栈顶指针减1。

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqStack* S, SElemType* e)
{
    if (S->top == -1)
        return ERROR;
    *e = S->data[S->top];     /* 将要删除的栈顶元素赋值给e */
    S->top--;                 /* 栈顶指针减一 */
    return OK;
}

第10步：遍历栈元素

从栈底（下标0）到栈顶（下标 top）依次访问每个元素。

/* 从栈底到栈顶依次对栈中每个元素显示 */
Status StackTraverse(SqStack S)
{
    int i;
    i = 0;
    while (i <= S.top)
    {
        visit(S.data[i++]);
    }
    printf("\n");
    return OK;
}

Status visit(SElemType c)
{
    printf("%d ", c);
    return OK;
}

完整测试用例

以下 main 函数演示了上述操作的连贯执行流程：创建栈 -> 连续入栈 -> 遍历查看 -> 弹出栈顶 -> 获取当前栈顶及长度 -> 清空栈并再次检测空状态。

int main()
{
    int j;
    SqStack s;
    int e;
    
    // 1. 初始化栈
    if (InitStack(&s) == OK)
    {
        // 2. 循环入栈 1-10
        for (j = 1; j <= 10; j++)
            Push(&s, j);
    }
    
    printf("栈中元素依次为：");
    StackTraverse(s);
    
    // 3. 弹出栈顶元素
    Pop(&s, &e);
    printf("弹出的栈顶元素 e=%d\n", e);
    
    // 4. 判断栈空否
    printf("栈空否：%d(1:空 0:否)\n", StackEmpty(s));
    
    // 5. 获取当前栈顶和长度
    GetTop(s, &e);
    printf("栈顶元素 e=%d 栈的长度为%d\n", e, StackLength(s));
    
    // 6. 清空栈
    ClearStack(&s);
    printf("清空栈后，栈空否：%d(1:空 0:否)\n", StackEmpty(s));
    
    return 0;
}

以上就是C语言实现顺序栈及其基本操作的详细内容，更多关于C语言顺序栈算法的知识请关注本站其它相关文章！