数据结构：单向链表，顺序栈和链式栈

2.3 核心特性

• 连续存储：数据在内存中连续存放
• 大小固定：静态实现有固定上限，动态实现可扩容
• 操作受限：仅允许在栈顶进行插入和删除
• 高效访问：通过数组下标直接访问，缓存友好

2.4 关键操作实现

// 初始化动态顺序栈
DynamicSeqStack* InitDynamicStack(int initCapacity) {
    DynamicSeqStack *stack = (DynamicSeqStack*)malloc(sizeof(DynamicSeqStack));
    stack->data = (int*)malloc(initCapacity * sizeof(int));
    stack->top = -1;
    stack->capacity = initCapacity;
    return stack;
}

// 入栈操作
int Push(DynamicSeqStack *stack, int value) {
    if (stack->top == stack->capacity - 1) {
        // 栈满，需要扩容
        int newCapacity = stack->capacity * 2;
        int *newData = (int*)realloc(stack->data, newCapacity * sizeof(int));
        if (!newData) return 0;
        stack->data = newData;
        stack->capacity = newCapacity;
    }
    stack->data[++stack->top] = value;
    return 1;
}

// 出栈操作
int Pop(DynamicSeqStack *stack) {
    if (stack->top == -1) {
        // 栈空处理
        return INT_MIN;
    }
    return stack->data[stack->top--];
}

三、链式栈（Linked Stack）

3.1 基本定义

链式栈基于链表实现栈结构，具备链表的动态特性与栈的操作限制。其设计存在两种主要模式：单结构体头节点法和双结构体封装法。

3.2 设计模式一：单结构体头节点法

该方法采用单一节点结构，使用头节点作为栈的标识，栈顶位于头节点之后。

结构定义

// 单结构体定义
typedef struct StackNode {
    int data;           // 数据域
    struct StackNode *next; // 指针域
} StackNode;

// 栈节点同时也是栈标识

实现特点

• 头节点作为栈标识：头节点不存储有效数据，其 next 指针指向栈顶
• 统一节点类型：仅需一种结构体类型
• 头插法操作：入栈采用头插法，出栈删除头节点后继
• 函数参数简单：函数直接接收头节点指针

核心操作示例

// 创建空栈
StackNode* CreateStack() {
    StackNode *head = (StackNode*)malloc(sizeof(StackNode));
    head->next = NULL; // 空栈，头节点 next 为 NULL
    return head;
}

// 入栈操作
void Push(StackNode *head, int value) {
    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->data = value;
    newNode->next = head->next; // 新节点指向原栈顶
    head->next = newNode;       // 头节点指向新栈顶
}

// 出栈操作
int Pop(StackNode *head) {
    if (head->next == NULL) {
        return INT_MIN; // 栈空处理
    }
    StackNode *top = head->next;
    int value = top->data;
    head->next = top->next;
    free(top);
    return value;
}

3.3 设计模式二：双结构体封装法

该方法采用两个结构体，分别定义节点和栈管理结构，实现逻辑与数据分离。

结构定义

// 节点结构
typedef struct LinkedStackNode {
    int data;           // 数据域
    struct LinkedStackNode *next; // 指针域
} LinkedStackNode;

// 栈管理结构
typedef struct {
    LinkedStackNode *top; // 栈顶指针
    int size;             // 栈大小
} LinkedStack;

实现特点

• 逻辑与数据分离：栈管理结构与节点结构分离
• 状态信息明确：可维护栈大小等状态信息
• 无头节点开销：栈顶指针直接指向栈顶元素
• 面向对象思想：更符合现代编程封装理念

核心操作示例

// 创建空栈
LinkedStack* CreateLinkedStack() {
    LinkedStack *stack = (LinkedStack*)malloc(sizeof(LinkedStack));
    stack->top = NULL;
    stack->size = 0;
    return stack;
}

// 入栈操作
void PushLinkedStack(LinkedStack *stack, int value) {
    LinkedStackNode *newNode = (LinkedStackNode*)malloc(sizeof(LinkedStackNode));
    newNode->data = value;
    newNode->next = stack->top; // 新节点指向原栈顶
    stack->top = newNode;       // 更新栈顶指针
    stack->size++;              // 更新栈大小
}

// 出栈操作
int PopLinkedStack(LinkedStack *stack) {
    if (stack->top == NULL) {
        return INT_MIN; // 栈空处理
    }
    LinkedStackNode *topNode = stack->top;
    int value = topNode->data;
    stack->top = topNode->next; // 更新栈顶指针
    free(topNode);
    stack->size--;              // 更新栈大小
    return value;
}

3.4 两种设计模式对比

四、三项结构综合对比

4.1 存储结构对比

4.2 操作特性对比

4.3 性能指标对比

五、结论

单向链表、顺序栈和链式栈代表了三种不同的线性数据组织策略。单向链表强调操作灵活性，顺序栈注重访问效率，链式栈则结合了动态扩展与操作约束。

链式栈的两种设计模式体现了不同的工程权衡：单结构体头节点法以简洁性见长，双结构体封装法则以扩展性取胜。实际选择应基于具体需求，权衡性能、内存、扩展性和实现复杂度等因素。

在系统设计中，理解这些基础结构的本质特性及其实现差异，对于选择合适的数据结构、优化算法性能、构建稳定可靠的软件系统具有重要意义。每种结构都有其适用场景，优秀的系统设计者应根据具体约束条件做出合理选择，而非盲目追求某种结构的普遍适用性。