【C语言】用栈实现队列篇

用户11456817

发布于 2025-02-15 13:17:16

4200

代码可运行

文章被收录于专栏：学习

运行总次数：0

代码可运行

一、数据结构基础回顾

1.1 栈（Stack）

特性：后进先出（LIFO）

核心操作：
- push: 元素入栈
- pop: 栈顶元素出栈
- peek: 查看栈顶元素

1.2 队列（Queue）

特性：先进先出（FIFO）

核心操作：
- enqueue: 元素入队
- dequeue: 队首元素出队
- front: 查看队首元素

二、问题分析与解决方案

2.1 核心矛盾

栈的LIFO特性与队列的FIFO需求存在根本性冲突，单个栈无法直接实现队列。

2.2 双栈方案

使用两个栈协同工作：

输入栈（input_stack）：专门处理入队操作
输出栈（output_stack）：专门处理出队操作

2.3 算法流程

// 入队操作
void enQueue(Queue* queue, int value) {
    push(&queue->input_stack, value);
}

// 出队操作
int deQueue(Queue* queue) {
    if (isStackEmpty(&queue->output_stack)) {
        // 当输出栈为空时，转移全部元素
        while (!isStackEmpty(&queue->input_stack)) {
            push(&queue->output_stack, pop(&queue->input_stack));
        }
    }
    return pop(&queue->output_stack);
}

三、完整实现代码

#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 isStackEmpty(Stack* s) {
    return s->top == -1;
}

// 判断栈满
int isStackFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈
void push(Stack* s, int val) {
    if (isStackFull(s)) {
        printf("Stack Overflow\n");
        exit(1);
    }
    s->data[++s->top] = val;
}

// 出栈
int pop(Stack* s) {
    if (isStackEmpty(s)) {
        printf("Stack Underflow\n");
        exit(1);
    }
    return s->data[s->top--];
}

// 队列结构体（包含两个栈）
typedef struct {
    Stack input_stack;
    Stack output_stack;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    initStack(&q->input_stack);
    initStack(&q->output_stack);
}

// 入队操作
void enQueue(Queue* q, int val) {
    if (isStackFull(&q->input_stack)) {
        printf("Queue is Full\n");
        return;
    }
    push(&q->input_stack, val);
}

// 出队操作
int deQueue(Queue* q) {
    if (isStackEmpty(&q->output_stack)) {
        if (isStackEmpty(&q->input_stack)) {
            printf("Queue is Empty\n");
            exit(1);
        }
        // 转移全部元素
        while (!isStackEmpty(&q->input_stack)) {
            push(&q->output_stack, pop(&q->input_stack));
        }
    }
    return pop(&q->output_stack);
}

// 获取队首元素
int queueFront(Queue* q) {
    if (isStackEmpty(&q->output_stack)) {
        while (!isStackEmpty(&q->input_stack)) {
            push(&q->output_stack, pop(&q->input_stack));
        }
    }
    return q->output_stack.data[q->output_stack.top];
}

// 判断队列是否为空
int isQueueEmpty(Queue* q) {
    return isStackEmpty(&q->input_stack) && isStackEmpty(&q->output_stack);
}

四、复杂度分析

4.1 时间复杂度

操作	时间复杂度	摊还复杂度
入队	O(1)	O(1)
出队	O(n)	O(1)

摊还分析：每个元素最多经历两次入栈和两次出栈操作，总体时间复杂度保持O(1)

4.2 空间复杂度

O(n)，需要维护两个栈的存储空间

五、测试与验证

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

    // 测试用例
    enQueue(&q, 1);
    enQueue(&q, 2);
    enQueue(&q, 3);

    printf("Dequeue: %d\n", deQueue(&q)); // 应输出1
    printf("Front: %d\n", queueFront(&q)); // 应输出2

    enQueue(&q, 4);
    
    printf("Dequeue: %d\n", deQueue(&q)); // 应输出2
    printf("Dequeue: %d\n", deQueue(&q)); // 应输出3
    printf("Dequeue: %d\n", deQueue(&q)); // 应输出4

    return 0;
}