題目：用隊列實現棧

示例1：

輸入：
[“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
{QDataType val;struct QueueNode* next; 
}QNode;
//隊列結構
typedef struct Queue
{QNode* phead;//隊頭QNode* ptail;//隊尾int size;//隊列大小
}Queue;//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//銷毀
void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur = pq->phead;while (pcur){QNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//隊尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}//隊頭刪除
void QueuePop(Queue* pq)
{assert(pq && pq->size > 0);if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}//取隊頭數據
QDataType QueueFront(Queue* pq)
{assert(pq && pq->size > 0);return pq->phead->val;
}//取隊尾數據
QDataType QueueBack(Queue* pq)
{assert(pq && pq->ptail);return pq->ptail->val;
}//判斷隊列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}//隊列個數
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//————————————————————————————
typedef struct {Queue q1;Queue 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) 
{Queue* empty = &(obj->q1);Queue* nonEmpty = &(obj->q2);if(!QueueEmpty(&(obj->q1))){empty = &(obj->q2);nonEmpty = &(obj->q1);}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);obj = NULL;
}