用队列实现栈

题目

leetcode /problems/implement-stack-using-queues/submissions/599882147

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

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

typedef struct { } MyStack; MyStack* myStackCreate(); void myStackPush(MyStack* obj, int x); int myStackPop(MyStack* obj); bool myStackEmpty(MyStack* obj); void myStackFree(MyStack* obj); /** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj); */

注意：

你只能使用队列的标准操作 —— 也就是 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

思路 保持一个队列为空，一个队列存数据出栈，把前面的数据导入空队列 代码

队列实现代码

typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; } QNode; typedef struct Queue { QNode* head; QNode* tail; int size; } Queue; void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("Queue()::malloc fail"); return; } newnode->data = x; newnode->next = NULL; if (pq->head == NULL) { assert(pq->tail == NULL); pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->size++; } void QueuePop(Queue* pq) { assert(pq && pq->head); if (pq->head == pq->tail) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* del = pq->head; pq->head = pq->head->next; free(del); } pq->size--; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }

题目实现

typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); if (pst == NULL) { perror("myStackCreate()::malloc fail"); return NULL; } 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* emptyQ = &obj->q1; Queue* noemptyQ = &obj->q2; if (!QueueEmpty(&obj->q1)) { emptyQ = &obj->q2; noemptyQ = &obj->q1; } //倒数据 while (QueueSize(noemptyQ) > 1) { QueuePush(emptyQ, QueueFront(noemptyQ)); QueuePop(noemptyQ); } QDataType top = QueueFront(noemptyQ); QueuePop(noemptyQ); 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); }