力扣：用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列
題目：
劍指 Offer 09. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
難度簡(jiǎn)單708收藏分享切換為英文接收動(dòng)態(tài)反饋
用兩個(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]
提示：
1 <= values <= 10000最多會(huì)對(duì)
?appendTail、deleteHead?進(jìn)行?10000?次調(diào)用
第一個(gè)對(duì)法：
無(wú)視題目要求直接用內(nèi)置函數(shù)（我這個(gè)屑）
class?CQueue?{
????queue<int>?q;
public:
????CQueue()?{
????????
????}
????
????void?appendTail(int?value)?{
????????q.push(value);
????}
????
????int?deleteHead()?{
????????if(q.empty())return?-1;
????????int?ans?=?q.front();
????????q.pop();
????????return?ans;
????}
};
/**
?*?Your?CQueue?object?will?be?instantiated?and?called?as?such:
?*?CQueue*?obj?=?new?CQueue();
?*?obj->appendTail(value);
?*?int?param_2?=?obj->deleteHead();
?*/
第一種錯(cuò)法：
class?CQueue?{
private:
????stack<int>?a1;
????stack<int>?a2;
public:
????CQueue()?{
????????
????}
????
????void?appendTail(int?value)?{
????????a1.push(value);
????}
????
????int?deleteHead()?{
????????while(!a1.empty()){
????????????a2.push(a1.top());
????????????a1.pop();
????????}
????????if(!a2.empty()){
????????????int?ans?=?a2.top();
????????????a2.pop();
????????????return?ans;
????????}
????????else?return?-1;
????}
};
/**
?*?Your?CQueue?object?will?be?instantiated?and?called?as?such:
?*?CQueue*?obj?=?new?CQueue();
?*?obj->appendTail(value);
?*?int?param_2?=?obj->deleteHead();
?*/
這里是因?yàn)槊看蝿h除一個(gè)元素的時(shí)候都把第一個(gè)棧的元素放到第二個(gè)棧那里，其實(shí)是只能在第二個(gè)棧空的時(shí)候再把第一個(gè)棧的全部元素都放進(jìn)去，不然會(huì)破壞了第二個(gè)棧的順序
第二種對(duì)法：
class?CQueue?{
private:
????stack<int>?a1;
????stack<int>?a2;
public:
????CQueue()?{
????????
????}
????
????void?appendTail(int?value)?{
????????a1.push(value);
????}
????
????int?deleteHead()?{
????????if(a2.empty()){
????????????while(!a1.empty()){
????????????????a2.push(a1.top());
????????????????a1.pop();
????????????}
????????}
????????if(!a2.empty()){
????????????int?ans?=?a2.top();
????????????a2.pop();
????????????return?ans;
????????}
????????else?return?-1;
????}
};
/**
?*?Your?CQueue?object?will?be?instantiated?and?called?as?such:
?*?CQueue*?obj?=?new?CQueue();
?*?obj->appendTail(value);
?*?int?param_2?=?obj->deleteHead();
?*/
