目录
题目:
解题:
代码讲解:
1.构建
2.creat
3.压栈
4.出栈
5.判空
6.释放
题目:
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push
、top
、pop
和 empty
)。
实现 MyStack
类:
-
void push(int x)
将元素 x 压入栈顶。 -
int pop()
移除并返回栈顶元素。 -
int top()
返回栈顶元素。 -
boolean empty()
如果栈是空的,返回true
;否则,返回false
。
提示:
1 <= x <= 9
- 最多调用
100
次push
、pop
、top
和empty
- 每次调用
pop
和top
都保证栈不为空
首先要实现队列
队列的实现-CSDN博客
解题:
整体思路:
利用队列的功能函数,实现栈的基本功能。
//Create类似于初始化
MyStack* myStackCreate() { //不传参,希望你创造一个结构体去初始化,再返回
MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); //开辟空间
QueueInit(&obj->q1); //->的优先级高于&
QueueInit(&obj->q2); //->的优先级高于&
return obj;
}
void myStackPush(MyStack* obj, int x) { //往不为空的入数据
if (!QueueEmpty(&obj->q1)) //往不为空的队列录入数据
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
//利用捯元素实现(需要实现删除功能)
//错误:开辟一块额外的空间,只不过存储的是相同的值
int myStackPop(MyStack* obj) { //返回Pop的值
Q* E_Queue = &obj->q1; //假设q1是空链表
Q* None_E_Queue = &obj->q2;
if (!QueueEmpty(&obj->q1)) //肯定一个为空、一个不为空
{
E_Queue = &obj->q2;
None_E_Queue = &obj->q1;
}
while (QueueSize(None_E_Queue) > 1) //QueueSize : 元素个数
{
QueuePush(E_Queue, QueueFront(None_E_Queue)); //将头元素传递
QueuePop(None_E_Queue);
}
QDatetype top = QueueFront(None_E_Queue);
QueuePop(None_E_Queue);
return top;
}
int myStackTop(MyStack* obj) {
if (!QueueEmpty(&obj->q1)) //肯定一个为空、一个不为空
{
return Queueback(&obj->q1);
}
else
{
return Queueback(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) { //判空
return QueueEmpty(&obj->q1)
&& QueueEmpty(&obj->q2); //只有一个有元素,当两者都是空,栈才会空
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
//不能只释放obj,obj只是含有q1 q2两个成员(q1 、q2只包含指针,只释放该空间,本质是释放掉phead 、ptail 、size 三个成员,无法释放队列的节点)
}
代码讲解:
1.构建
typedef struct { //第三层嵌套(->)
Q q1; //两个链表
Q q2;
} MyStack;
两个队列,组成一个栈
2.creat
MyStack* myStackCreate() { //不传参,希望你创造一个结构体去初始化,再返回
MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); //开辟空间
QueueInit(&obj->q1); //->的优先级高于&
QueueInit(&obj->q2); //->的优先级高于&
return obj;
}
creat功能可以理解为:开辟空间、初始化
3.压栈
void myStackPush(MyStack* obj, int x) { //往不为空的入数据
if (!QueueEmpty(&obj->q1)) //往不为空的队列录入数据
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
压栈:往不为空的队列Push元素
4.出栈
int myStackPop(MyStack* obj) { //返回Pop的值
Q* E_Queue = &obj->q1; //假设q1是空链表
Q* None_E_Queue = &obj->q2;
if (!QueueEmpty(&obj->q1)) //肯定一个为空、一个不为空
{
E_Queue = &obj->q2;
None_E_Queue = &obj->q1;
}
while (QueueSize(None_E_Queue) > 1) //QueueSize : 元素个数
{
QueuePush(E_Queue, QueueFront(None_E_Queue)); //将头元素传递
QueuePop(None_E_Queue);
}
QDatetype top = QueueFront(None_E_Queue);
QueuePop(None_E_Queue);
return top;
}
出栈:
需要注意的是,当我们需要分情况对两个对象操作的时候,如果存在可以进行区分的方法,可以采用假设法。
可以先假设q1是空链表。当q1不会空,只需更该指针指向。
5.判空
bool myStackEmpty(MyStack* obj) { //判空
return QueueEmpty(&obj->q1)
&& QueueEmpty(&obj->q2); //只有一个有元素,当两者都是空,栈才会空
}
进行判空时,需要两个都为空,stack才会为空
6.释放
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
//不能只释放obj,obj只是含有q1 q2两个成员(q1 、q2只包含指针,只释放该空间,本质是释放掉phead 、ptail 、size 三个成员,无法释放队列的节点)
}
释放:
需要注意的是:需要进行两方面的释放,1.对队列各个节点的释放(在调用队列函数时,开辟了节点)。 2.对creat函数中malloc的my_stack空间的释放。my_stack只包括两个队列phead、ptail、和size三个元素。