【数据结构与算法】使用栈实现队列（图文详解）
【摘要】 栈和队列在数据结构上是两种完全不同的类型（栈是后进先出，队列是先进先出），解决问题的关键就在于如何巧妙地利用两个栈的后进先出的特性来模拟队列先进先出的行为。
我们定义两个栈，stack1和stack2。其中一个栈（例如stack1）用于入队操作，另一个栈（例如stack2）用于出队操作。
目录
一、问题描述
原题出自
二、前置知识
关于栈的详细讲解请阅读这篇文章
关于队列的详细讲解请阅读这篇文章
三、解题思路
使用两个栈（Stack）来实现队列（Queue）的功能是一个经典的算法问题。栈和队列在数据结构上是两种完全不同的类型（栈是后进先出，队列是先进先出），解决问题的关键就在于如何巧妙地利用两个栈的后进先出的特性来模拟队列先进先出的行为。
原理：
- 结构定义：我们定义两个栈，
stack1和stack2。其中一个栈（例如stack1）用于入队操作，另一个栈（例如stack2）用于出队操作。- 入队操作：所有元素都压入
stack1。- 出队操作：
- 如果
stack2不为空，直接从stack2弹出栈顶元素，作为出队元素。- 如果
stack2为空，则将stack1中的所有元素逐个弹出并压入stack2（这个操作实际上是将stack1的元素反转后压入stack2），然后再从stack2弹出栈顶元素，作为出队元素。- 取队首元素：类似出队操作，只是最后支取栈顶元素，不出栈
图解：
（为方便理解对队列的结构进行了简化）
取队首元素类似于出队列，只是取出的元素不出栈
注：
另外还有一种可行的实现方式：
结构定义：一个栈用来出队列和入队列，另一个栈保持为空，只用来移动数据
- 入队列：都入到非空栈
- 出队列 ：先将非空栈的所有元素（除了最后一个）移到空栈，最后的元素出栈并返回，并将移出的元素移动回来恢复顺序
- 取队首元素：先将非空栈的所有元素（除了最后一个）移到空栈，最后的元素返回，再将移出的元素移动回来恢复顺序
这种方法在理论上是可行的，只不过每次出队列或取队首元素都需要将栈的元素移动两遍，效率比较低，因此这里就不给出实现代码了，建议使用第一种方式
四、C语言实现代码
🍃栈实现代码：
// 支持动态增长的栈
typedef int STDataType;//对数据类型重命名，方便后期修改类型
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;//定义结构同时重命名
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//判断是否需要扩容
if (ps->top == ps->capacity)
{
int newcapa = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapa);
if (tmp == NULL)
{
perror("realloc\n");
exit(1);
}
ps->a = tmp;
ps->capacity = newcapa;
}
//确定空间足够之后再插入数据
ps->a[ps->top] = data;
ps->top++;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top);
ps->top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top);
return ps->a[ps->top-1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
🍃栈实现队列代码：
typedef struct {
Stack pushst;//入数据的栈
Stack popst;//出数据的栈
} MyQueue;
MyQueue* myQueueCreate() //初始化
{
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&(obj->pushst));
StackInit(&(obj->popst));
return obj;
}
void myQueuePush(MyQueue* obj, int x) //模拟入队列
{
assert(obj);
StackPush(&(obj->pushst), x);//入队列直接插入到pushst栈
}
int myQueuePop(MyQueue* obj) //模拟出队列
{
assert(obj);
assert(!StackEmpty(&(obj->popst)) || !StackEmpty(&(obj->pushst)));//首先两个栈不能都为空
if (StackEmpty(&(obj->popst)))//如果popst栈为空，把数据倒过去
{
while (obj->pushst.top)
{
StackPush(&(obj->popst), StackTop(&(obj->pushst)));
StackPop (&(obj->pushst));
}
}
int top = StackTop(&(obj->popst));
StackPop(&(obj->popst));//再从popst栈出数据
return top;
}
int myQueuePeek(MyQueue* obj) //模拟取队列首元素
{
assert(obj);
assert(!StackEmpty(&(obj->popst)) || !StackEmpty(&(obj->pushst)));
if (StackEmpty(&(obj->popst)))//如果popst栈为空，把数据倒过去
{
while (obj->pushst.top)
{
StackPush(&(obj->popst), StackTop(&(obj->pushst)));
StackPop(&(obj->pushst));
}
}
return StackTop(&(obj->popst));
}
bool myQueueEmpty(MyQueue* obj) //模拟队列判空
{
return StackEmpty(&(obj->pushst)) && StackEmpty(&(obj->popst));
}
void myQueueFree(MyQueue* obj) //销毁
{
StackDestroy(&(obj->pushst));
StackDestroy(&(obj->popst));
free(obj);
obj = NULL;
}
🍃测试文件及结果：
void test2()
{
MyQueue* Queue = myQueueCreate();
if (myQueueEmpty(Queue))
printf("队列空\n");
else
printf("队列非空\n");
myQueuePush(Queue, 1);
myQueuePush(Queue, 2);
myQueuePush(Queue, 3);
myQueuePush(Queue, 4);
printf("队首元素 %d\n", myQueuePeek(Queue));
if (myQueueEmpty(Queue))
printf("队列空\n");
else
printf("队列非空\n");
while (!myQueueEmpty(Queue))
{
printf("%d ", myQueuePop(Queue));
}
printf("\n");
if (myQueueEmpty(Queue))
printf("队列空\n");
else
printf("队列非空\n");
myQueueFree(Queue);
}
【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）