LeetCode每日精进：225.用队列实现栈

题目链接：225.用队列实现栈

题目描述：

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

实现 MyStack 类：

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

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false] 解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False

提示：

1 <= x <= 9最多调用100 次 push、pop、top 和 empty每次调用 pop 和 top 都保证栈不为空  思路：

        由于要使用到队列，需要添加队列的相关代码，参考队列：数据结构中的”排队艺术“

1.栈的结构 typedef struct { Queue q1; Queue q2; } MyStack;

        这里我们定义的栈用两个队列进行实现栈先进后出的特性。

2.栈的创建 MyStack* myStackCreate()

        对我们的栈申请空间，并对结构中的两个队列初始化，返回指向栈的指针。

MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; } 3.入栈 void myStackPush(MyStack* obj, int x)

        假设栈中原有数据1，在将下一个数据入栈时，为了方便之后取栈顶元素和出栈的操作，下一个数据2直接找非空队列q1入队列即可。

        所以入栈的操作是：找非空队列直接入队列即可，若两队列均为空，则入哪个队列都可以，这里我们默认两队列为空时数据入队列q2。

代码实现：

void myStackPush(MyStack* obj, int x) { if (!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else{ QueuePush(&obj->q2,x); } } 4.出栈 int myStackPop(MyStack* obj)

        假设现在队列q1中有4个数据，所对应的栈的结构如右图所示，在右图的栈中出栈只需将栈的有效数据个数减一即可，但在我们定义的栈中，由于队列q1只能从队头出数据，所以在出栈操作中需要使用两个队列。        

Queue* emp = &obj->q1; Queue* noneEmp = &obj->q2; if (QueueEmpty(&obj->q2)) { emp = &obj->q2; noneEmp = &obj->q1; }

         由于需要频繁判断两个队列是否为空，这里令q1为空队列emp，q2为非空队列noneEmp，若q2为空队列，那么令q1为非空队列，q2为空队列，这样无需再区分q1，q2哪个为空队列和非空队列了。          

        这里我们将除非空队列中的最后一个元素4以外的元素按照顺序入到空队列中，由于需要返回出栈的元素，我们用top记录后，再出队列即可。 

while(QueueSize(noneEmp) > 1) { QueuePush(emp,QueueFront(noneEmp)); QueuePop(noneEmp); } int top = QueueFront(noneEmp); QueuePop(noneEmp); return top;

         所以出栈的操作是：将非空队列noneEmp中前size-1个数据入到空队列emp中，记录非空队列中出栈元素，再将其出队列。

完整代码：

while(QueueSize(noneEmp) > 1) { QueuePush(emp,QueueFront(noneEmp)); QueuePop(noneEmp); } int top = QueueFront(noneEmp); QueuePop(noneEmp); return top; 5.返回栈顶元素 int myStackTop(MyStack* obj)

        图示中栈顶元素为4，对应我们定义的栈中非空队列q1的队尾元素4。

        所以返回栈顶元素的操作是：找非空队列，返回非空队列队尾元素。

代码实现：

int myStackTop(MyStack* obj) { if (!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else{ return QueueBack(&obj->q2); } } 6.判空 bool myStackEmpty(MyStack* obj)

        无论q1还是q2只要队列中有数据，那么对应的栈则不为空，所以当两个队列都为空时，栈为空，返回true，两个队列中只要有一个队列有数据，则栈不为空，返回false。

代码实现：

bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } 7.销毁 void myStackFree(MyStack* obj)

         由于我们定义的栈中有两个队列，所以先将队列q1，q2销毁，又因为在这之前栈的创建myStackCreate()函数中申请了一个MyStack大小的空间，所以需要将参数obj所指向的空间释放并置空，从而完成销毁。

代码实现：

void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); obj = NULL; } 代码总览： typedef int QDataType; // 链式结构：表示队列 typedef struct QListNode { struct QListNode* _next; QDataType _data; }QNode; // 队列的结构 typedef struct Queue { QNode* _front; QNode* _rear; int size; }Queue; void QueueInit(Queue* q) { assert(q); q->_front = q->_rear = NULL; q->size = 0; } // 队尾入队列 void QueuePush(Queue* q, QDataType data) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc"); exit(1); } newnode->_data = data; newnode->_next = NULL; if (q->_front == NULL) { q->_front = q->_rear = newnode; } else { q->_rear->_next = newnode; q->_rear = q->_rear->_next; } ++q->size; } // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q) { assert(q); return q->_front == NULL; } // 队头出队列 void QueuePop(Queue* q) { assert(!QueueEmpty(q)); if (q->_front == q->_rear) { free(q->_front); q->_front = q->_rear = NULL; } else { QNode* next = q->_front->_next; free(q->_front); q->_front = next; } --q->size; } // 获取队列头部元素 QDataType QueueFront(Queue* q) { assert(!QueueEmpty(q)); return q->_front->_data; } // 获取队列队尾元素 QDataType QueueBack(Queue* q) { assert(!QueueEmpty(q)); return q->_rear->_data; } // 获取队列中有效元素个数 int QueueSize(Queue* q) { assert(q); return q->size; } // 销毁队列 void QueueDestroy(Queue* q) { assert(q); QNode* pcur = q->_front; while (pcur) { QNode* next = pcur->_next; free(pcur); pcur = next; } q->_front = q->_rear = NULL; q->size = 0; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; } void myStackPush(MyStack* obj, int x) { if (!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else{ QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { Queue* emp = &obj->q1; Queue* noneEmp = &obj->q2; if (QueueEmpty(&obj->q2)) { emp = &obj->q2; noneEmp = &obj->q1; } while(QueueSize(noneEmp) > 1) { QueuePush(emp,QueueFront(noneEmp)); QueuePop(noneEmp); } int top = QueueFront(noneEmp); QueuePop(noneEmp); 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 = NULL; }