数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列（核心思路、解题过程、完整题解）一：https://developer.aliyun.com/article/1530537
销毁栈函数
销毁栈不能只free掉栈结构体的空间，栈结构里面还有两个队列结构，而队列里面有指针指向链式结构。只free掉栈结构体时，会发生内存泄漏，即队列里面指向链式结构的指针没得到释放。所以我们应该由内到外，先把两个队列free掉，最后再free掉栈。
void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }
完整题解（C语言）
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; }Queue; void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } void QueueDestroy(Queue* pq) { assert(pq); QueueNode* cur = pq->head; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->data = x; newnode->next = NULL; if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); QueueNode* next = pq->head->next; free(pq->head); pq->head = next; if (pq->head == NULL) { pq->tail = NULL; } } 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; } int QueueSize(Queue* pq) { assert(pq); int n = 0; QueueNode* cur = pq->head; while (cur) { n++; cur = cur->next; } return n; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* st = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&st->q1); QueueInit(&st->q2); return st; } 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* nonemptyQ = &obj->q2; if(!QueueEmpty(&obj->q1)) { emptyQ = &obj->q2; nonemptyQ = &obj->q1; } while(QueueSize(nonemptyQ) > 1) { QueuePush(emptyQ,QueueFront(nonemptyQ)); QueuePop(nonemptyQ); } int top = QueueFront(nonemptyQ); QueuePop(nonemptyQ); 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); } /** * 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、pop、peek、empty）：实现
MyQueue类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
题目示例
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
核心思路
与上一道题本质上是没有区别的，所以就只写一下核心思路
要用两个栈来实现队列： 入数据时，入到其中的一个栈中。（设此栈为PushStack） 出数据时，将有数据的栈转移到另一个栈，这样就把数据倒过来了，这时直接出这个栈的数据就实现了先进先出了（设此栈为PopStack）
完整题解（C语言）
typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; //或者ps->top = -1; ps->capacity = 0; } void StackPrint(ST* ps) { assert(ps); for (int i = 0; i < ps->top; i++) { printf("%d\t", ps->a[i]); } printf("\n"); } void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0;//top为0返回真，否则返回假 } void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } 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]; } int StackSize(ST* ps)//计算栈中有多少个元素 { assert(ps); return ps->top; } typedef struct { ST pushST; ST popST; } MyQueue; MyQueue* myQueueCreate() { MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&q->pushST); StackInit(&q->popST); return q; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushST,x); } int myQueuePop(MyQueue* obj) { //如果popST中没有数据，将pushST的数据传递过去 //popST中的数据就可以符合先进先出的顺序了 if(StackEmpty(&obj->popST)) { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } int front = StackTop(&obj->popST); StackPop(&obj->popST); return front; } int myQueuePeek(MyQueue* obj) { //如果popST中没有数据，将pushST的数据传递过去 //popST中的数据就符合先进先出的顺序 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) { StackDestroy(&obj->pushST); StackDestroy(&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); */
