leetcode225 用队列实现栈（C语言）

• 1.基本数据类型
• 2.栈的结构体创建
• 3.压栈
• 4.出栈
• 5.获取栈顶元素
• 6.判断栈是否为空
• 7.销毁栈
• 8.代码全貌

leetcode225 用队列实现栈

栈——先进后出
队列——先进先出
本文将利用两个队列实现一个栈的功能。
关于队列的操作代码可以参考队列博客

我们在栈中放入两个队列结构 q1和q2

typedef struct {
    //队列1
	Queue q1;
	//队列2
	Queue q2;
} MyStack;

动态开辟栈，并且初始化其中的两个队列。

MyStack* myStackCreate() {
    //创建栈结构体
	MyStack* OBJ = (MyStack*)malloc(sizeof(MyStack));//需要malloc 否则函数结束，局部变量即销毁
	QueueInit(&OBJ->q1);
	QueueInit(&OBJ->q2);
	return OBJ;
}

如非空队列即可

void myStackPush(MyStack* obj, int x) {
    //压栈比较好解决，直接入非空队列即可
	if (!QueueEmpty(&obj->q1))//q1非空压入即可
	{
		QueuePush(&obj->q1, x);
	}
	else//q1为空 压入q2
	{
		QueuePush(&obj->q2, x);
	}
}

将非空队列（non_empty）的元素全部转移到空队列（empty）（除最后一个元素），然后将最后一个元素x（栈顶结点）保留等待返回，将最后一个元素从非空队列出队。

int myStackPop(MyStack* obj) {
    //获取非空队列
	Queue* non_empty=&obj->q1;
	Queue* empty=&obj->q2;
	if (QueueEmpty(&obj->q1))//如果q1为空，则互换
	{
		non_empty = &obj->q2;
		empty = &obj->q1;
	}
	assert(non_empty);//两者都为空则没有出栈的必要

	//保留队尾值
	QDataType x;
	x = QueueBack(non_empty);
	//弹栈 意味着消除队尾
	//将非空队的元素逐步输入到空队中
	while (non_empty->head != non_empty->tail)
	{
		QueuePush(empty, non_empty->head->data);

		//非空出队头
		QueuePop(non_empty);
	}
    //消除非空中仅剩的元素（tail）
	QueuePop(non_empty);
	return x;
}

找到非空队列，返回该队列的队尾元素

int myStackTop(MyStack* obj) {
    //获取非空队列的队尾
	Queue* non_empty = &obj->q1;
	if (QueueEmpty(&obj->q1))//如果q1为空，则互换
	{
		non_empty = &obj->q2;
	}
	assert(non_empty);//两者都为空则没有出栈的必要

	return QueueBack(non_empty);
}

如果两个队列都为空，则栈为空。

bool myStackEmpty(MyStack* obj) {
    return (QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2));
}

将两个队列销毁，然后销毁栈结构体。

void myStackFree(MyStack* obj) {
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);
	free(obj);
}

/

青山不改 绿水长流