原題鏈接 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
題目描述
用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列集灌，完成隊(duì)列的Push和Pop操作祟同。 隊(duì)列中的元素為int類型。
首先總結(jié)一下隊(duì)列(queue)以及棧(stack)的特性，在總結(jié)之前給大家推薦一下不錯(cuò)的C++中文在線手冊(cè)：英文版：cppreference.com 豺鼻，如果讀起來(lái)費(fèi)勁可以去：中文翻譯：cppreference.com
-
queue：std::queue類是容器適配器沫勿，它給予程序員隊(duì)列的功能--尤其是FIFO(現(xiàn)先進(jìn)先出)數(shù)據(jù)結(jié)構(gòu)挨约。queue在底層容器尾端推入元素味混，從首端彈出元素。要實(shí)現(xiàn)的兩個(gè)操作：
- push向隊(duì)列尾部插入元素诫惭；
- pop刪除第一個(gè)元素（題主曾經(jīng)吃過(guò)的虧啊翁锡。劃重點(diǎn)：C++中pop()無(wú)返回值,題目要求是有返回值的。）
-
stack：std::stack類是容器適配器夕土，它給與程序員棧的功能--特別是FILO(先進(jìn)后出)數(shù)據(jù)結(jié)構(gòu)馆衔。棧從被稱作棧頂?shù)娜萜魑膊客茝椩亍Ｖ饕某蓡T函數(shù)：
- top():用來(lái)訪問(wèn)棧頂元素怨绣；
- empty():用來(lái)檢查底層的容器是否為空角溃；
- push:用來(lái)向棧頂插入元素；
- pop():用來(lái)刪除棧頂?shù)脑兀?/li>
- size():用來(lái)返回容納的元素?cái)?shù)篮撑。
解題思路：堆棧的特性是先進(jìn)后出减细，隊(duì)列是的特性是先進(jìn)先出。分別標(biāo)記兩個(gè)棧為S1和S2咽扇，push操作就是往S1的入棧操作邪财，pop操作要返回S1棧底的元素，首先要判斷S2是否為空质欲，若為空树埠，則要先將S1的元素從棧頂?shù)綏５兹繅喝隨2中，然后再返回S2的棧頂元素嘶伟；若S2不為空怎憋，則直接返回S2的棧頂元素。（還有一個(gè)異常判斷九昧，當(dāng)S1和S2都為空時(shí)绊袋，應(yīng)拋出異常）
具體代碼如下：
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
class Solution {
public:
void push(int Node) {
stack1.push(Node);
}
int pop() {
if(stack1.empty() && stack2.empty()) {
throw "INPUT Valid";
}
else if (stack2.empty()) {
while (!stack1.empty()) {
int tem = stack1.top();
stack1.pop();
stack2.push(tem);
}
}
int res = stack2.top();
stack2.pop();
return res;
}
private:
stack<int> stack1;
stack<int> stack2;
};
void main() {
Solution s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.pop();
s.push(5);
s.pop();
s.pop();
s.pop();
s.pop();
s.pop();
system("pause");
}
