【題目】
編寫一個(gè)類仍翰，用兩個(gè)棧實(shí)現(xiàn)隊(duì)列，支持隊(duì)列的基本操作（add观话、poll予借、peek）。
??有一個(gè)簡(jiǎn)單，但不是最優(yōu)解的思路灵迫，如下圖喧笔，在push的時(shí)候，如果stackPop中不為空就把stackPop中的所有元素push到stackPush中龟再，最后再往stackPush中push新值书闸，此時(shí)stackPop一定為空了。peek或者poll利凑，就把stackPush中的所有元素push到stackPop中浆劲，此時(shí)stackPush為空了，同時(shí)只會(huì)出現(xiàn)其中一個(gè)stack為空的情況哀澈。
倒置stackPush棧
代碼如下：
#include <assert.h>
#include <stack>
using namespace std;
template<class T>
class DoubleStackQueue {
stack<T> m_stackPush;
stack<T> m_stackPop;
private:
inline void AlltoPopStack() {
int size = m_stackPush.size();
for (int i = 0; i < size; ++i) {
m_stackPop.push(m_stackPush.top());
m_stackPush.pop();
}
}
public:
void push(const T val) {
int size = m_stackPop.size();
for (int i = 0; i < size; ++i) {
m_stackPush.push(m_stackPop.top());
m_stackPop.pop();
}
m_stackPush.push(val);
}
T peek() {
AlltoPopStack();
assert(m_stackPop.empty() == false);
return m_stackPop.top();
}
T poll() {
AlltoPopStack();
assert(m_stackPop.empty() == false);
T ret = m_stackPop.top();
m_stackPop.pop();
return ret;
}
int count() {
return m_stackPop.empty()==false ? m_stackPop.size() : m_stackPush.size();
}
};
??另外的一個(gè)效率更高的思路是牌借，push的時(shí)候盡管往stackPush中push，不受stackPop干擾割按，而在pop和peek的時(shí)候膨报，只要stackPop不為空，那就peek或pop stackPop就行了适荣，而一旦為空才把stackPush的所有元素裝入 stackPop现柠，生產(chǎn)消費(fèi)者思想。
代碼：
#include <assert.h>
#include <stack>
using namespace std;
template<class T>
class DoubleStackQueue {
stack<T> m_stackPush;
stack<T> m_stackPop;
private:
inline void AlltoPopStack() {
int size = m_stackPush.size();
if(m_stackPop.empty())
for (int i = 0; i < size; ++i) {
m_stackPop.push(m_stackPush.top());
m_stackPush.pop();
}
}
public:
void push(const T val) {
m_stackPush.push(val);
}
T peek() {
AlltoPopStack();
assert(m_stackPop.empty() == false);
T ret = m_stackPop.top();
return ret;
}
T poll() {
AlltoPopStack();
assert(m_stackPop.empty() == false);
T ret = m_stackPop.top();
m_stackPop.pop();
return ret;
}
int count() {
return m_stackPop.size() + m_stackPush.size();
}
};
