今日總結(jié)：快要期末考試了，現(xiàn)在在瘋狂速成，今天稍微緩和了一點(diǎn)，應(yīng)該能保證繼續(xù)每天刷題，欠下的那些寒假補(bǔ)上。
Day 10
01. 用棧實(shí)現(xiàn)隊(duì)列（No. 232）
題目鏈接
代碼隨想錄題解
1.1 題目
請(qǐng)你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列。隊(duì)列應(yīng)當(dāng)支持一般隊(duì)列支持的所有操作（push、pop、peek、empty）：
實(shí)現(xiàn) MyQueue 類：
-
void push(int x)將元素 x 推到隊(duì)列的末尾 -
int pop()從隊(duì)列的開頭移除并返回元素 -
int peek()返回隊(duì)列開頭的元素 -
boolean empty()如果隊(duì)列為空，返回true；否則，返回false
說明：
- 你 只能 使用標(biāo)準(zhǔn)的棧操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。 - 你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)棧，只要是標(biāo)準(zhǔn)的棧操作即可。
示例 1：
輸入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 1, 1, false]解釋：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9- 最多調(diào)用
100次push、pop、peek和empty - 假設(shè)所有操作都是有效的 （例如，一個(gè)空的隊(duì)列不會(huì)調(diào)用
pop或者peek操作）
1.2 筆記
非常經(jīng)典的題目，考察了對(duì)這兩個(gè)數(shù)據(jù)結(jié)構(gòu)的理解。棧實(shí)現(xiàn)了“先進(jìn)后出”而隊(duì)列則是“先進(jìn)先出”，所以如果我們想要借助棧來實(shí)現(xiàn)隊(duì)列的話，很容易就想到我們?cè)谳敵龅臅r(shí)候?qū)Ｖ械臄?shù)據(jù)反轉(zhuǎn)即可，那反轉(zhuǎn)如何實(shí)現(xiàn)呢？
這就需要用到兩個(gè)棧：
即將 Stack1 視作一個(gè) 中轉(zhuǎn)站，當(dāng)我們需要輸出的時(shí)候，就將 Stack1 中的元素 pop() 到 Stack2 中，然后從 Stack2 中取元素。
注意 push() 的時(shí)候要判斷 Stack2 是否為空，如果不為空就會(huì)出現(xiàn)順序問題，因?yàn)榇藭r(shí)的 Stack2 中即將彈出的第一個(gè)元素是我們構(gòu)造的隊(duì)列的第一個(gè)元素，如果我們?cè)?Stack2 還未空的時(shí)候就 push() 新元素進(jìn)來，就打破了確定的順序。
1.3 代碼
class MyQueue {
Stack<Integer> s1;
Stack<Integer> s2;
public MyQueue() {
// 初始化
s1 = new Stack<>();
s2 = new Stack<>();
}
public void push(int x) {
// 每次放入新元素的時(shí)候都暫存到 s1
s1.push(x);
}
public int pop() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
// 判斷 s2 是否為空
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.empty() && s2.empty();
}
}
02. 用隊(duì)列實(shí)現(xiàn)棧
題目鏈接
代碼隨想錄題解
2.1 題目
請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。
實(shí)現(xiàn) MyStack 類：
-
void push(int x)將元素 x 壓入棧頂。 -
int pop()移除并返回棧頂元素。 -
int top()返回棧頂元素。 -
boolean empty()如果棧是空的，返回true；否則，返回false。
注意：
- 你只能使用隊(duì)列的基本操作 —— 也就是
push to back、peek/pop from front、size和is empty這些操作。 - 你所使用的語言也許不支持隊(duì)列。 你可以使用 list （列表）或者 deque（雙端隊(duì)列）來模擬一個(gè)隊(duì)列 , 只要是標(biāo)準(zhǔn)的隊(duì)列操作即可。
示例：
輸入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 2, 2, false]解釋：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
提示：
1 <= x <= 9- 最多調(diào)用
100次push、pop、top和empty - 每次調(diào)用
pop和top都保證棧不為空
2.2 筆記
有了上面那道題的經(jīng)驗(yàn)，很多朋友拿到這道題就想著想上面那道題一樣倒過來就行了，那怎樣倒過來呢？
簡(jiǎn)單，在創(chuàng)建一個(gè)隊(duì)列然后從第一個(gè)隊(duì)列推入就行了。
但是提交發(fā)現(xiàn)題目還是錯(cuò)了，這是為什么呢？
隊(duì)列是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，我們把一個(gè)隊(duì)列一個(gè)個(gè)取出放入另一個(gè)隊(duì)列，順序是不會(huì)改變的，就像正數(shù)乘以一個(gè)整數(shù)還是整數(shù)，棧能夠倒置原因就是它是先進(jìn)后出，負(fù)數(shù)乘以負(fù)數(shù)結(jié)果就是正數(shù)，這樣類比起來就比較好理解。
這道題目可以使用一個(gè)隊(duì)列來實(shí)現(xiàn)，隊(duì)列的隊(duì)尾元素是棧的棧頂元素：
那如果想要?jiǎng)h除這個(gè)隊(duì)尾的元素，我們可以從隊(duì)頭開始遍歷，然后將隊(duì)頭的元素依次放到隊(duì)尾，直到最開始的隊(duì)尾元素（棧頂）是隊(duì)列的隊(duì)頭的時(shí)候停止，也就是需要遍歷 size - 1 次，這時(shí)候?qū)㈥?duì)頭元素彈出得到的就是需要的元素了。
那如何獲取隊(duì)尾元素呢？
我們可以按照上面的方法循環(huán) size- 1 然后得到隊(duì)頭的元素但不刪除。但其實(shí)我們可以設(shè)置一個(gè)變量 lastNum 當(dāng)我們需要隊(duì)尾元素的時(shí)候就直接將這個(gè)返回。文章來源：http://www.zghlxwxcb.cn/news/detail-817956.html
如果沒有刪除元素的話那這個(gè) lastNum 的值就很好確定，我們每次 add() 添加新元素的時(shí)候就將 lastNum 重置為這個(gè)值即可，那如果執(zhí)行了刪除的話，這時(shí)候原本的倒數(shù)第二個(gè)元素就成了新的 lastNum 我們只需要在遍歷到倒數(shù)第二個(gè)元素的時(shí)候?qū)⑵滟x值即可。文章來源地址http://www.zghlxwxcb.cn/news/detail-817956.html
2.3 代碼
class MyStack {
Queue<Integer> q1;
int lastNum; // 記錄最后一個(gè)元素的值
public MyStack() {
q1 = new ArrayDeque<>();
}
public void push(int x) {
q1.add(x);
lastNum = x;
}
public int pop() {
int size = q1.size();
size = size - 1;
while (size-- > 0) {
int temp = q1.remove(); // 記錄此時(shí)彈出的元素
q1.add(temp);
// 當(dāng)循環(huán)結(jié)束的時(shí)候就將其賦值成倒數(shù)第二個(gè)元素了，其實(shí)等價(jià)于 if (size == 0) {lastNum = temp; }
lastNum = temp;
}
return q1.remove();
}
public int top() {
return lastNum;
}
public boolean empty() {
return q1.isEmpty();
}
}
到了這里，關(guān)于代碼隨想錄刷題筆記（DAY 10）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
