1. 顺序栈（数组实现）

sqstack.h 头文件定义

typedef int elem_type;

typedef struct {
    elem_type *arr;      // 存储数据的连续内存
    int capacity;        // 栈最大容量
    int stack_ptr;       // 栈顶指针索引
} SeqStack;

SeqStack* create_stack(int size);
int push_to_stack(SeqStack *stk, elem_type val);
int is_stack_empty(SeqStack *stk);
int is_stack_full(SeqStack *stk);
elem_type pop_from_stack(SeqStack *stk);
elem_type peek_stack_top(SeqStack *stk);
int reset_stack(SeqStack *stk);
int display_stack(SeqStack *stk);
int destroy_stack(SeqStack *stk);

sqstack.c 核心实现

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

SeqStack* create_stack(int size) {
    SeqStack *stk = (SeqStack*)malloc(sizeof(SeqStack));
    if (!stk) {
        printf("Memory allocation for stack failed\n");
        return NULL;
    }

    elem_type *buffer = (elem_type*)malloc(size * sizeof(elem_type));
    if (!buffer) {
        printf("Memory allocation for data buffer failed\n");
        free(stk);
        return NULL;
    }

    memset(buffer, 0, size * sizeof(elem_type));
    stk->arr = buffer;
    stk->capacity = size;
    stk->stack_ptr = -1;  // 空栈标识
    return stk;
}

int push_to_stack(SeqStack *stk, elem_type val) {
    if (!stk) {
        printf("Stack pointer is NULL\n");
        return -1;
    }
    if (stk->stack_ptr == stk->capacity - 1) {
        printf("Stack overflow - cannot push\n");
        return -1;
    }
    stk->stack_ptr++;
    stk->arr[stk->stack_ptr] = val;
    return 0;
}

int is_stack_empty(SeqStack *stk) {
    if (!stk) return -1;
    return (stk->stack_ptr == -1) ? 1 : 0;
}

int is_stack_full(SeqStack *stk) {
    if (!stk) return -1;
    return (stk->stack_ptr == stk->capacity - 1) ? 1 : 0;
}

elem_type pop_from_stack(SeqStack *stk) {
    if (!stk || is_stack_empty(stk)) {
        printf("Cannot pop from empty stack\n");
        return -1;
    }
    elem_type value = stk->arr[stk->stack_ptr];
    stk->stack_ptr--;
    return value;
}

elem_type peek_stack_top(SeqStack *stk) {
    if (!stk || is_stack_empty(stk)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stk->arr[stk->stack_ptr];
}

int reset_stack(SeqStack *stk) {
    if (!stk) return -1;
    stk->stack_ptr = -1;
    return 0;
}

int display_stack(SeqStack *stk) {
    if (!stk) return -1;
    for (int i = 0; i <= stk->stack_ptr; i++) {
        printf("%d ", stk->arr[i]);
    }
    printf("\n");
    return 0;
}

int destroy_stack(SeqStack *stk) {
    if (!stk) return -1;
    if (stk->arr) {
        free(stk->arr);
    }
    free(stk);
    return 0;
}

测试用例 test.c

#include <stdio.h>
#include "sqstack.h"

int main() {
    SeqStack *my_stack = create_stack(10);
    push_to_stack(my_stack, 100);
    push_to_stack(my_stack, 200);
    push_to_stack(my_stack, 300);
    
    display_stack(my_stack);
    printf("Current top element: %d\n", peek_stack_top(my_stack));
    
    while (!is_stack_empty(my_stack)) {
        printf("Popped: %d\n", pop_from_stack(my_stack));
    }
    
    destroy_stack(my_stack);
    return 0;
}

2. 链式栈（链表实现）

linkstack.h 头文件定义

typedef int elem_type;

typedef struct StackNode {
    elem_type value;
    struct StackNode *next;
} LinkedStack;

LinkedStack* init_stack(void);
int insert_to_stack(LinkedStack *stk, elem_type val);
int check_if_empty(LinkedStack *stk);
elem_type remove_from_stack(LinkedStack *stk);
elem_type get_stack_top(LinkedStack *stk);
int print_stack_elements(LinkedStack *stk);
int release_stack(LinkedStack *stk);

linkstack.c 核心实现

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

LinkedStack* init_stack() {
    LinkedStack *head = (LinkedStack*)malloc(sizeof(LinkedStack));
    if (!head) {
        printf("Failed to create head node\n");
        return NULL;
    }
    head->value = 0;
    head->next = NULL;
    return head;
}

int insert_to_stack(LinkedStack *stk, elem_type val) {
    if (!stk) return -1;
    
    LinkedStack *node = (LinkedStack*)malloc(sizeof(LinkedStack));
    if (!node) return -1;
    
    node->value = val;
    node->next = stk->next;  // 头插法入栈
    stk->next = node;
    return 0;
}

int check_if_empty(LinkedStack *stk) {
    if (!stk) return -1;
    return (stk->next == NULL) ? 1 : 0;
}

elem_type remove_from_stack(LinkedStack *stk) {
    if (!stk || check_if_empty(stk)) {
        printf("Stack underflow\n");
        return -1;
    }
    
    LinkedStack *temp = stk->next;
    elem_type value = temp->value;
    stk->next = temp->next;
    free(temp);
    return value;
}

elem_type get_stack_top(LinkedStack *stk) {
    if (!stk || check_if_empty(stk)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stk->next->value;
}

int print_stack_elements(LinkedStack *stk) {
    if (!stk) return -1;
    
    LinkedStack *curr = stk;
    while (curr->next) {
        printf("%d ", curr->next->value);
        curr = curr->next;
    }
    printf("\n");
    return 0;
}

int release_stack(LinkedStack *stk) {
    if (!stk) return -1;
    
    LinkedStack *curr = stk;
    LinkedStack *next_node;
    while (curr) {
        next_node = curr->next;
        printf("Freeing node with value: %d\n", curr->value);
        free(curr);
        curr = next_node;
    }
    return 0;
}

测试用例 test.c

#include <stdio.h>
#include "linkstack.h"

int main() {
    LinkedStack *stack = init_stack();
    insert_to_stack(stack, 10);
    insert_to_stack(stack, 20);
    insert_to_stack(stack, 30);
    
    print_stack_elements(stack);
    printf("Top element: %d\n", get_stack_top(stack));
    
    while (!check_if_empty(stack)) {
        printf("Popped: %d\n", remove_from_stack(stack));
    }
    
    release_stack(stack);
    return 0;
}

关键概念解析

• 后进先出（LIFO）：栈的核心特性是后插入的元素先被取出，就像叠盘子一样。
• 顺序实现：使用固定大小的数组，操作简单但容量受限，适合元素数量可预测的场景。
• 链式实现：通过动态内存分配管理节点，空间利用灵活，但每个节点需要额外保存指针。
• 时间复杂度：两种实现的入栈和出栈操作均为 O(1)，但链式栈的节点分配可能带来额外开销。