数据结构 定义栈的存储结构（顺序栈或者链栈均可）算法代码 c语言

栈是一种线性数据结构，它遵循“先进后出”（Last In First Out, LIFO）的原则，常用于函数调用、表达式求值等场景。这里有两种常见的栈实现方式，分别是顺序栈和链栈。

**顺序栈（基于数组）**:
在C语言中，可以使用数组来实现顺序栈。数组栈的特点是空间连续，插入和删除操作的时间复杂度为O(1)，但如果接近栈顶，需要移动大量元素才能继续添加或移除元素。

typedef struct {
    int* stack; // 存储数据的数组
    int top; // 栈顶指针
    int size; // 栈的最大容量
} Stack;

// 初始化栈
void init(Stack* s, int capacity) {
    s->stack = (int*)malloc(capacity * sizeof(int));
    s->top = -1;
    s->size = capacity;
}

// 入栈
void push(Stack* s, int value) {
    if (s- 1) {
        s->stack[++s->top] = value;
    } else {
        printf("Stack overflow\n");
    }
}

// 出栈
int pop(Stack* s) {
    if (s->top >= 0) {
        return s->stack[s->top--];
    } else {
        printf("Stack underflow\n");
        return -1; // 返回特殊值表示空栈
    }
}

**链栈（基于链表）**:
链栈则利用链表节点，每个节点包含数据和指向下一个节点的指针，操作更灵活，不需要预先分配固定大小的空间，但是插入和删除操作的时间复杂度通常为O(1)。

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* top;
    Node* bottom;
} LinkStack;

// 初始化链栈
void link_init(LinkStack* s) {
    s->top = s->bottom = NULL;
}

// 入栈
void link_push(LinkStack* s, int value) {
    Node* newNode = malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
    if (!s->bottom)
        s->bottom = newNode;
}

// 出栈
int link_pop(LinkStack* s) {
    if (s->top) {
        int data = s->top->data;
        Node* temp = s->top;
        s->top = s->top->next;
        free(temp);
        if (!s->top)
            s->bottom = NULL;
        return data;
    } else {
        printf("Stack empty\n");
        return -1;
    }
}