【題目】
編寫一個類，用兩個棧實現(xiàn)隊列，支持隊列的基本操作（add、poll、peek）。
??有一個簡單，但不是最優(yōu)解的思路，如下圖，在push的時候，如果stackPop中不為空就把stackPop中的所有元素push到stackPush中，最后再往stackPush中push新值，此時stackPop一定為空了。peek或者poll，就把stackPush中的所有元素push到stackPop中，此時stackPush為空了，同時只會出現(xiàn)其中一個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();
}
};
??另外的一個效率更高的思路是，push的時候盡管往stackPush中push，不受stackPop干擾，而在pop和peek的時候，只要stackPop不為空，那就peek或pop stackPop就行了，而一旦為空才把stackPush的所有元素裝入 stackPop，生產消費者思想。
代碼：
#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();
}
};
