🎁個人主頁：我們的五年
🔍系列專欄：初階數據結構刷題
🎉歡迎大家點贊👍評論📝收藏?文章
🚗??1.問題描述：
?題目中說了只能使用兩個棧實現隊列，并且只能使用基本的棧操作。比如：在棧頂進行入棧操作，在棧頂進行出棧，取棧頂元素，還有判空這些基本的棧操作函數。然后使用這些函數實現隊列的基本操作，隊列的特點就是在隊尾插入數據，在隊頭刪除數據，在對頭取數據。
題中說使用兩個棧實現，也給了我們提示。
🚗??2.問題分析：
假如先在一個棧中插入三元素1.2.3。
當使用StackPush函數在PushST進行三次插入以后，就變成了上面的情形，但是如果我們要進行隊列取隊頭的數據，進行隊列刪除隊頭的數據，我們就要先把上面的3和2拿走。從而我們就想到了把左邊棧里面的元素的放到右邊去。
進行上面的操作以后，我們就調用棧的取棧頂的函數就可以拿到元素1，也可以進行取刪除元素1，就可以達到和隊列一樣的性質：先進先出。
插入數據的時候，我們還是在PushST中插入數據，加入先插入4，5.
如果要進行刪除操作，取元素操作也是可以直接在PopST棧中直接取。也是滿足隊列的要求的。但是當我們把PopST的元素都取完以后，我們就要再一次把PushST棧里面的元素導到PopST棧里面。
按照上面的步驟就可以實現隊列的操作。
🚗?3.代碼層面進行解析：
棧的函數接口
先給出棧的接口：
typedef int SLDataType;
typedef struct Stack{
? ? ????????SLDataType* a;
? ????????? int top;
? ? ????????int capacity;
}Stack;
//對棧進行初始化
void StackInit(Stack* ptr);
//對棧進行銷毀
void StackDestroy(Stack* ptr);
//在棧頂插入元素
void StackPush(Stack* ptr, SLDataType x);
//獲取棧頂元素
SLDataType StackTop(Stack* ptr);
//對棧進行判斷，如果為空，返回true，否則返回false
bool StackEmpty(Stack* ptr);
//銷毀棧的棧頂元素
void StackPop(Stack* ptr);
用棧的函數實現隊列
先定義我自己結構體的類型：
根據上面分析也是用兩個棧實現隊列，也就是說我的隊列類型中保護了兩個棧，并且我把這兩個隊列命名為PushST和PopST
typedef struct {Stack PushST;? ? ? ? //把元素新的元素放在這個棧，也就是在這個棧里面實現插入操作Stack PopST;? ? ? ? ?//在這個棧中取數據，刪除數據} MyQueue;創建隊列，在堆區上申請一塊空間，并且對隊列里面的棧進行初始化
MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));StackInit(&obj->PushST);? ? ? //對PushST和PopST棧進行初始化??StackInit(&obj->PopST);return obj;}取隊頭元素
int myQueuePeek(MyQueue* obj) {if(StackEmpty(&obj->PopST)) //PopST棧為空的時候就要把PushST棧里面的元素導過來{while(!StackEmpty(&obj->PushST)) //導元素{int Pop=StackTop(&obj->PushST);StackPop(&obj->PushST);StackPush(&obj->PopST,Pop);}}return StackTop(&obj->PopST); 返回PopST棧頂的元素
}銷毀隊頭元素，并且返回隊頭元素。首先應該保存PopST棧的棧頂元素，然后銷毀棧頂元素。
一個特別巧妙的點就是，我們在進行取隊頭元素的時候，如果PopST為空，取隊頭元素函數就會把PushST里面的元素導到PopST里面，這樣我們在myQueuePop中就避免了導元素這一步驟。
int myQueuePop(MyQueue* obj) {int top=myQueuePeek(obj); //取隊頭元素StackPop(&obj->PopST);return top;
}?最后的push函數和判空函數還有銷毀函數也是比較簡單的
//直接在PushST隊列中進行插入
void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->PushST,x);
}//隊列判空，當隊列里面的兩個隊列都為空時才為空
bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);
}//銷毀隊列
void myQueueFree(MyQueue* obj) {StackDestroy(&obj->PopST);StackDestroy(&obj->PushST);
}🚗?最終代碼:
typedef int SLDataType;typedef struct Stack{SLDataType* a;int top;int capacity;
}Stack;//對棧進行初始化
void StackInit(Stack* ptr);//對棧進行銷毀
void StackDestroy(Stack* ptr);//在棧頂插入元素
void StackPush(Stack* ptr, SLDataType x);//獲取棧頂元素
SLDataType StackTop(Stack* ptr);//對棧進行判斷，如果為空，返回true，否則返回false
bool StackEmpty(Stack* ptr);void StackPop(Stack* ptr);//棧的初始化
void StackInit(Stack* ptr)
{assert(ptr);ptr->a = NULL;ptr->capacity = ptr->top = 0;
}//銷毀棧
void StackDestroy(Stack* ptr)
{assert(ptr);free(ptr->a);ptr->a = NULL;ptr->capacity = ptr->top = 0; //初始化時，top=0，表示指向棧頂的下一個元素
}//在棧頂插入元素
void StackPush(Stack* ptr, SLDataType x)
{assert(ptr);if (ptr->top == ptr->capacity){int newcapacity = ptr->capacity == 0 ? 4 : ptr->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ptr->a, newcapacity*sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");return;}ptr->a = tmp;ptr->capacity = newcapacity;}ptr->a[ptr->top++] = x;
}//取棧頂元素
SLDataType StackTop(Stack* ptr)
{assert(ptr);assert(!StackEmpty(ptr));return ptr->a[ptr->top - 1];
}//棧判空
bool StackEmpty(Stack* ptr)
{assert(ptr);return ptr->top == 0;
}//銷毀棧頂元素
void StackPop(Stack* ptr)
{assert(ptr);assert(!StackEmpty(ptr));ptr->top--;
}typedef struct {Stack PushST;Stack PopST;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));StackInit(&obj->PushST);StackInit(&obj->PopST);return obj;
}void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->PushST,x);
}int myQueuePop(MyQueue* obj) {int top=myQueuePeek(obj);StackPop(&obj->PopST);return top;
}int myQueuePeek(MyQueue* obj) {if(StackEmpty(&obj->PopST)){while(!StackEmpty(&obj->PushST)){int Pop=StackTop(&obj->PushST);StackPop(&obj->PushST);StackPush(&obj->PopST,Pop);}}return StackTop(&obj->PopST);
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);
}void myQueueFree(MyQueue* obj) {StackDestroy(&obj->PopST);StackDestroy(&obj->PushST);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/?
