力扣 225 用隊列實現棧
題目描述
請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop?和?empty）。
實現?MyStack?類：
void push(int x)?將元素 x 壓入棧頂。int pop()?移除并返回棧頂元素。int top()?返回棧頂元素。boolean empty()?如果棧是空的，返回?true?；否則，返回?false?。
思路分析
關于棧的功能，見于是基礎的數據結構，且如果知道隊列的功能也一定會知道棧的功能，這里不過多贅述，直接上思路
基于棧后進先出，而隊列先進先出的特點，我們可以定義兩個隊列，
這里先描述出棧的實現，假設一個隊列里已經放好了值，為1，2，3，4，按照隊列出隊的話，先取到1，但如果出棧的話，就需要取到4，這里另外一個隊列就派上用場了，我們可以將隊尾前的所有元素出隊，并進入到另一個隊列里，最后剩下的就是需要出棧的元素，此時我們在去原隊列的隊頭元素即可。
接下來到入棧的實現，關鍵在于應該入哪個隊，如果兩隊為空，隨便一個，但接下來的話如果要方便上述出棧的實現，我們就需要入隊到不為空的隊列。
緊接著是返回棧頂元素，我們已經知道，隊尾就是我們出棧的元素，所以這里直接返回隊列的隊尾元素即可。
判斷棧為空，直接檢測兩個隊列是否同時為空即可。
力扣不提供隊列的實現代碼，我們需要自己實現
完整代碼
隊列的實現代碼
typedef int QueueDataType;typedef struct QuNode
{QueueDataType data;struct QuNode* next;
}QuNode;typedef struct Queue
{QuNode* phead;QuNode* ptail;int size;
}Queue;// 初始化隊列
void QueueInit(Queue* q);
// 隊尾入隊列
void QueuePush(Queue* q, QueueDataType data);
// 隊頭出隊列
void QueuePop(Queue* q);
// 獲取隊列頭部元素
QueueDataType QueueFront(Queue* q);
// 獲取隊列隊尾元素
QueueDataType QueueBack(Queue* q);
// 獲取隊列中有效元素個數
int QueueSize(Queue* q);
// 檢測隊列是否為空，如果為空返回非零結果，如果非空返回0
int QueueEmpty(Queue* q);
//打印隊列
void QueuePrint(Queue* q);
// 銷毀隊列
void QueueDestroy(Queue* q);// 初始化隊列
void QueueInit(Queue* q)
{assert(q);q->phead = NULL;q->ptail = NULL;q->size = 0;
}
// 隊尾入隊列
void QueuePush(Queue* q, QueueDataType data)
{assert(q);//創建結點QuNode* newnode = (QuNode*)malloc(sizeof(QuNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = data;newnode->next = NULL;//插入if (q->ptail == NULL){q->phead = q->ptail = newnode;}else{q->ptail->next = newnode;q->ptail = newnode;}q->size++;
}// 隊頭出隊列
void QueuePop(Queue* q)
{assert(q);assert(q->phead);QuNode* del = q->phead;q->phead = q->phead->next;free(del);del = NULL;if (q->phead == NULL){q->ptail = NULL;}q->size--;
}// 獲取隊列頭部元素
QueueDataType QueueFront(Queue* q)
{assert(q);assert(q->phead);return q->phead->data;
}
// 獲取隊列隊尾元素
QueueDataType QueueBack(Queue* q)
{assert(q);assert(q->ptail);return q->ptail->data;
}
// 獲取隊列中有效元素個數
int QueueSize(Queue* q)
{assert(q);return q->size;
}
// 檢測隊列是否為空，如果為空返回非零結果，如果非空返回0
int QueueEmpty(Queue* q)
{assert(q);if (q->phead == NULL){return 1;}else{return 0;}
}// 銷毀隊列
void QueueDestroy(Queue* q)
{assert(q);QuNode* cur = q->phead;while (cur){QuNode* next = cur->next;free(cur);cur = next;}q->phead = q->ptail = NULL;q->size = 0;
}//打印隊列
void QueuePrint(Queue* q)
{assert(q);QuNode* cur = q->phead;while (cur->next!=NULL){printf("%d ", cur->data);cur = cur->next;}
}實現代碼
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* pst, int x) {if(QueueEmpty(&pst->q1))//找出不為空的隊列將元素入隊{QueuePush(&pst->q2,x);}else{QueuePush(&pst->q1,x);}}int myStackPop(MyStack* pst) {Queue* empty=&pst->q1;//假設法，假設q1為空，后面再判斷一下結果，不對再反過來Queue* noneempty=&pst->q2;if(QueueEmpty(&pst->q2)){empty=&pst->q2;noneempty=&pst->q1;}while(QueueSize(noneempty)>1)//將出棧元素前的所有元素出隊，進入到空隊列中{QueuePush(empty,QueueFront(noneempty));QueuePop(noneempty);}int top=QueueFront(noneempty);//取到出棧元素QueuePop(noneempty);return top;}int myStackTop(MyStack* pst) {if(QueueEmpty(&pst->q1))//返回不為空隊列的隊尾元素{return QueueBack(&pst->q2);}else{return QueueBack(&pst->q1);}}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;}
