問題描述：
請你僅用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通隊列的全部四種操作（push、top、pop和empty）。
實現MyStack類：
- void push(int x) 將元素x壓入棧頂。
- int pop()移除并返回棧頂元素。
- int top()返回棧頂元素。
- boolean empty()如果棧是空的，返回true；否則，返回false。
解題思路：?
?
1. 入數據，往不為空的隊列入
2. 出數據，把不為空的隊列數據導入為空，直至只剩最后一個
解決本題之前，要先將隊列的各類接口函數準備好，隊列的接口函數我上一篇中提到了喔：
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//刪除數據和插入數據需要記錄頭結點和尾結點
typedef struct Queue
{QNode* head;QNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
//隊尾入
void QueuePush(Queue* pq, QDataType x);
//隊頭出
void QueuePop(Queue* pq);
//取隊頭的數據
QDataType QueueFront(Queue* pq);
//取隊尾的數據
QDataType QueueBack(Queue* pq);
//取數據的個數
int QueueSize(Queue* pq);
//判斷隊列是否為空
bool QueueEmpty(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));if (newnode == NULL){printf("malloc fail\n");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;}}
//隊頭出
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head);//斷言隊列是否為空，為空就不可刪除，會有野指針if (pq->head->next == NULL)//當只有一個節點時，tail可能為野指針，tail指向已釋放的空間pq->tail = NULL;QNode* next = pq->head->next;free(pq->head);pq->head = next;}
//取隊頭的數據
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}
//取隊尾的數據
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head);return pq->tail->data;
}
//取數據的個數
int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* cur = pq->head;while (cur){size++;cur = cur->next;}return size;
}
//判斷隊列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}通過隊列創建棧：
typedef struct
{Queue q1;Queue q2;
}MyStack;
MyStack* myStackCreate()
{MyStack* ps = (MyStack*)malloc(sizeof(MyStack));if (ps == NULL){printf("malloc fail\n");exit(-1);}QueueInit(&ps->q1);//對隊列進行初始化QueueInit(&ps->q2);return ps;
}在棧頂添加數據：
添加數據時，要在不為空的隊列里添加：
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)
{QueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);
}整體代碼：
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//刪除數據和插入數據需要記錄頭結點和尾結點
typedef struct Queue
{QNode* head;QNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
//隊尾入
void QueuePush(Queue* pq, QDataType x);
//隊頭出
void QueuePop(Queue* pq);
//取隊頭的數據
QDataType QueueFront(Queue* pq);
//取隊尾的數據
QDataType QueueBack(Queue* pq);
//取數據的個數
int QueueSize(Queue* pq);
//判斷隊列是否為空
bool QueueEmpty(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));if (newnode == NULL){printf("malloc fail\n");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;}}
//隊頭出
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head);//斷言隊列是否為空，為空就不可刪除，會有野指針if (pq->head->next == NULL)//當只有一個節點時，tail可能為野指針，tail指向已釋放的空間pq->tail = NULL;QNode* next = pq->head->next;free(pq->head);pq->head = next;}
//取隊頭的數據
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}
//取隊尾的數據
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head);return pq->tail->data;
}
//取數據的個數
int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* cur = pq->head;while (cur){size++;cur = cur->next;}return size;
}
//判斷隊列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}
typedef struct
{Queue q1;Queue q2;
}MyStack;
MyStack* myStackCreate()
{MyStack* ps = (MyStack*)malloc(sizeof(MyStack));if (ps == NULL){printf("malloc fail\n");exit(-1);}QueueInit(&ps->q1);QueueInit(&ps->q2);return ps;
}
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)
{QueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);
}
