C语言数据结构之栈与队列怎么相互实现

在C语言中，栈（Stack）和队列（Queue）是两种常见的数据结构，它们分别遵循“后进先出”（LIFO）和“先进先出”（FIFO）的原则。虽然它们在操作方式上有所不同，但通过巧妙的设计，我们可以利用栈来实现队列，或者利用队列来实现栈。本文将详细介绍如何用栈实现队列，以及如何用队列实现栈。

1. 用栈实现队列

1.1 基本思路

队列的特点是先进先出，而栈的特点是后进先出。为了用栈实现队列，我们需要使用两个栈来模拟队列的行为。具体思路如下：

1. 入队操作：将元素压入第一个栈（称为“输入栈”）。
2. 出队操作：如果第二个栈（称为“输出栈”）为空，则将输入栈中的所有元素依次弹出并压入输出栈。然后从输出栈中弹出栈顶元素，即为队列的队首元素。

1.2 代码实现

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->data[++s->top] = value;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1;
    }
    return s->data[s->top--];
}

typedef struct {
    Stack input;
    Stack output;
} Queue;

void initQueue(Queue *q) {
    initStack(&q->input);
    initStack(&q->output);
}

void enqueue(Queue *q, int value) {
    push(&q->input, value);
}

int dequeue(Queue *q) {
    if (isEmpty(&q->output)) {
        while (!isEmpty(&q->input)) {
            push(&q->output, pop(&q->input));
        }
    }
    return pop(&q->output);
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);

    printf("%d\n", dequeue(&q)); // 输出 1
    printf("%d\n", dequeue(&q)); // 输出 2
    printf("%d\n", dequeue(&q)); // 输出 3

    return 0;
}

1.3 分析

• 时间复杂度：入队操作的时间复杂度为O(1)，出队操作的时间复杂度在最好情况下为O(1)，最坏情况下为O(n)（当输出栈为空时，需要将输入栈中的所有元素移动到输出栈）。
• 空间复杂度：使用了两个栈，空间复杂度为O(n)。

2. 用队列实现栈

2.1 基本思路

栈的特点是后进先出，而队列的特点是先进先出。为了用队列实现栈，我们需要使用两个队列来模拟栈的行为。具体思路如下：

1. 入栈操作：将元素加入非空队列。
2. 出栈操作：将非空队列中的元素依次出队并加入另一个队列，直到只剩下一个元素，该元素即为栈顶元素，将其出队。

2.2 代码实现

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

void initQueue(Queue *q) {
    q->front = q->rear = -1;
}

int isEmpty(Queue *q) {
    return q->front == -1;
}

int isFull(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue overflow\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = q->rear = 0;
    } else {
        q->rear = (q->rear + 1) % MAX_SIZE;
    }
    q->data[q->rear] = value;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue underflow\n");
        return -1;
    }
    int value = q->data[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX_SIZE;
    }
    return value;
}

typedef struct {
    Queue q1;
    Queue q2;
} Stack;

void initStack(Stack *s) {
    initQueue(&s->q1);
    initQueue(&s->q2);
}

void push(Stack *s, int value) {
    if (!isEmpty(&s->q1)) {
        enqueue(&s->q1, value);
    } else {
        enqueue(&s->q2, value);
    }
}

int pop(Stack *s) {
    Queue *nonEmptyQueue = isEmpty(&s->q1) ? &s->q2 : &s->q1;
    Queue *emptyQueue = isEmpty(&s->q1) ? &s->q1 : &s->q2;

    while ((nonEmptyQueue->front + 1) % MAX_SIZE != nonEmptyQueue->rear) {
        enqueue(emptyQueue, dequeue(nonEmptyQueue));
    }
    return dequeue(nonEmptyQueue);
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 1);
    push(&s, 2);
    push(&s, 3);

    printf("%d\n", pop(&s)); // 输出 3
    printf("%d\n", pop(&s)); // 输出 2
    printf("%d\n", pop(&s)); // 输出 1

    return 0;
}

2.3 分析

• 时间复杂度：入栈操作的时间复杂度为O(1)，出栈操作的时间复杂度为O(n)（需要将队列中的元素逐个移动到另一个队列）。
• 空间复杂度：使用了两个队列，空间复杂度为O(n)。

3. 总结

通过上述实现，我们可以看到，栈和队列虽然是两种不同的数据结构，但它们之间可以通过相互模拟来实现对方的功能。用栈实现队列的关键在于使用两个栈来分别处理入队和出队操作，而用队列实现栈的关键在于使用两个队列来模拟栈的后进先出特性。

在实际应用中，选择哪种实现方式取决于具体的需求和场景。例如，如果对出队操作的性能要求较高，可以选择用栈实现队列；如果对出栈操作的性能要求较高，可以选择用队列实现栈。

希望本文能帮助你更好地理解栈和队列的相互实现方式，并在实际编程中灵活运用。