栈实现队列

用栈实现队列：C 语言代码解析

在数据结构的世界里，栈和队列是两种基础且重要的线性结构。栈遵循后进先出（LIFO）的原则，而队列遵循先进先出（FIFO）的原则。在实现的过程之中，需要两个队列，一个用于出栈，一个用于入栈。

栈的基本实现

首先，我们来看代码中栈的实现部分。

typedef int STDataType;
typedef struct Stack
{
    STDataType* arr;
    int top;     //指向栈顶的位置
    int capacity;//栈的容量
}ST;

这里定义了一个Stack结构体，包含一个动态数组arr用于存储栈中的元素，top表示栈顶元素的位置，capacity表示栈的当前容量。

栈的初始化

void StackInit(ST* ps)
{
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

StackInit函数用于初始化栈，将arr指针设为NULL，top和capacity都初始化为 0。

栈的销毁

void StackDestroy(ST* ps)
{
    if (ps->arr)
        free(ps->arr);
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

StackDestroy函数负责释放栈所占用的内存空间。如果arr不为空，就释放arr指向的内存，然后将arr设为NULL，并重置top和capacity。

入栈操作

void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        //增容
        int newCapacity = ps->capacity == 0? 4 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
        if (tmp == NULL)
        {
            perror("realloc fail!");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    ps->arr[ps->top++] = x;
}

StackPush函数用于将元素x压入栈中。首先检查栈是否已满，如果已满则进行增容操作。增容时，新容量为当前容量为 0 时设为 4，否则为当前容量的 2 倍。使用realloc函数重新分配内存，如果分配失败则打印错误信息并退出程序。最后将元素x放入栈顶位置并将top指针后移。

检查栈是否为空

bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}

StackEmpty函数通过检查top是否为 0 来判断栈是否为空。

出栈操作

void StackPop(ST* ps)
{
    assert(!StackEmpty(ps));
    --ps->top;
}

StackPop函数用于弹出栈顶元素，首先确保栈不为空，然后将top指针前移一位。

获取栈顶元素

STDataType StackTop(ST* ps)
{
    assert(!StackEmpty(ps));
    return ps->arr[ps->top - 1];
}

StackTop函数返回栈顶元素，前提是栈不为空。

获取栈中元素个数

i

nt StackSize(ST* ps)
{
    return ps->top;
}

StackSize函数返回栈中当前有效元素的个数，即top的值。

用栈实现队列

接下来，我们看如何利用上述实现的栈来模拟队列的行为。

typedef struct {
    ST push;
    ST pop;
} MyQueue;

这里定义了一个MyQueue结构体，包含两个Stack类型的成员push和pop，分别用于入队和出队操作。

队列的创建

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

myQueueCreate函数用于创建一个新的队列。首先分配MyQueue结构体大小的内存，然后分别初始化push栈和pop栈。

入队操作

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

myQueuePush函数将元素x入队，实现很简单，直接将元素压入push栈中。

出队操作

int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {int tmp = StackTop(&obj->push);
        StackPush(&obj->pop,tmp);
        StackPop(&obj->push);}
    }

    int top = StackTop(&obj->pop);
    StackPop(&obj->pop);
    return top;
}

myQueuePop函数用于出队操作。首先检查pop栈是否为空，如果为空，则将push栈中的元素依次弹出并压入pop栈中，这样pop栈中的元素顺序就与队列的出队顺序一致了。然后弹出pop栈的栈顶元素并返回。

获取队首元素

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {int tmp = StackTop(&obj->push);
        StackPush(&obj->pop,tmp);
        StackPop(&obj->push);}
    }
    return StackTop(&obj->pop);
}

myQueuePeek函数用于获取队首元素。同样，先检查pop栈是否为空，如果为空则将push栈元素转移到pop栈，然后返回pop栈的栈顶元素。

检查队列是否为空

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
}

myQueueEmpty函数通过检查push栈和pop栈是否都为空来判断队列是否为空。

队列的销毁

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->push);
    StackDestroy(&obj->pop);
    free(obj);
    obj = NULL;
}

myQueueFree函数用于销毁队列。先分别销毁push栈和pop栈，然后释放MyQueue结构体所占用的内存。

总结

通过上述代码，我们成功地用栈实现了队列的基本操作。这种实现方式巧妙地利用了栈的后进先出特性，通过两个栈的配合来模拟队列的先进先出行为。