leetcode 255.用队列实现栈

255.用队列实现栈

不出意外大概率这几天都会更新 leetcode，如果没有做新的题，大概就会把 leetcode 之前写过的题整理（单链表的题目居多一点）出来写成博客

今天讲的题蛮容易出错的（注意传参啊，最好把队列的实现写过一遍，写起来就容易一点）

---

题目

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

文字 和 画图 分析

1. 首先思考一下 栈 和 队列 两者之间 的区别：

栈：先进后出（用数组实现） 队列：先进先出（用链表实现）

栈：

队列：

      2. 最大的问题就是 出元素

   

明显一个队列我们不好模拟出栈，这里我们就要借助 两个队列去实现

栈是出 存进去的最后一个元素，而队列是出 存进去的第 一 个元素，要想两者对等，即第一个元素也就是最后 一个元素

我们把存放所有元素的那一个队列，除了最后一个元素， 其它的元素都移到没有存放元素的那一个队列，这样就做 到第一个元素也就是最后一个元素

      3. 存入元素

这里我们需要确保其中一个队列始终为空（有利于后面的 出元素），另一个队列专门存入元素，由于后续的出元素 导致我们无法确保哪一个队列存元素，哪一个队列为空 （如果 q1存元素，进行一次出元素之后，它就为空了 ），

这里我们用了一个方法：再定义两个指针 nonEmpty 和 Empty，用来存放 两个队列 的地址，开始nonEmpty存放 q1的地址，Empty存放q2的地址，判断 q1是否为空，如 果为空，nonEmpty存放q2的地址，Empty存放q1的地址

（也可以用 if ,else语句直接判断）

---

代码

typedef int QLType;
typedef struct QueueNode
{QLType val;struct QueueNode* next;
}QN;//创建节点
typedef struct QueueList
{QN* head;QN* tail;int size;
}QL;//创建队列
void QNInit(QL* pphead)
{pphead->head = pphead->tail = NULL;pphead->size = 0;
}//队列初始化
QLType QLTop(QL* pphead)
{return pphead->head->val;
}//返回列队的头节点元素
QLType QLtail(QL* pphead)
{return pphead->tail->val;
}//返回列队的尾节点元素
int  QLSize(QL* pphead)
{return pphead->size;
}//返回队列里面有效元素个数
bool QLEmpty(QL* pphead)
{return pphead->head == NULL;
}//判断队列是否为空
void QNPop(QL* pphead)
{QN* cur = pphead->head;pphead->head = pphead->head->next;free(cur);pphead->size--;
}//出队列存储的第一个元素
void QNPush(QL* pphead, QLType x)
{QN* newnode = (QN*)malloc(sizeof(QN));newnode->next = NULL;newnode->val = x;if (newnode == NULL){perror("malloc");return;}if (QLEmpty(pphead)){pphead->head = pphead->tail = newnode;}else{pphead->tail->next = newnode;pphead->tail = newnode;}pphead->size++;
}//存入队列元素//以上都是服务队列的创建typedef struct 
{QL q1;QL q2;
}MyStack//存放两个队列MyStack* myStackCreate() 
{MyStack* obj = (MyStack*)malloc(sizeof(MyStack));QNInit(&obj->q1);QNInit(&obj->q2);return obj;
} //两个队列的初始化void myStackPush(MyStack* obj, int x) 
{if(!QLEmpty(&obj->q1)){QNPush(&obj->q1,  x);}else{QNPush(&obj->q2,  x);}
}//存放元素int myStackPop(MyStack* obj)
{QL *nonEmpty = &obj->q1;QL *Empty = &obj->q2;if(QLEmpty(&obj->q1)){nonEmpty = &obj->q2;Empty = &obj->q1;}while(QLSize(nonEmpty) > 1){QNPush(Empty, QLTop(nonEmpty));QNPop(nonEmpty);}int top = QLTop(nonEmpty);QNPop(nonEmpty);return top;
}//出元素int myStackTop(MyStack* obj) 
{if(!QLEmpty(&obj->q1)){return QLtail(&obj->q1);}else{return QLtail(&obj->q2);}
}//返回栈顶元素bool myStackEmpty(MyStack* obj) 
{return  QLEmpty(&obj->q1) && QLEmpty(&obj->q2);
}//判断两个栈是否都为空void myStackFree(MyStack* obj) 
{free(obj);
}//销毁空间