堆栈链式存储表示及实现

堆栈是一种先进后出（Last In First Out，LIFO）的数据结构，可以使用链式存储方式实现。链式存储方式可以使用单链表或双向链表来表示堆栈，具体实现如下：

1. 单链表实现堆栈：

定义一个节点结构体，包含数据域和指向下一个节点的指针域。定义一个栈结构体，包含一个指向栈顶节点的指针。

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

typedef struct Stack {
    Node* top;
} Stack;

入栈操作时，新建一个节点，将数据存入节点的数据域中，将该节点插入到链表的首部，同时更新栈顶指针。

void push(Stack* s, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = s->top;
    s->top = new_node;
}

出栈操作时，将栈顶节点从链表中删除，并返回该节点的数据域，同时更新栈顶指针。

int pop(Stack* s) {
    if (s->top == NULL) {
        printf("Stack is empty.\n");
        return -1;
    }
    Node* temp = s->top;
    int data = temp->data;
    s->top = temp->next;
    free(temp);
    return data;
}

2. 双向链表实现堆栈：

定义一个节点结构体，包含数据域、指向前一个节点的指针域和指向后一个节点的指针域。定义一个栈结构体，包含一个指向栈顶节点的指针和一个指向栈底节点的指针。

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

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

入栈操作时，新建一个节点，将数据存入节点的数据域中，将该节点插入到链表的末尾，同时更新栈顶指针和栈底指针。

void push(Stack* s, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->prev = s->top;
    new_node->next = NULL;
    if (s->top == NULL) {
        s->top = new_node;
        s->bottom = new_node;
    } else {
        s->top->next = new_node;
        s->top = new_node;
    }
}

出栈操作时，将栈顶节点从链表中删除，并返回该节点的数据域，同时更新栈顶指针和栈底指针。

int pop(Stack* s) {
    if (s->top == NULL) {
        printf("Stack is empty.\n");
        return -1;
    }
    Node* temp = s->top;
    int data = temp->data;
    s->top = temp->prev;
    if (s->top == NULL) {
        s->bottom = NULL;
    } else {
        s->top->next = NULL;
    }
    free(temp);
    return data;
}