题目链接
225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)
题目描述
思路
//栈是后进先出 队列是先进后出
//用两个队列来回倒
//思路：把数据入到一个有数据的队列,出的时候把前n-1个数据倒到另一个队列
//然后留下来的数据再出出去就可以了，就这样一直来回倒。
代码
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int QDataType; // 链式结构：表示队列 typedef struct QListNode { struct QListNode* next; QDataType data; }QNode; // 队列的结构 typedef struct Queue { QNode* front; QNode* tail; }Queue; // 初始化队列 void QueueInit(Queue* q); // 队尾入队列 void QueuePush(Queue* q, QDataType data); // 队头出队列 void QueuePop(Queue* q); // 获取队列头部元素 QDataType QueueFront(Queue* q); // 获取队列队尾元素 QDataType QueueBack(Queue* q); // 获取队列中有效元素个数 int QueueSize(Queue* q); // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q); // 销毁队列 void QueueDestory(Queue* pq); #define _CRT_SECURE_NO_WARNINGS 1 // 初始化队列 void QueueInit(Queue* q) { assert(q); q->front = NULL; q->tail = NULL; } // 队尾入队列 void QueuePush(Queue* q, QDataType data) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("QueuePush:"); exit(-1); } newnode->data = data; newnode->next = NULL; if (q->front ==NULL && q->tail == NULL) { q->front = q->tail = newnode; } else { q->tail->next = newnode; q->tail = newnode; } } int QueueSize(Queue* q) { assert(q); QNode* cur=q->front; int count=0; while(cur!=NULL) { count++; cur=cur->next; } return count; } // 队头出队列 void QueuePop(Queue* q) { assert(q); assert(q->front && q->tail); QNode* next = q->front->next; if (next != NULL) { free(q->front); q->front = NULL; q->front = next; } else { free(q->front); q->front = NULL; q->tail = NULL; } } // 获取队列头部元素 QDataType QueueFront(Queue* q) { assert(q); assert(q->front != NULL); return q->front->data; } // 获取队列队尾元素 QDataType QueueBack(Queue* q) { assert(q); assert(q->tail != NULL); return q->tail->data; } // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q) { assert(q); return q->front ==NULL && q->tail == NULL; } // // 销毁队列 // void QueueDestory(Queue* q) // { // assert(q); // assert(q->front == NULL); // QNode* cur = q->front; // QNode* next = cur->next; // while (next != NULL) // { // free(cur); // cur = NULL; // cur = next; // next = next->next; // } // free(cur); // cur = NULL; // } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->front; while (cur) { QNode* next = cur->next; free(cur); cur = next; } } /// // #include <stdio.h> // #include <stdlib.h> // #include <stdbool.h> // #include <assert.h> // typedef int QDataType; // //typedef struct QueueNode // //{ // // QDataType data; // // struct QueueNode* next; // //}QNode, *PNode; // typedef struct QueueNode // { // QDataType data; // struct QueueNode* next; // }QNode; // typedef struct Queue // { // QNode* head; // QNode* tail; // //size_t size; // }Queue; // void QueueInit(Queue* pq); // void QueueDestory(Queue* pq); // void QueuePush(Queue* pq, QDataType x); // void QueuePop(Queue* pq); // bool QueueEmpty(Queue* pq); // size_t QueueSize(Queue* pq); // QDataType QueueFront(Queue* pq); // QDataType QueueBack(Queue* pq); // void QueueInit(Queue* pq) // { // assert(pq); // pq->head = pq->tail = NULL; // } // void QueueDestory(Queue* pq) // { // assert(pq); // QNode* cur = pq->head; // while (cur) // { // QNode* next = cur->next; // free(cur); // cur = next; // } // pq->head = pq->tail = NULL; // } // void QueuePush(Queue* pq, QDataType x) // { // assert(pq); // QNode* newnode = (QNode*)malloc(sizeof(QNode)); // assert(newnode); // newnode->data = x; // newnode->next = NULL; // if (pq->tail == NULL) // { // assert(pq->head == NULL); // pq->head = pq->tail = newnode; // } // else // { // pq->tail->next = newnode; // pq->tail = newnode; // } // } // void QueuePop(Queue* pq) // { // assert(pq); // assert(pq->head && pq->tail); // if (pq->head->next == NULL) // { // free(pq->head); // pq->head = pq->tail = NULL; // } // else // { // QNode* next = pq->head->next; // free(pq->head); // pq->head = next; // } // } // bool QueueEmpty(Queue* pq) // { // assert(pq); // //return pq->head == NULL && pq->tail == NULL; // return pq->head == NULL; // } // size_t QueueSize(Queue* pq) // { // assert(pq); // QNode* cur = pq->head; // size_t size = 0; // while (cur) // { // size++; // cur = cur->next; // } // return size; // } // QDataType QueueFront(Queue* pq) // { // assert(pq); // assert(pq->head); // return pq->head->data; // } // QDataType QueueBack(Queue* pq) // { // assert(pq); // assert(pq->tail); // return pq->tail->data; // } // //以上是队列 //栈是后进先出 队列是先进后出 //用两个队列来回倒 //思路：把数据入到一个有数据的队列,出的时候把前n-1个数据倒到另一个队列 //然后留下来的数据再出出去就可以了，就这样一直来回倒。 //用两个队列实现 typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* pst=(MyStack*)malloc(sizeof(MyStack)); assert(pst); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; } void myStackPush(MyStack* obj, int x) { assert(obj); 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); } //因为还要pop所以要先用top保存 int top = QueueFront(nonemptyQ); QueuePop(nonemptyQ); return top; } int myStackTop(MyStack* obj) { assert(obj); Queue* nonemptyQ=&obj->q1; if(QueueEmpty(&obj->q1)) { nonemptyQ=&obj->q2; } int top=QueueBack(nonemptyQ); return top; } bool myStackEmpty(MyStack* obj) { assert(obj); return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { assert(obj); QueueDestory(&obj->q1); QueueDestory(&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); */
最后的最后，创作不易，希望读者三连支持💖
赠人玫瑰，手有余香💖
