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

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

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

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

目录

做题思路

代码实现

1. MyQueue

2. myQueueCreate

 3. myQueuePush

4. myQueuePeek

5. myQueuePop

6. myQueueEmpty

7. myQueueFree

全部代码

---

做题思路

简单来说，就是把一个栈（栈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);
}

---

本文完​​​​​​​