舞伴问题链队列和链栈具体代码

舞伴问题链队列和链栈都是数据结构的一种实现，它们通常用于模拟特定场景下的操作。这里以C语言为例，我会简单地描述一下它们的基本概念以及简单的链式版本实现。

**链队列（Linked Queue）**: 链队列是一种先进先出（FIFO）的数据结构，它类似于日常生活中排队的情况。我们有一个指向头节点的指针`front`和一个指向尾节点的指针`rear`。添加元素（入队）时，新节点会连接到尾部；删除元素（出队）时，从头部开始遍历直到找到第一个节点并移除。

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

struct Queue {
    Node* front;
    Node* rear;
};

// 入队
void enqueue(Queue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队
int dequeue(Queue* q) {
    if (q->front == NULL) {
        return -1; // 空队列
    }
    int value = q->front->data;
    Node* temp = q->front;
    q->front = q->front->next;
    free(temp); // 释放内存
    if (q->front == NULL) {
        q->rear = NULL;
    }
    return value;
}

**链栈（Linked Stack）**: 链栈则是一种后进先出（LIFO）的数据结构，就像是一叠盘子，最后放入的会被最先拿走。这里只有一个指针`top`表示栈顶，所有的插入和删除都发生在这个位置上。

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

struct Stack {
    Node* top;
};

// 入栈
void push(Stack* s, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

// 出栈
int pop(Stack* s) {
    if (s->top == NULL) {
        return -1; // 空栈
    }
    int value = s->top->data;
    Node* temp = s->top;
    s->top = s->top->next;
    free(temp);
    return value;
}