225、用隊列實現棧

一、題目描述

請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。實現 MyStack 類：①、void push(int x) 將元素 x 壓入棧頂。
②、nt pop() 移除并返回棧頂元素。
③、int top() 返回棧頂元素。
④、boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。

二、題目要求

Ⅰ、你只能使用隊列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 這些操作。
Ⅱ、你所使用的語言也許不支持隊列。 你可以使用 list （列表）或者 deque（雙端隊列）來模擬一個隊列 , 只要是標準的隊列操作即可。

三、題目示例

四、題目解析

首先我們看到本題是用隊列實現棧。那么我們便要對棧和隊列的相關特性有一定的了解，例如棧是先進后出的，而隊列是先進先出的。如果有伙伴對這兩種數據結構有些遺忘的話，建議看一下博主之前的兩篇文章，分別是《數據結構——棧的詳細介紹》和《數據結構——看完這篇保證你學會隊列》。
我們想要解決這道題，首先便要實現一個完整的隊列，其中的接口包括初始化隊列，銷毀隊列，入隊，出隊等，其代碼如下：

//定義數據類型
typedef int QueueDataType;
//定義隊列結構
typedef struct QueueNode
{struct QueueNode* next;QueueDataType Data;
}Qnode;//定義頭、尾指針
typedef struct Queue
{Qnode* phead;Qnode* ptail;int size;
}Queue;//初始化
void InitQueue(Queue* pq);
//銷毀
void DestoryQueue(Queue* pq);
//入隊
void PushQueue(Queue* pq, QueueDataType x);
//出隊
void PopQueue(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//獲取SIze
int SizeQueue(Queue* pq);
//獲取隊頭元素
QueueDataType QueueFront(Queue* pq);
//獲取隊尾元素
QueueDataType QueueBack(Queue* pq);void InitQueue(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
//銷毀
void DestoryQueue(Queue* pq)
{assert(pq);Qnode* cur = pq->phead;while (cur){Qnode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}
//入隊
void PushQueue(Queue* pq, QueueDataType x)
{assert(pq);Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));if (newnode == NULL){perror("malloc fail");return;}//賦值newnode->Data = x;newnode->next = NULL;//分情況討論if (pq->ptail == NULL){assert(pq->phead == NULL);pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}
//出隊
void PopQueue(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//一個節點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--;}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
//獲取SIze
int SizeQueue(Queue* pq)
{assert(pq);return pq->size;
}
//獲取隊頭元素
QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->Data;
}
//獲取隊尾元素
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->Data;
}

構建好隊列的各種接口之后，我們需要在Mystack的結構體中創建兩個隊列變量。代碼如下：

typedef struct 
{Queue q1;Queue q2;
} MyStack;

Ⅰ、MyStack* myStackCreate

該接口，需要我們在內存中開辟空間，利用malloc函數，并且將q1和q2進行初始化。

MyStack* myStackCreate() 
{MyStack*obj=(MyStack*)malloc(sizeof(MyStack));if(obj==NULL){perror("malloc fail");return NULL;}InitQueue(&obj->q1);InitQueue(&obj->q2);return obj;}

Ⅱ、void myStackPush(MyStack* obj, int x)

如果兩個隊列都為空，那么任選一個進行入隊操作即可，后續入隊往有數據的隊列進行入隊操作即可。

void myStackPush(MyStack* obj, int x) 
{if(!QueueEmpty(&obj->q1)){PushQueue(&obj->q1,x);}else{PushQueue(&obj->q2,x);}
}

Ⅲ、int myStackPop(MyStack* obj)

最為復雜的便是出棧了，我們的大體思路便是假定q1為空，q2不為空：如果結果相反，則調換一下二者的順序，我們將不為空的隊列進行出隊操作，并將其數據壓入為空的隊列，直到為空的隊列中只剩下一個數據，我們將這個數據定義為top,并對其進行出隊操作，最后將其進行返回。

 Queue*EmptyQ=&obj->q1;Queue*NonEmptyq=&obj->q2;if(!QueueEmpty(&obj->q1)){EmptyQ=&obj->q2;NonEmptyq=&obj->q1;}while(SizeQueue(NonEmptyq)>1){PushQueue(EmptyQ,QueueFront(NonEmptyq));PopQueue(NonEmptyq);}int top=QueueFront(NonEmptyq);PopQueue(NonEmptyq);return top;

Ⅳ、int myStackTop(MyStack* obj)

解決這個接口，我們首先需要找到不為空的那個隊列，然后調用其獲取隊尾數據的函數，最后將這個函數返回的結果返回即可。

int myStackTop(MyStack* obj) 
{if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

Ⅴ、bool myStackEmpty(MyStack* obj)

我們需要保證我們的兩個隊列都為空，這樣才能夠保證我們創建的隊列為空。

bool myStackEmpty(MyStack* obj) 
{return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);    
}

Ⅵ、void myStackFree(MyStack* obj)

需要先對我們所創建的q1和q2隊列進行銷毀，然后再對ob進行free操作，以防止內存的泄漏。

void myStackFree(MyStack* obj) 
{DestoryQueue(&obj->q1);DestoryQueue(&obj->q2);free(obj);}

五、完整代碼

//定義數據類型
typedef int QueueDataType;
//定義隊列結構
typedef struct QueueNode
{struct QueueNode* next;QueueDataType Data;
}Qnode;//定義頭、尾指針
typedef struct Queue
{Qnode* phead;Qnode* ptail;int size;
}Queue;//初始化
void InitQueue(Queue* pq);
//銷毀
void DestoryQueue(Queue* pq);
//入隊
void PushQueue(Queue* pq, QueueDataType x);
//出隊
void PopQueue(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//獲取SIze
int SizeQueue(Queue* pq);
//獲取隊頭元素
QueueDataType QueueFront(Queue* pq);
//獲取隊尾元素
QueueDataType QueueBack(Queue* pq);void InitQueue(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
//銷毀
void DestoryQueue(Queue* pq)
{assert(pq);Qnode* cur = pq->phead;while (cur){Qnode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}
//入隊
void PushQueue(Queue* pq, QueueDataType x)
{assert(pq);Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));if (newnode == NULL){perror("malloc fail");return;}//賦值newnode->Data = x;newnode->next = NULL;//分情況討論if (pq->ptail == NULL){assert(pq->phead == NULL);pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}
//出隊
void PopQueue(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//一個節點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--;}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
//獲取SIze
int SizeQueue(Queue* pq)
{assert(pq);return pq->size;
}
//獲取隊頭元素
QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->Data;
}
//獲取隊尾元素
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->Data;
}typedef struct 
{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() 
{MyStack*obj=(MyStack*)malloc(sizeof(MyStack));if(obj==NULL){perror("malloc fail");return NULL;}InitQueue(&obj->q1);InitQueue(&obj->q2);return obj;}void myStackPush(MyStack* obj, int x) 
{if(!QueueEmpty(&obj->q1)){PushQueue(&obj->q1,x);}else{PushQueue(&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(SizeQueue(NonEmptyq)>1){PushQueue(EmptyQ,QueueFront(NonEmptyq));PopQueue(NonEmptyq);}int top=QueueFront(NonEmptyq);PopQueue(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) 
{DestoryQueue(&obj->q1);DestoryQueue(&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);
*/