LeetCode 232: 用栈实现队列

LeetCode 232: 用栈实现队列

题目描述

使用栈实现队列的操作。支持以下操作：

1. MyQueue()：初始化队列。
2. push(x)：将元素 x 推入队列。
3. pop()：从队列中移除元素。
4. peek()：返回队列头部的元素。
5. empty()：检查队列是否为空。

队列的先进先出（FIFO）原则可以通过两个栈来模拟。栈 A 用于入队操作，栈 B 用于出队操作。

C 语言实现

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

// 定义栈结构体
typedef struct {
    int* data;
    int top;
    int capacity;
} Stack;

// 初始化栈
Stack* stackCreate(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->data = (int*)malloc(sizeof(int) * capacity);
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

// 检查栈是否为空
int stackIsEmpty(Stack* stack) {
    return stack->top == -1;
}

// 入栈操作
void stackPush(Stack* stack, int x) {
    stack->data[++stack->top] = x;
}

// 出栈操作
int stackPop(Stack* stack) {
    return stack->data[stack->top--];
}

// 获取栈顶元素
int stackTop(Stack* stack) {
    return stack->data[stack->top];
}

// 释放栈内存
void stackFree(Stack* stack) {
    free(stack->data);
    free(stack);
}

// 定义队列结构体
typedef struct {
    Stack* stackA;
    Stack* stackB;
} MyQueue;

// 初始化队列
MyQueue* myQueueCreate() {
    MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    queue->stackA = stackCreate(100); // 栈 A 的初始容量
    queue->stackB = stackCreate(100); // 栈 B 的初始容量
    return queue;
}

// 入队操作
void myQueuePush(MyQueue* obj, int x) {
    stackPush(obj->stackA, x);  // 将元素推入栈 A
}

// 出队操作
int myQueuePop(MyQueue* obj) {
    if (stackIsEmpty(obj->stackB)) {  // 如果栈 B 为空
        while (!stackIsEmpty(obj->stackA)) {  // 将栈 A 中的元素全部移到栈 B
            stackPush(obj->stackB, stackPop(obj->stackA));
        }
    }
    return stackPop(obj->stackB);  // 从栈 B 出栈
}

// 获取队列头部元素
int myQueuePeek(MyQueue* obj) {
    if (stackIsEmpty(obj->stackB)) {  // 如果栈 B 为空
        while (!stackIsEmpty(obj->stackA)) {  // 将栈 A 中的元素全部移到栈 B
            stackPush(obj->stackB, stackPop(obj->stackA));
        }
    }
    return stackTop(obj->stackB);  // 返回栈 B 顶部元素
}

// 检查队列是否为空
int myQueueEmpty(MyQueue* obj) {
    return stackIsEmpty(obj->stackA) && stackIsEmpty(obj->stackB);  // 栈 A 和栈 B 都为空时队列为空
}

// 释放队列内存
void myQueueFree(MyQueue* obj) {
    stackFree(obj->stackA);
    stackFree(obj->stackB);
    free(obj);
}

// 测试主函数
int main() {
    MyQueue* queue = myQueueCreate();
    
    myQueuePush(queue, 1);
    myQueuePush(queue, 2);
    printf("peek: %d\n", myQueuePeek(queue));  // 应输出 1
    printf("pop: %d\n", myQueuePop(queue));   // 应输出 1
    printf("empty: %d\n", myQueueEmpty(queue));  // 应输出 0

    myQueuePush(queue, 3);
    printf("peek: %d\n", myQueuePeek(queue));  // 应输出 2
    printf("pop: %d\n", myQueuePop(queue));   // 应输出 2
    printf("pop: %d\n", myQueuePop(queue));   // 应输出 3
    printf("empty: %d\n", myQueueEmpty(queue));  // 应输出 1

    myQueueFree(queue);
    return 0;
}

代码逐行解释

栈的实现

typedef struct {
    int* data;
    int top;
    int capacity;
} Stack;

我们首先定义了一个 Stack 结构体，包含了三个成员：

• data：存储栈元素的数组。
• top：栈顶元素的索引。
• capacity：栈的最大容量。

Stack* stackCreate(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->data = (int*)malloc(sizeof(int) * capacity);
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

stackCreate 用来初始化一个栈，分配内存并设置初始值。

int stackIsEmpty(Stack* stack) {
    return stack->top == -1;
}

stackIsEmpty 用于检查栈是否为空，栈空时返回 1。

void stackPush(Stack* stack, int x) {
    stack->data[++stack->top] = x;
}

stackPush 用于将元素推入栈中，top 先自增再将元素存入。

int stackPop(Stack* stack) {
    return stack->data[stack->top--];
}

stackPop 用于从栈中弹出元素，并返回弹出的元素。

int stackTop(Stack* stack) {
    return stack->data[stack->top];
}

stackTop 用于获取栈顶元素，但不删除它。

队列的实现

typedef struct {
    Stack* stackA;
    Stack* stackB;
} MyQueue;

我们定义了一个 MyQueue 结构体，它包含两个栈：

• stackA 用于存储入队元素。
• stackB 用于存储出队元素。

MyQueue* myQueueCreate() {
    MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    queue->stackA = stackCreate(100); 
    queue->stackB = stackCreate(100); 
    return queue;
}

myQueueCreate 用于创建一个队列并初始化其中的两个栈。

void myQueuePush(MyQueue* obj, int x) {
    stackPush(obj->stackA, x);  
}

myQueuePush 将元素压入 stackA。

int myQueuePop(MyQueue* obj) {
    if (stackIsEmpty(obj->stackB)) {
        while (!stackIsEmpty(obj->stackA)) {
            stackPush(obj->stackB, stackPop(obj->stackA));
        }
    }
    return stackPop(obj->stackB);
}

myQueuePop 用于从队列中弹出元素。首先检查 stackB 是否为空，如果为空，则将 stackA 中的所有元素转移到 stackB 中。然后从 stackB 弹出栈顶元素。

int myQueuePeek(MyQueue* obj) {
    if (stackIsEmpty(obj->stackB)) {
        while (!stackIsEmpty(obj->stackA)) {
            stackPush(obj->stackB, stackPop(obj->stackA));
        }
    }
    return stackTop(obj->stackB);
}

myQueuePeek 用于获取队列头部的元素，逻辑与 myQueuePop 相同，只不过不移除元素。

int myQueueEmpty(MyQueue* obj) {
    return stackIsEmpty(obj->stackA) && stackIsEmpty(obj->stackB);
}

myQueueEmpty 检查队列是否为空，只有当 stackA 和 stackB 都为空时，队列才为空。

void myQueueFree(MyQueue* obj) {
    stackFree(obj->stackA);
    stackFree(obj->stackB);
    free(obj);
}

myQueueFree 用于释放队列及其内部栈的内存。