作者：一个喜欢猫咪的的程序员
专栏：《Leetcode》
喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
目录
225. 用队列实现栈
225. 用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/
题目描述：
请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
思路：
使用两个队列q1和q2，当利用我们之前实现的队列的接口来辅助实现。
队列实现可看我的另外一篇博客：
当PUSH的时候，我们判断哪个队列为空，将元素插入到这个空队列中。
当Pop的时候，我们将要出的元素前面的所有的元素移到另外一个空的队列，当只剩下一个元素，将其出出去。
代码实现：
typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; void QInit(Queue* pq); void QDestroty(Queue* pq); void QPush(Queue* pq, QDataType x); void QPop(Queue* pq); QDataType QFront(Queue* pq); QDataType QBack(Queue* pq); bool QEmpty(Queue* pq); int QSize(Queue* pq); void QInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; pq->size = 0; } void QDestroty(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL; } void QPush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail==NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QPop(Queue* pq) { assert(pq); assert(!QEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = NULL; pq->tail = NULL; } else { QNode* del = pq->head; pq->head = pq->head->next; free(del); del = NULL; } pq->size--; } QDataType QFront(Queue* pq) { assert(pq); assert(!QEmpty(pq)); return pq->head->data; } QDataType QBack(Queue* pq) { assert(pq); assert(!QEmpty(pq)); return pq->tail->data; } bool QEmpty(Queue* pq) { assert(pq); if (pq->head == NULL && pq->tail == NULL) return true; else return false; } int QSize(Queue* pq) { assert(pq); return pq->size; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* obj=(MyStack*)malloc(sizeof(MyStack)); QInit(&obj->q1); QInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { if(!QEmpty(&obj->q1)) { QPush(&obj->q1,x); } else { QPush(&obj->q2,x); } } int myStackPop(MyStack* obj) { Queue*Empty=&obj->q1; Queue*NonEmpty=&obj->q2; if(!QEmpty(&obj->q1)) { NonEmpty=&obj->q1; Empty=&obj->q2; } while(QSize(NonEmpty)>1) { QPush(Empty,QFront(NonEmpty)); QPop(NonEmpty); } int top=QFront(NonEmpty); QPop(NonEmpty); return top; } int myStackTop(MyStack* obj) { if(!QEmpty(&obj->q1)) { return QBack(&obj->q1); } else { return QBack(&obj->q2); } } bool myStackEmpty(MyStack* obj) { return QEmpty(&obj->q1)&&QEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QDestroty(&obj->q1); QDestroty(&obj->q2); free(obj); }
232. 用栈实现队列
232. 用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/
题目描述：
示例：
代码实现：
typedef int STDatatype; typedef struct Stack { STDatatype* a; int capacity; int top; }ST; void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps, STDatatype x); void StackPop(ST* ps); STDatatype StackTop(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST*ps); void StackInit(ST* ps) { assert(ps); ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4); if (ps->a == NULL) { perror("Init fail"); exit(-1); } ps->capacity = 4; ps->top = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps, STDatatype x) { assert(ps); if (ps->capacity == ps->top) { STDatatype* tmp = (STDatatype*)realloc(ps->a,ps->capacity * 2 * sizeof(ps->a)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } STDatatype StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; } typedef struct { ST pushst; ST popst; } MyQueue; MyQueue* myQueueCreate() { MyQueue* pq=(MyQueue*)malloc(sizeof(MyQueue)); StackInit(&pq->pushst); StackInit(&pq->popst); return pq; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushst,x); } int myQueuePop(MyQueue* obj) { int peek=myQueuePeek(obj); StackPop(&obj->popst); return peek; } int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popst)) { while(!StackEmpty(&obj->pushst)) { StackPush(&obj->popst,StackTop(&obj->pushst)); StackPop(&obj->pushst); } } return StackTop(&obj->popst); } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushst)&&StackEmpty(&obj->popst); } void myQueueFree(MyQueue* obj) { StackDestory(&obj->pushst); StackDestory(&obj->popst); free(obj); } /** * Your MyQueue struct will be instantiated and called as such: * MyQueue* obj = myQueueCreate(); * myQueuePush(obj, x); * int param_2 = myQueuePop(obj); * int param_3 = myQueuePeek(obj); * bool param_4 = myQueueEmpty(obj); * myQueueFree(obj); */
