LeetCode鏈接：232. 用棧實現(xiàn)隊列 - 力扣（LeetCode）
注：本文默認讀者已掌握棧與隊列的基本操作
可以看這篇文章熟悉知識點：【數(shù)據(jù)結(jié)構(gòu)】棧與隊列_字節(jié)連結(jié)的博客-CSDN博客
目錄
做題思路
代碼實現(xiàn)
1. MyQueue
2. myQueueCreate
3. myQueuePush
4. myQueuePeek
5. myQueuePop
6. myQueueEmpty
7. myQueueFree
全部代碼
做題思路
簡單來說，就是把一個棧（棧1）的數(shù)據(jù)捯入另一個棧（棧2），此時（棧2）出數(shù)據(jù)的順序就和隊列是一樣的。
為了更方便理解，我會畫圖來演示一下具體思路。
我們需要兩個棧來實現(xiàn)隊列：
- push棧：專門入數(shù)據(jù)的棧
- pop棧：專門出數(shù)據(jù)的棧
如下圖：
插入數(shù)據(jù)：直接在push棧內(nèi)插入即可
push棧內(nèi)插入數(shù)據(jù)：1、2、3、4、5
刪除數(shù)據(jù)：需要把push棧內(nèi)的數(shù)據(jù)捯入pop棧
- 棧是后入先出的
- 當push棧的數(shù)據(jù)捯入pop棧后，數(shù)據(jù)順序會改變
如下圖：
可以看到數(shù)據(jù)順序逆轉(zhuǎn)了
但是棧的這些操作跟隊列有什么聯(lián)系呢？
不妨來看看pop棧與隊列的對比：
由此可見：pop棧出數(shù)據(jù)的順序是和隊列一樣的
到這里思路已經(jīng)很清晰了：我們需要兩個棧，一個專門用來push，一個專門用來pop，捯數(shù)據(jù)后，pop棧出數(shù)據(jù)的順序就跟隊列是一樣的。
那么如何用代碼（C）來實現(xiàn)這個思路呢？
代碼實現(xiàn)
由于我們使用的是C語言，不能直接使用棧的操作
所以先把之前模擬實現(xiàn)過的棧復(fù)制過來：
//C語言模擬實現(xiàn)棧
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
//初始化棧
void STInit(ST* ps);
//銷毀棧
void STDestroy(ST* ps);
//入棧
void STPush(ST* ps, STDataType x);
//出棧
void STPop(ST* ps);
//獲取棧頂元素
STDataType STTop(ST* ps);
//獲取棧中有效元素個數(shù)
int STSize(ST* ps);
//檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
bool STEmpty(ST* ps);
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void STPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void STPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
STDataType STTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}復(fù)制完成之后就是本題的重點內(nèi)容了。
本題要求：
實現(xiàn)?
MyQueue?類：
void push(int x)?將元素 x 推到隊列的末尾int pop()?從隊列的開頭移除并返回元素int peek()?返回隊列開頭的元素boolean empty()?如果隊列為空，返回?true?；否則，返回?false
1. MyQueue
由于我們是用兩個棧實現(xiàn)隊列
所以這里需要定義兩個棧
//兩個棧模擬實現(xiàn)隊列
typedef struct
{
ST pushst;
ST popst;
} MyQueue;2. myQueueCreate
這個函數(shù)要求我們開辟空間，并初始化棧
//開辟空間并初始化
MyQueue* myQueueCreate()
{
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}3. myQueuePush
直接把數(shù)據(jù)插入到push棧即可
//將元素X推到隊列的末尾
void myQueuePush(MyQueue* obj, int x)
{
STPush(&obj->pushst, x);
}
4. myQueuePeek
本函數(shù)要求返回隊列開頭的元素
- 如果pop棧為空：要把push棧的數(shù)據(jù)捯入pop棧才能找到隊列的首元素
- 如果pop棧不為空：pop棧的棧頂元素就是隊列的首元素
//返回隊列開頭的元素
int myQueuePeek(MyQueue* obj)
{
if (STEmpty(&obj->popst))
{
//捯數(shù)據(jù)
while (!STEmpty(&obj->pushst))
{
STPush(&obj->popst, STTop(&obj->pushst));
STPop(&obj->pushst);
}
}
return STTop(&obj->popst);
}5. myQueuePop
- 要求刪除隊頭元素，也就是pop棧的棧頂元素，直接刪除即可
- 并且要返回隊頭元素的值，需要先定義一個臨時變量來保存隊頭元素的值
- 最后返回這個臨時變量
//從隊列的開頭移除并返回元素
int myQueuePop(MyQueue* obj)
{
int front = myQueuePeek(obj);
STPop(&obj->popst);
return front;
}6. myQueueEmpty
判斷隊列是否為空，返回一個bool值（true/false）
如果push棧和pop棧都為空，則說明隊列為空
//如果隊列為空，返回true；否則，返回false
bool myQueueEmpty(MyQueue* obj)
{
return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}7. myQueueFree
銷毀隊列
- 銷毀push棧和pop棧
- 釋放動態(tài)開辟的空間
//銷毀隊列
void myQueueFree(MyQueue* obj)
{
STDestroy(&obj->popst);
STDestroy(&obj->pushst);
free(obj);
}到這里全部函數(shù)已經(jīng)實現(xiàn)完畢，提交代碼：
成功通過
下面我會把本題的全部代碼整合在一起發(fā)出來文章來源：http://www.zghlxwxcb.cn/news/detail-677259.html
全部代碼
//C語言模擬實現(xiàn)棧
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
//初始化棧
void STInit(ST* ps);
//銷毀棧
void STDestroy(ST* ps);
//入棧
void STPush(ST* ps, STDataType x);
//出棧
void STPop(ST* ps);
//獲取棧頂元素
STDataType STTop(ST* ps);
//獲取棧中有效元素個數(shù)
int STSize(ST* ps);
//檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
bool STEmpty(ST* ps);
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void STPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void STPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
STDataType STTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
//=======================================================================
//兩個棧模擬實現(xiàn)隊列
typedef struct
{
ST pushst;
ST popst;
} MyQueue;
//開辟空間并初始化
MyQueue* myQueueCreate()
{
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}
//將元素X推到隊列的末尾
void myQueuePush(MyQueue* obj, int x)
{
STPush(&obj->pushst, x);
}
//返回隊列開頭的元素
int myQueuePeek(MyQueue* obj)
{
if (STEmpty(&obj->popst))
{
//捯數(shù)據(jù)
while (!STEmpty(&obj->pushst))
{
STPush(&obj->popst, STTop(&obj->pushst));
STPop(&obj->pushst);
}
}
return STTop(&obj->popst);
}
//從隊列的開頭移除并返回元素
int myQueuePop(MyQueue* obj)
{
int front = myQueuePeek(obj);
STPop(&obj->popst);
return front;
}
//如果隊列為空，返回true；否則，返回false
bool myQueueEmpty(MyQueue* obj)
{
return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}
//銷毀隊列
void myQueueFree(MyQueue* obj)
{
STDestroy(&obj->popst);
STDestroy(&obj->pushst);
free(obj);
}本文完文章來源地址http://www.zghlxwxcb.cn/news/detail-677259.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】如何用棧實現(xiàn)隊列？圖文解析（LeetCode）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
