【数据结构】如何用栈实现队列？图文解析（LeetCode）

LeetCode链接：232. 用栈实现队列 - 力扣（LeetCode）

注：本文默认读者已掌握栈与队列的基本操作

可以看这篇文章熟悉知识点：【数据结构】栈与队列_字节连结的博客-CSDN博客

做题思路

简单来说，就是把一个栈（栈1）的数据捯入另一个栈（栈2），此时（栈2）出数据的顺序就和队列是一样的。

为了更方便理解，我会画图来演示一下具体思路。

我们需要两个栈来实现队列：

• push栈：专门入数据的栈
• pop栈：专门出数据的栈

如下图：

插入数据：直接在push栈内插入即可

push栈内插入数据：1、2、3、4、5

删除数据：需要把push栈内的数据捯入pop栈

• 栈是后入先出的
• 当push栈的数据捯入pop栈后，数据顺序会改变

如下图：

可以看到数据顺序逆转了

但是栈的这些操作跟队列有什么联系呢？

不妨来看看pop栈与队列的对比：

由此可见：pop栈出数据的顺序是和队列一样的

到这里思路已经很清晰了：我们需要两个栈，一个专门用来push，一个专门用来pop，捯数据后，pop栈出数据的顺序就跟队列是一样的。

那么如何用代码（C）来实现这个思路呢？

代码实现

由于我们使用的是C语言，不能直接使用栈的操作

所以先把之前模拟实现过的栈复制过来：

//C语言模拟实现栈

typedef int STDataType;
typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;

//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool STEmpty(ST* ps);

void STInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

void STDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

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

void STPop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}

STDataType STTop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

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

复制完成之后就是本题的重点内容了。

本题要求：

实现

MyQueue

类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

1. MyQueue

由于我们是用两个栈实现队列

所以这里需要定义两个栈

//两个栈模拟实现队列
typedef struct
{
    ST pushst;
    ST popst;
} MyQueue;

2. myQueueCreate

这个函数要求我们开辟空间，并初始化栈

//开辟空间并初始化
MyQueue* myQueueCreate()
{
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}

3. myQueuePush

直接把数据插入到push栈即可

//将元素X推到队列的末尾
void myQueuePush(MyQueue* obj, int x)
{
    STPush(&obj->pushst, x);
}

4. myQueuePeek

本函数要求返回队列开头的元素

• 如果pop栈为空：要把push栈的数据捯入pop栈才能找到队列的首元素
• 如果pop栈不为空：pop栈的栈顶元素就是队列的首元素

//返回队列开头的元素
int myQueuePeek(MyQueue* obj)
{
    if (STEmpty(&obj->popst))
    {
        //捯数据
        while (!STEmpty(&obj->pushst))
        {
            STPush(&obj->popst, STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }
    return STTop(&obj->popst);
}

5. myQueuePop

• 要求删除队头元素，也就是pop栈的栈顶元素，直接删除即可
• 并且要返回队头元素的值，需要先定义一个临时变量来保存队头元素的值
• 最后返回这个临时变量

//从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj)
{
    int front = myQueuePeek(obj);
    STPop(&obj->popst);
    return front;
}

6. myQueueEmpty

判断队列是否为空，返回一个bool值（true/false）

如果push栈和pop栈都为空，则说明队列为空

//如果队列为空，返回true；否则，返回false
bool myQueueEmpty(MyQueue* obj)
{
    return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}

7. myQueueFree

销毁队列

• 销毁push栈和pop栈
• 释放动态开辟的空间

//销毁队列
void myQueueFree(MyQueue* obj)
{
    STDestroy(&obj->popst);
    STDestroy(&obj->pushst);
    free(obj);
}

到这里全部函数已经实现完毕，提交代码：

成功通过

下面我会把本题的全部代码整合在一起发出来

全部代码

//C语言模拟实现栈

typedef int STDataType;
typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;

//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool STEmpty(ST* ps);

void STInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

void STDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

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

void STPop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}

STDataType STTop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

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

//=======================================================================

//两个栈模拟实现队列
typedef struct
{
    ST pushst;
    ST popst;
} MyQueue;

//开辟空间并初始化
MyQueue* myQueueCreate()
{
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}

//将元素X推到队列的末尾
void myQueuePush(MyQueue* obj, int x)
{
    STPush(&obj->pushst, x);
}

//返回队列开头的元素
int myQueuePeek(MyQueue* obj)
{
    if (STEmpty(&obj->popst))
    {
        //捯数据
        while (!STEmpty(&obj->pushst))
        {
            STPush(&obj->popst, STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }
    return STTop(&obj->popst);
}

//从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj)
{
    int front = myQueuePeek(obj);
    STPop(&obj->popst);
    return front;
}

//如果队列为空，返回true；否则，返回false
bool myQueueEmpty(MyQueue* obj)
{
    return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}

//销毁队列
void myQueueFree(MyQueue* obj)
{
    STDestroy(&obj->popst);
    STDestroy(&obj->pushst);
    free(obj);
}

本文完