C语言实现双栈模拟队列

在C语言中，由于标准库并不直接提供双端队列（Deque）的数据结构，我们可以使用两个栈来模拟一个队列的功能。这种设计利用了栈的特点，即后进先出（LIFO），通过将元素依次压入第一个栈（先进入队列），然后从第二个栈（最后出队）弹出元素，可以实现实体队列的基本操作，如入队、出队和查看队头。

下面是一个简单的示例：

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

typedef struct {
    int* stack1;
    int* stack2;
    int top1;
    int top2;
} Queue;

Queue* create_queue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->stack1 = (int*)malloc(10 * sizeof(int)); // 假设栈容量为10
    queue->stack2 = (int*)malloc(10 * sizeof(int));
    queue->top1 = -1;
    queue->top2 = -1;
    return queue;
}

void enqueue(Queue* queue, int value) {
    if (queue->top1 == 9) { // 如果栈1满了
        printf("Stack 1 is full, cannot enqueue.\n");
        return;
    }
    queue->stack1[++queue->top1] = value; // 入栈
}

int dequeue(Queue* queue) {
    if (queue->top2 == -1) { // 如果栈2为空
        while (queue->top1 != -1) {
            queue->stack2[queue->top2++] = queue->stack1[queue->top1--]; // 将栈1的元素移到栈2
        }
        if (queue->top1 == -1) { // 如果栈1也为空，说明队列已空
            printf("Queue is empty.\n");
            return -1;
        }
    }
    return queue->stack2[queue->top2--]; // 出栈并返回值
}

void display_queue(Queue* queue) {
    if (queue->top1 == -1) {
        printf("Queue is empty.\n");
    } else {
        for (int i = queue->top1; i >= 0; i--) {
            printf("%d ", queue->stack1[i]);
        }
        printf("\n");
    }
}

int main() {
    Queue* q = create_queue();
    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);
    display_queue(q); // 输出: 3 2 1
    printf("Dequeued element: %d\n", dequeue(q)); // 输出: Dequeued element: 1
    display_queue(q); // 输出: 2 3
    free(q->stack1);
    free(q->stack2);
    free(q);
    return 0;
}