数据结构C语言练习(两个栈实现队列)

一、引言

在数据结构的学习中，我们经常会遇到一些有趣的问题，比如如何用一种数据结构去实现另一种数据结构的功能。本文将深入探讨 “用栈实现队列” 这一经典问题，详细解析解题思路、代码实现以及每个函数的作用，帮助读者更好地理解数据结构之间的转换与应用。

练习题：

1.力扣 232. 用栈实现队列

二、解题思路

队列的特点是先进先出（FIFO），而栈的特点是后进先出（LIFO）。为了用栈实现队列，我们使用两个栈：pushST 和 popST。

• 入队操作（push）：直接将元素压入 pushST 栈。
• 出队操作（pop）和获取队头元素（peek）：若 popST 栈为空，将 pushST 栈中的所有元素依次弹出并压入 popST 栈，此时 popST 栈的栈顶元素就是队列的队头元素，然后进行相应的弹出（pop）或返回（peek）操作。
• 判空操作（empty）：只有当 pushST 和 popST 两个栈都为空时，队列才为空。

三、数据结构定义

typedef int STDataType;
typedef struct Stack {
    STDataType* _a;
    int _top;
    int _capacity;
} Stack;

typedef struct {
    Stack pushST;
    Stack popST;
} MyQueue;

• Stack 结构体表示栈，包含存储数据的数组 _a、栈顶指针 _top 和容量 _capacity。
• MyQueue 结构体包含两个栈 pushST 和 popST，用于实现队列功能。

四、栈的基础操作函数详解

1. 栈初始化（StackInit）

void StackInit(Stack* ps) {
    ps->_a = NULL;
    ps->_capacity = ps->_top = 0;
}

• 功能：初始化栈，将栈的存储数组、容量和栈顶指针都置为初始状态。
• 步骤：将 _a 置为 NULL，_capacity 和 _top 置为 0，表示空栈。

2. 入栈操作（StackPush）

void StackPush(Stack* ps, STDataType data) {
    assert(ps);
    if (ps->_capacity == ps->_top) {
        int newCapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
        STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("Fail realloc");
            exit(1);
        }
        ps->_a = tmp;
        ps->_capacity = newCapacity;
    }
    ps->_a[ps->_top++] = data;
}

• 功能：将元素压入栈顶。
• 步骤：
  1. 检查栈是否已满，若满则扩容（初始容量为 4，每次扩容为原来的 2 倍）。
  2. 扩容后将新元素插入到栈顶位置，更新 _top 指针。

三、队列操作函数详解

1. myQueueCreate：创建队列

MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&pq->pushST);
    StackInit(&pq->popST);
    return pq;
}

• 功能：创建队列实例。
• 步骤：
  • 为 MyQueue 分配内存，确保存储队列相关数据的空间。
  • 初始化内部的 pushST(入) 和 popST(出) 栈，通过 StackInit 清空栈状态，为后续操作做准备。

2. myQueuePush：入队操作

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST, x);
}

• 功能：将元素加入队列尾部。
• 原理：直接利用 pushST 栈的入栈操作。入队操作只需关注元素添加，无需处理顺序，因此直接将元素压入 pushST，后续出队时再通过 popST 调整顺序。

3. myQueuePop：出队操作(取后删)

int myQueuePop(MyQueue* obj) {
    if (StackEmpty(&obj->popST)) {
        while (!StackEmpty(&obj->pushST)) {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    int top = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return top;
}

• 功能：移除并返回队列头部元素。
• 步骤：
  • 检查 popST 是否为空。若为空，需将 pushST 中元素转移到 popST，以模拟队列的先进先出。转移过程：不断获取 pushST 栈顶元素（StackTop），压入 popST（StackPush），再弹出 pushST 栈顶元素（StackPop）。
  • 转移完成后，popST 栈顶即为队列头部元素，获取该元素值（StackTop），弹出 popST 栈顶元素（StackPop），并返回元素值。

4. myQueuePeek：获取队头元素(取不删)

int myQueuePeek(MyQueue* obj) {
    if (StackEmpty(&obj->popST)) {
        while (!StackEmpty(&obj->pushST)) {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}

• 功能：返回队列头部元素，不弹出。
• 逻辑：与 myQueuePop 类似。先确保 popST 有元素（若 popST 空，转移 pushST 元素），再通过 StackTop 获取 popST 栈顶元素，即队列头部元素，不执行弹出操作。

5. myQueueEmpty：判断队列是否为空

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}

• 功能：判断队列是否为空。
• 原理：队列由 pushST 和 popST 共同维护，只有两者都为空时，队列才为空。通过同时检查两个栈的 StackEmpty 状态实现判断。

6. myQueueFree：释放队列资源

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}

• 功能：释放队列及内部栈占用的内存。
• 步骤：
  • 先调用 StackDestroy 销毁 pushST 和 popST 栈，释放栈内部存储元素的内存。
  • 最后释放队列结构体 obj 本身的内存，完成资源清理。

六、总结

通过两个栈的巧妙配合，我们成功地实现了队列的功能。这种实现方式不仅加深了我们对栈和队列特性的理解，还展示了如何通过组合数据结构来解决实际问题。在实际编程中，灵活运用数据结构的特性可以让我们更高效地解决各种问题。希望本文的解析能帮助读者更好地掌握这一经典实现方法。