一、題目
1、題目描述
用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead ，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能。(若隊(duì)列中沒(méi)有元素，deleteHead 操作返回 -1 )
示例 1：
輸入：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”,“deleteHead”]
[[],[3],[],[],[]]
輸出：[null,null,3,-1,-1]
示例 2：
輸入：
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]
2、基礎(chǔ)框架
- C++版本給出的基礎(chǔ)框架如下：
3、原題鏈接
https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
二、解題報(bào)告
1、思路分析
??
(
1
)
(1)
(1)設(shè)置兩個(gè)棧，一個(gè)入隊(duì)棧，一個(gè)出隊(duì)棧。
??
(
2
)
(2)
(2)執(zhí)行appendTail時(shí)，將元素放入入隊(duì)棧。
??
(
3
)
(3)
(3)執(zhí)行deleteHead時(shí)，刪除出隊(duì)棧的棧頭元素，如果出隊(duì)棧為空，則將入隊(duì)棧的元素移入出隊(duì)棧。再?gòu)某鲫?duì)棧刪除棧頭元素。如果入隊(duì)棧也為空，返回-1。所有入棧出棧操作均根據(jù)棧規(guī)則。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-428163.html
2、時(shí)間復(fù)雜度
入隊(duì)操作時(shí)間復(fù)雜度為O(1)
出隊(duì)操作時(shí)間復(fù)雜度為O(n)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-428163.html
3、代碼詳解
class CQueue {
public:
stack<int> s1;
stack<int> s2;
CQueue() {
}
void appendTail(int value) {
s1.push(value);
}
int deleteHead() {
int re = -1;
if (!s2.empty()) {
re = s2.top();
s2.pop();
} else if (!s1.empty()){
while (!s1.empty()){
s2.push(s1.top());
s1.pop();
}
re = s2.top();
s2.pop();
}
return re;
}
};
三、本題小知識(shí)
到了這里，關(guān)于【棧和隊(duì)列】劍指 Offer 09. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
