C语言用两个栈实现队列

在C语言中，可以利用两个栈（stack）来实现队列（queue），这是因为栈只允许在一端进行插入（push）和删除（pop）。通过这种方式，我们可以在第一个栈（先进先出栈，通常称为A栈）中入队，而在第二个栈（后进先出栈，称为B栈）中出队。当需要出队时，我们将B栈顶的元素弹出并压回A栈，这样新的元素就自然地出现在了A栈顶，实现了队列的操作。

以下是具体的实现过程：

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

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

// 创建一个新节点
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// 使用的第一个栈（先进先出）
void push_A(Node** top, int data) {
    Node* new_node = newNode(data);
    if (*top == NULL) {
        *top = new_node;
    } else {
        new_node->next = *top;
        *top = new_node;
    }
}

// 使用的第二个栈（后进先出）
void push_B(Node** bottom, int data) {
    Node* new_node = newNode(data);
    if (*bottom == NULL) {
        *bottom = new_node;
    } else {
        new_node->next = *bottom;
        *bottom = new_node;
    }
}

// 从B栈出队并在A栈入队
void enqueue(Node** A, Node** B) {
    if (*B != NULL) {
        Node* temp = *B;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        push_A(A, temp->data);
        free(temp);
    }
}

// 从A栈出队
int dequeue(Node** top) {
    if (*top == NULL) {
        printf("Queue is empty\n");
        return -1;
    } else {
        int data = (*top)->data;
        Node* temp = *top;
        *top = (*top)->next;
        free(temp);
        return data;
    }
}

// 主函数测试
int main() {
    Node* A_top = NULL, *A_bottom = NULL;
    Node* B_top = NULL, *B_bottom = NULL;

    enqueue(&A_top, &B_top, 1);
    enqueue(&A_top, &B_top, 2);
    enqueue(&A_top, &B_top, 3);

    printf("Enqueued items: ");
    while (dequeue(&A_top) != -1) {
        printf("%d ", dequeue(&A_top));
    }

    enqueue(&A_top, &B_top, 4); // 增加一个元素到B栈

    printf("\nDequeue from front: %d", dequeue(&A_top));

    enqueue(&A_top, &B_top, 5); // 再次添加元素，证明队列特性

    return 0;
}

这个实现中，`enqueue` 函数用于将元素添加到队列的末尾，而 `dequeue` 函数用于从队列的前端（实际上是A栈顶）取出元素。注意，为了保持A栈始终是先进先出，我们在B栈出队后立即把数据推到A栈。这样，每次从A栈出队实际上就是从队列前端取元素。