C语言实现通用数据结构之通用椎栈

概述

通用椎栈（Generic Linked List Stack），简称GLL Stack，是一种通用的数据结构，能够以动态的方式存储和访问任意类型的数据。GLL Stack 采用链表实现，可以进行进栈（push）、出栈（pop）、查看栈顶元素（peek）、判断栈是否为空（isEmpty）等基本操作。

基本操作

数据结构定义

首先，我们需要定义一个通用的数据结构来存储数据：

typedef struct {
    void *data;
    struct gll_node *next;
} gll_node;

这是通用椎栈链表的节点类型，其中 data 存储了实际的数据，next 指向下一个节点。

typedef struct {
    gll_node *top;
} gll_stack;

这是通用椎栈的定义，其中 top 指向栈顶节点。

进栈（push）

新元素进栈时，需要动态的为其分配内存，并将其插入到栈顶。

void push(gll_stack *stack, void *data) {
    // 分配空间
    gll_node *new_node = (gll_node*) malloc(sizeof(gll_node));
    new_node->data = data;
    // 入栈
    new_node->next = stack->top;
    stack->top = new_node;
}

出栈（pop）

将栈顶元素出栈时，需要从链表中删除该节点，并释放空间。

void *pop(gll_stack *stack) {
    if (isEmpty(stack)) return NULL;
    // 出栈
    gll_node *popped_node = stack->top;
    void *data = popped_node->data;
    stack->top = popped_node->next;
    // 释放空间
    free(popped_node);
    return data;
}

查看栈顶元素（peek）

查看栈顶元素时，只需要返回栈顶节点的数据部分。

void *peek(gll_stack *stack) {
    if (isEmpty(stack)) return NULL;
    return stack->top->data;
}

判断栈是否为空（isEmpty）

判断栈是否为空时，只需检查栈顶指针是否为NULL。

int isEmpty(gll_stack *stack) {
    return (stack->top == NULL);
}

示例

示例1：使用GLL栈实现字符串反转

初始时将字符串中的每个字符依次进栈，最后再将字符依次出栈即可得到反转后的字符串。

#include <stdio.h>
#include <string.h>
#include "gll_stack.h"  // 通用椎栈定义及操作

#define MAX_LEN 100

int main() {
    char str[MAX_LEN];
    printf("请输入一个字符串：");
    scanf("%s", str);

    int len = strlen(str);

    // 字符串依次进栈
    gll_stack stack;
    stack.top = NULL;
    for (int i = 0; i < len; i++) {
        push(&stack, (void*) &str[i]);
    }

    // 字符串出栈
    char reversed_str[MAX_LEN];
    for (int i = 0; i < len; i++) {
        reversed_str[i] = *((char*) pop(&stack)); // 注意要强制类型转换
    }
    reversed_str[len] = '\0';

    printf("反转后的字符串为：%s\n", reversed_str);

    return 0;
}

示例2：使用GLL栈实现十进制数转二进制数

将十进制数依次压入GLL栈，然后依次出栈，并将每个出栈的数字转换为二进制数的一位。最后将所有位拼接起来，即为转换后的二进制数。

#include <stdio.h>
#include "gll_stack.h"  // 通用椎栈定义及操作

int main() {
    int num;
    printf("请输入一个十进制整数：");
    scanf("%d", &num);

    // 转换为二进制数
    gll_stack stack;
    stack.top = NULL;
    while (num != 0) {
        push(&stack, (void*) (num % 2));
        num /= 2;
    }

    // 拼接字符串
    char binary_str[100];
    int i = 0;
    while (!isEmpty(&stack)) {
        int bit = *((int*) pop(&stack));  // 注意要强制类型转换
        binary_str[i] = bit + '0';  // 转换为字符形式
        i++;
    }
    binary_str[i] = '\0';

    printf("转换为二进制数为：%s\n", binary_str);

    return 0;
}

总结

通过实现以上基本操作，我们可以使用GLL Stack 存储和访问任意类型的数据，并使用栈的特性来实现各种业务逻辑。