1. 理論基礎(chǔ)
- 棧和隊(duì)列對(duì)應(yīng)的三個(gè)不同的STL版本，底層實(shí)現(xiàn)方式不一樣, 為我們所知道的是 SGI STL
棧
- 棧提供 pop和push等接口， 不提供走訪功能
- 也不提供迭代器， 不像map和set可以使用迭代器遍歷，往往不被歸類為容器，而是容器適配器
- 棧的內(nèi)部實(shí)現(xiàn)結(jié)構(gòu)可以使用 verctor、list 和 deque(默認(rèn))
- 可以在初始化的時(shí)候指定使用哪種底層實(shí)現(xiàn)
std::stack<int, std::vector<int> > third; // 使用vector為底層容器的棧
std::queue<int, std::list<int>> third; // 定義以list為底層容器的隊(duì)列
棧的api
stack 包含在 頭文件中
成員函數(shù)
- top() 返回頭部元素
- empty() 檢查是否為空 size() 返回容納的元素
- push() 頂層插入元素， emplace() 在頂層構(gòu)造元素 pop() 返回為void，直接刪除元素 swap()
2. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
LeetCode 鏈接
- 注意點(diǎn)
- pop返回的是void，要彈出并獲取頂部的值應(yīng)該先top再pop
- 兩個(gè)棧有一個(gè)不為空就返回false，因此是 is.empty() && os.empty()
實(shí)現(xiàn)思路圖：
class MyQueue {
public:
MyQueue() {
}
stack<int> is;
stack<int> os;
void push(int x) {
// 將數(shù)據(jù)直接壓入is 棧
is.push(x);
}
int pop() {
// 得先判斷os中是否還有元素，如果有直接彈出，否則從is中彈出壓入到os
// 先將is棧中的內(nèi)容 逐個(gè)彈出 壓入 os棧，知道所有is中都空則彈出os棧的第一個(gè)元素
if(os.empty()){
while(!(is.empty())){
os.push(is.top());
is.pop();
}
}
int top = os.top();
os.pop();
return top;
}
int peek() {
if(os.empty()){
while(!(is.empty())){
os.push(is.top());
is.pop();
}
}
return os.top();
}
bool empty() {
return os.empty() && is.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();
*/
3. 兩個(gè)隊(duì)列實(shí)現(xiàn)棧
LeetCode
queue api
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-444573.html
class MyStack {
public:
MyStack() {
}
queue<int> qi;
queue<int> qo;
void push(int x) {
qi.push(x);
}
int pop() {
int size = qi.size();
while(--size){
qo.push(qi.front());
qi.pop();
}
int result = qi.front();
qi.pop();
while(!qo.empty()){
qi.push(qo.front());
qo.pop();
}
return result;
}
int top() {
return qi.back();
}
bool empty() {
return qi.empty() && qo.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();
*/
優(yōu)化，每次彈出的時(shí)候只需要將 彈出的元素重新添加到隊(duì)尾文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-444573.html
class MyStack {
public:
MyStack() {
}
queue<int> qi;
void push(int x) {
qi.push(x);
}
int pop() {
int size = qi.size();
while(--size){
qi.push(qi.front());
qi.pop();
}
int result = qi.front();
qi.pop();
return result;
}
int top() {
return qi.back();
}
bool empty() {
return qi.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();
*/
到了這里，關(guān)于第10天-代碼隨想錄刷題訓(xùn)練-第五章 棧和隊(duì)列- ● 理論基礎(chǔ) ● 232.用棧實(shí)現(xiàn)隊(duì)列 ● 225. 用隊(duì)列實(shí)現(xiàn)棧的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
