C语言详解如何实现顺序栈

当我们需要实现一个顺序栈时，需要先定义栈结构体，然后实现栈的基本操作，包括入栈、出栈等。以下为具体步骤：

1. 定义栈结构体

定义一个结构体，包含栈的基本属性：

typedef struct SeqStack {
    int *data;      // 栈的元素存储空间
    int size;       // 栈的大小
    int top;        // 栈顶指针
} SeqStack;

其中，data是指向栈元素存储空间的指针，size是栈的大小（即最多可以存储的元素个数），top是栈顶指针，指向最后一个入栈的元素。

2. 初始化栈

对于一个空栈，需要进行初始化操作，即给栈分配空间，并将栈顶指针置为-1。

void initSeqStack(SeqStack *s, int size)
{
    s->data = (int*) malloc(sizeof(int) * size);
    s->size = size;
    s->top = -1;
}

3. 判断栈是否为空

可以通过判断栈顶指针是否等于-1来判断栈是否为空。

int isSeqStackEmpty(SeqStack *s)
{
    return s->top == -1;
}

4. 判断栈是否已满

可以通过判断栈顶指针是否等于栈的大小减1来判断栈是否已满。

int isSeqStackFull(SeqStack *s)
{
    return s->top == s->size - 1;
}

5. 入栈操作

当栈不为空且未满时，可以进行入栈操作，即将元素压入栈顶，并将栈顶指针加一。

void pushSeqStack(SeqStack *s, int x)
{
    if (!isSeqStackFull(s)) {
        s->top++;
        s->data[s->top] = x;
    } else {
        printf("ERROR: Stack overflow!\n");
    }
}

6. 出栈操作

当栈不为空时，可以进行出栈操作，即将栈顶元素弹出，并将栈顶指针减一。

int popSeqStack(SeqStack *s)
{
    if (!isSeqStackEmpty(s)) {
        int x = s->data[s->top];
        s->top--;
        return x;
    } else {
        printf("ERROR: Stack underflow!\n");
        return -1;
    }
}

示例一

以下代码为一个示例程序，实现了对顺序栈的基本操作：

#include <stdio.h>
#include <stdlib.h>

#define STACK_SIZE 5

typedef struct SeqStack {
    int *data;      // 栈的元素存储空间
    int size;       // 栈的大小
    int top;        // 栈顶指针
} SeqStack;

// 初始化栈
void initSeqStack(SeqStack *s, int size)
{
    s->data = (int*) malloc(sizeof(int) * size);
    s->size = size;
    s->top = -1;
}

// 判断栈是否为空
int isSeqStackEmpty(SeqStack *s)
{
    return s->top == -1;
}

// 判断栈是否已满
int isSeqStackFull(SeqStack *s)
{
    return s->top == s->size - 1;
}

// 入栈操作
void pushSeqStack(SeqStack *s, int x)
{
    if (!isSeqStackFull(s)) {
        s->top++;
        s->data[s->top] = x;
    } else {
        printf("ERROR: Stack overflow!\n");
    }
}

// 出栈操作
int popSeqStack(SeqStack *s)
{
    if (!isSeqStackEmpty(s)) {
        int x = s->data[s->top];
        s->top--;
        return x;
    } else {
        printf("ERROR: Stack underflow!\n");
        return -1;
    }
}

int main()
{
    SeqStack s;
    initSeqStack(&s, STACK_SIZE);

    pushSeqStack(&s, 1);
    pushSeqStack(&s, 2);
    pushSeqStack(&s, 3);
    printf("%d\n", popSeqStack(&s));        // output: 3
    printf("%d\n", popSeqStack(&s));        // output: 2
    pushSeqStack(&s, 4);
    pushSeqStack(&s, 5);
    pushSeqStack(&s, 6);            // output: ERROR: Stack overflow!
    printf("%d\n", popSeqStack(&s));        // output: 5
    printf("%d\n", popSeqStack(&s));        // output: 4
    printf("%d\n", popSeqStack(&s));        // output: 1
    printf("%d\n", popSeqStack(&s));        // output: ERROR: Stack underflow!

    return 0;
}

示例二

以下代码为一个示例程序，利用栈实现字符串的反转：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define STACK_SIZE 100

typedef struct SeqStack {
    char *data;     // 栈的元素存储空间
    int size;       // 栈的大小
    int top;        // 栈顶指针
} SeqStack;

// 初始化栈
void initSeqStack(SeqStack *s, int size)
{
    s->data = (char*) malloc(sizeof(char) * size);
    s->size = size;
    s->top = -1;
}

// 判断栈是否为空
int isSeqStackEmpty(SeqStack *s)
{
    return s->top == -1;
}

// 判断栈是否已满
int isSeqStackFull(SeqStack *s)
{
    return s->top == s->size - 1;
}

// 入栈操作
void pushSeqStack(SeqStack *s, char x)
{
    if (!isSeqStackFull(s)) {
        s->top++;
        s->data[s->top] = x;
    } else {
        printf("ERROR: Stack overflow!\n");
    }
}

// 出栈操作
char popSeqStack(SeqStack *s)
{
    if (!isSeqStackEmpty(s)) {
        char x = s->data[s->top];
        s->top--;
        return x;
    } else {
        printf("ERROR: Stack underflow!\n");
        return '\0';
    }
}

int main()
{
    SeqStack s;
    initSeqStack(&s, STACK_SIZE);

    char str[] = "Hello, world!";
    int len = strlen(str);

    // 将字符串中的每个字符入栈
    for (int i = 0; i < len; i++) {
        pushSeqStack(&s, str[i]);
    }

    // 出栈并输出
    while (!isSeqStackEmpty(&s)) {
        printf("%c", popSeqStack(&s));
    }
    printf("\n");

    return 0;
}

运行上述程序，输出为：!dlrow ,olleH，即字符串被成功反转。