队列是先进先出的数据结构,栈时先进后出的数据结构,可以使用栈和队列模拟彼此。
使用C++泛型编程,栈使用STL的stack容器适配器。
主要思想:
与“两个队列模拟栈”不同:这个问题中,在某个状态下两个栈可能都不为空。
(1)向队列插入:一律插入stack1中。
(2)从队列取数:如果stack2不为空,直接从stack2中弹出一个元素;
如果stack2为空,那么将stack1中所有元素弹出并插入stack2,然后从stack2中pop一个。
template <typename T>
class CQueue
{
public:
void display();
// 在队列末尾添加一个结点
void appendTail(const T& node);
// 删除队列的头结点
void deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
template<typename T>
void CQueue<T>::display() {
stack<T> sq1(stack1);
stack<T> sq2(stack2);
while (sq2.size() > 0) {
cout << sq2.top() << " ";
sq2.pop();
}
while (sq1.size() > 0) {
T data = sq1.top();
sq1.pop();
sq2.push(data);
}
while (sq2.size() > 0) {
cout << sq2.top() << " ";
sq2.pop();
}
cout << endl;
}
template<typename T>
void CQueue<T>::appendTail(const T& element)
{
stack1.push(element);
}
template<typename T>
void CQueue<T>::deleteHead()
{
if(stack2.size()<= 0)
{
while(stack1.size()>0)
{
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
if (stack2.size() > 0)
stack2.pop();
return;
}
《剑指offer》中deleteHead函数返回被删除的元素,我认为没必要,因为STL中queue队列的删除返回就是void。当对空queue进行pop操作时,在VS2010下运行时会提示下图所示内容,但是g++下不会有任何提示,程序正确。
测试:
int main() {
CQueue<int> cq;
cq.appendTail(1);
cq.appendTail(2);
cq.appendTail(3);
cq.appendTail(4);
cq.display();
cq.deleteHead();
cq.deleteHead();
cq.display();
cq.appendTail(5);
cq.appendTail(6);
cq.display();
}