題目

題目分析

鏈接: 題目

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）：

實現 MyQueue 類：

void push(int x) 將元素 x 推到隊列的末尾
int pop() 從隊列的開頭移除并返回元素
int peek() 返回隊列開頭的元素
boolean empty() 如果隊列為空，返回 true ；否則，返回 false

根據題目，我們可以知道，我們需要用兩個棧來實現隊列，棧的出入規則是后進先出，而隊列的出入規則是先進先出。
如果我們現在又兩個棧，pushpst和popst,先在pushst中入4個數據（4,3,2,1）。

如果我們要出數據的話，我們根據隊列的出入原則，應該出數據1，所以我們可以把pushst里面的數據全部倒入到popst中，那么popst中的數據為(1,2,3,4).
如圖：

如果需要出數據的話，直接按照順序出就可以了。
那么，問題來了，我們要入數據，需要在哪個棧里面入？
答案是pushst.如果我們要入數據（5，6）.

pushst拿來入數據，popst拿來出數據，剛好可以滿足隊列的需求。先出四個數據。

想再出數據時，已經沒有數據了，我們需要從pushst里再次倒入數據（5，6），

再依此類推…

代碼

棧的實現

我們實現棧使用的是數組。

結構體。

先創建一個結構體

typedef int STDataType;
typedef struct stack
{STDataType* a;int top;//棧當前大小int capacity;//棧的大小
}ST;

棧的初始化

void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}

棧的銷毀

void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}

入棧

void Push(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity)//如果棧的空間不夠了，我們需要擴容。{int newnode = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newnode);if (tmp == NULL) {perror("realloc:fail");}pst->a = tmp;pst->capacity = newnode;}pst->a[pst->top++] = x;
}

刪除

void Pop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;//只需要頂部刪除即可
}

查找頂部數據

STDataType Top(ST* pst)
{return pst->a[pst->top-1];
}

判空

bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}

答案

我們需要先創建兩個棧的結構體

結構體

typedef struct {ST pushst;ST popst;
} MyQueue;

初始化

MyQueue* myQueueCreate() {MyQueue * obj = (MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->pushst);//對每一個隊列進行初始化STInit(&obj->popst);return obj;
}

插入數據

void myQueuePush(MyQueue* obj, int x) {Push(&obj->pushst,x);//只需要往pushst里面插入就可以了
}

刪除數據

先對popst判空，如果為空，我們需要倒入數據后，再刪除數據。

int myQueuePop(MyQueue* obj) {if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){Push(&obj->popst,Top(&obj->pushst));Pop(&obj->pushst);//倒入一個，記得刪除一個}}int top = Top(&obj->popst);//獲取頂部蘇數據Pop(&obj->popst);//刪除頂部數據return top;
}

獲取隊列開頭元素

跟myQueuePop(MyQueue* obj)函數類似

int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){Push(&obj->popst,Top(&obj->pushst));Pop(&obj->pushst);}}return Top(&obj->popst);
}

判空

兩個棧為空，隊列才為空。

bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}

銷毀棧

先要對連個隊列進行銷毀，再對兩個棧的結構體銷毀。

void myQueueFree(MyQueue* obj) {STDestory(&obj->popst);STDestory(&obj->pushst);free(obj);
}