摘要
- 用棧實(shí)現(xiàn)隊(duì)列践剂，用隊(duì)列實(shí)現(xiàn)棧，雖然可能沒有什么實(shí)際應(yīng)用價(jià)值娜膘，但是對于熟悉棧和隊(duì)列的結(jié)構(gòu)以及基本操作是很有意義的逊脯。
- 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
- 通過讓隊(duì)列循環(huán)來實(shí)現(xiàn)棧
今日學(xué)習(xí)的視頻和文章
- 代碼隨想錄 棧和隊(duì)列的基礎(chǔ)
- C++Primer 棧和隊(duì)列部分
- 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)C++語言版（第二版）棧和隊(duì)列部分
LeetCode232 用隊(duì)列實(shí)現(xiàn)棧
- 今天的題目比較簡單，棧是后進(jìn)先出竣贪，而隊(duì)列是先進(jìn)先出军洼，用棧實(shí)現(xiàn)隊(duì)列的關(guān)鍵就在于如何將后進(jìn)先出轉(zhuǎn)化為先進(jìn)先出。
- 如果我們只用一個(gè)棧演怎，能不能做到先進(jìn)先出呢匕争？由于題目要求只能使用棧的標(biāo)準(zhǔn)操作，而彈出先進(jìn)的元素（即棧底的元素）前必須彈出在其之后的所有元素爷耀，所以我們應(yīng)該用另一塊內(nèi)存空間來保留這部分元素汗捡。而這部分元素的彈出順序是遵循棧的后進(jìn)先出的，由對稱性的想法畏纲，這另一個(gè)用來保存元素的空間也可以是棧的結(jié)構(gòu)扇住。
- 例如，這里元素1盗胀，2艘蹋，3入棧，【或】表示棧底
- 棧in：【1票灰，2女阀，3 ；棧out：【
- 此時(shí)屑迂，根據(jù)隊(duì)列的先進(jìn)先出浸策，我們要彈出1，將2惹盼，3保留在另一個(gè)棧中
- 棧in：【1庸汗；棧out：【3，2手报，
- 為了代碼邏輯更加簡潔蚯舱，我們可以統(tǒng)一將棧1的元素都push進(jìn)棧2中改化，而不是判斷棧1是否還剩余1個(gè)元素
- 棧in：【；棧out：【3枉昏，2陈肛，1
- 此時(shí)在讓棧2的棧頂元素出棧即可
- 棧in：【；棧out：【3兄裂，2
- 再插入元素到用棧實(shí)現(xiàn)的隊(duì)列中的邏輯與元素出隊(duì)列的邏輯是對稱的句旱，銜接上面的例子，我們要插入元素4晰奖，元素4是后進(jìn)的前翎，所以對于出棧來說它應(yīng)該位于棧底：棧out【4，3畅涂，2
- 棧in：【港华；棧out：【3，2
- 此時(shí)午衰，將棧out的元素push回棧in中
- 棧in：【2立宜，3；棧out：【
- 然后再將元素4 push進(jìn)棧in中
- 棧in：【2臊岸，3橙数，4；棧out：【
- 這樣就完成了元素4進(jìn)入用棧實(shí)現(xiàn)的隊(duì)列的操作
完整題解代碼如下
class MyQueue {
private:
stack<int> in;
stack<int> out;
public:
MyQueue() {
}
void push(int x) {
while (!out.empty()) {
in.push(out.top());
out.pop();
}
in.push(x);
}
int pop() {
while (!in.empty()) {
out.push(in.top());
in.pop();
}
int temp = out.top();
out.pop();// 要注意這里的 pop 會返回值帅戒，而C++STL的棧的pop是不返回值的
return temp;
}
int peek() {
while (!in.empty()) {
out.push(in.top());
in.pop();
}
return out.top();
}
bool empty() {
return in.empty() && out.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
LeetCode225 用隊(duì)列實(shí)現(xiàn)棧
- 初見題目時(shí)的想法：既然用兩個(gè)棧能實(shí)現(xiàn)隊(duì)列灯帮，那對稱地來想，是不是能用兩個(gè)隊(duì)列來實(shí)現(xiàn)棧呢逻住？
- 這里用【表示隊(duì)列頭钟哥，用】表示隊(duì)列尾
- 假設(shè)元素1，2瞎访，3進(jìn)入由隊(duì)列實(shí)現(xiàn)的棧腻贰，那么根據(jù)后進(jìn)先出，此時(shí)應(yīng)該彈出的是元素3
- 隊(duì)列1：【1扒秸，2播演，3】；隊(duì)列2：【】
- 如果我們簡單去類比用兩個(gè)棧實(shí)現(xiàn)隊(duì)列伴奥，想用兩個(gè)隊(duì)列實(shí)現(xiàn)棧的話
- 隊(duì)列1：【】写烤；隊(duì)列2：【1，2拾徙，3】
- 上面的隊(duì)列2再pop洲炊，還是彈出元素1而不是元素3。
- 因?yàn)殛?duì)列是先進(jìn)先出，即使我們模仿棧實(shí)現(xiàn)隊(duì)列的思路选浑，把要彈出的元素之前的元素保留在另一個(gè)隊(duì)列中，也無法實(shí)現(xiàn)棧玄叠。因?yàn)樵跅５暮筮M(jìn)先出古徒，我們可以通過兩個(gè)棧顛倒元素的彈出順序；但是隊(duì)列的彈出順序就是我們將元素放入隊(duì)列的順序读恃。
- 然后隧膘，我注意到，兩個(gè)棧實(shí)現(xiàn)隊(duì)列中寺惫，有一個(gè)地方被簡化了邏輯：
- ”為了代碼邏輯更加簡潔疹吃，我們可以統(tǒng)一將棧1的元素都push進(jìn)棧2中，而不是判斷棧1是否還剩余1個(gè)元素“
- 實(shí)際上西雀，我們只需要判斷隊(duì)列是否出隊(duì)到只剩隊(duì)尾元素（即最后一個(gè)進(jìn)入隊(duì)列的元素）萨驶，然后在按順序保存隊(duì)列的其他元素時(shí)讓隊(duì)尾元素出隊(duì)即可。
- 這樣一來艇肴，實(shí)際上我們可以只用一個(gè)隊(duì)列來實(shí)現(xiàn)棧腔呜，即讓隊(duì)首元素出隊(duì)后再入隊(duì)，直到我們遍歷到原來的隊(duì)尾元素再悼，讓其出隊(duì)而不再入隊(duì)即可核畴。
- 例子：【1，2冲九，3】-> 【2谤草，3，1】-> 【3莺奸，1丑孩，2】-> 【1，2】
- 那么如何push元素到由隊(duì)列實(shí)現(xiàn)的棧中呢灭贷？我們在上面實(shí)現(xiàn)的出棧操作中嚎杨，是固定彈出隊(duì)尾元素的，所以我們直接將元素push到隊(duì)列中就好了氧腰。
完整的題解代碼如下
class MyStack {
private:
queue<int> q;
public:
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
int count = 0;
while (count < q.size() - 1) {
q.push(q.front());
q.pop();
count++;
}
int temp = q.front();
q.pop();
return temp;
}
int top() {
int temp = pop();
push(temp);
return temp;
}
bool empty() {
return q.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
