原題鏈接：https://leetcode.cn/problems/implement-stack-using-queues/
目錄
1. 題目描述
2. 思路分析
3. 代碼實現
1. 題目描述
2. 思路分析
可以用兩個隊列去實現一個棧，每次始終保持一個隊列為空。
入棧相當于給非空隊列進行入隊操作。
出棧相當于非空隊列的隊尾元素出隊，此時需要把非空隊列除最后一個元素之外的其余元素入隊到空隊列，然后出隊最后一個隊尾元素。
3. 代碼實現
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;void QueueInit(Que* pq);
void QueuePush(Que* pq,QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
QDataType QueueSize(Que* pq);
bool QueueEmpty(Que* pq);
void QueueDestroy(Que* pq);void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc failed");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 QueuePop(Que* pq)
{assert(pq);//隊列為空assert(!QueueEmpty(pq));//只有一個結點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;}pq->size--;
}QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}QDataType QueueSize(Que* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}typedef struct {Que q1;Que 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) {Que* empty=&obj->q1;Que* nonEmpty=&obj->q2;if(!QueueEmpty(&obj->q1)){nonEmpty=&obj->q1;empty=&obj->q2;}//前size-1個導入空隊列while(QueueSize(nonEmpty)>1){QueuePush(empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int top=QueueFront(nonEmpty);QueuePop(nonEmpty);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);
*/
)