【题目】
编写一个类，用两个栈实现队列，支持队列的基本操作（add、poll、peek）。
有一个简单，但不是最优解的思路，如下图，在push的时候，如果stackPop中不为空就把stackPop中的所有元素push到stackPush中，最后再往stackPush中push新值，此时stackPop一定为空了。peek或者poll，就把stackPush中的所有元素push到stackPop中，此时stackPush为空了，同时只会出现其中一个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();
}
};
网友评论