下面这段代码是我定义的Stack类模板，接下来介绍几种用2个该Stack类实现队列Queue的几种方法。
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：主机域名、虚拟空间、营销软件、网站建设、阿拉善盟网站维护、网站推广。
template
class Stack
{
public:
Stack();
Stack(const Stack &st);
Stack &operator=(const Stack &st);
~Stack();
public:
void Push(const T &data);
void Pop();
T &Top();
T &End();
bool Empty();
size_t Size();
void Print();
protected:
void CheckCapacity();
protected:
T *_arr;
size_t _top;
size_t _capacity;
};
声明：为了实现除“入队”“出队”之外更多的功能，比如“打印”等，我将上面那个已造好的“轮子”Stack做了扩展，增加了一些成员方法。而如果你关注的重点是push和pop的算法，那么其实并不需要在意我造的下面这个“轮子”。可以直接跳过下面的代码，并把所有我使用的Stack类型当作库里的stack即可.
扩展后的Stack:
template
class Stack
{
public:
Stack()
:_arr(NULL)
, _top(0)
, _capacity(0)
{}
Stack(const Stack &st)
:_arr(new T[st._capacity])
, _top(st._top)
, _capacity(st._capacity)
{
for (size_t i = 0; i < _capacity; i++)
{
_arr[i] = st._arr[i];
}
}
Stack &operator=(const Stack &st)
{
if (st._arr != _arr)
{
delete[] _arr;
_arr = new T[st._capacity];
for (size_t i = 0; i < st._capacity; i++)
{
_arr[i] = st._arr[i];
}
_top = st._top;
_capacity = st._capacity;
}
return *this;
}
~Stack()
{
if (_arr != NULL)
{
delete[] _arr;
}
}
public:
void Push(const T &data)
{
CheckCapacity();
_arr[_top] = data;
++_top;
}
void Pop()
{
--_top;
}
T &Top()
{
return _arr[_top - 1];
}
T &End()
{
return _arr[0];
}
bool Empty()
{
if (0 == _top)
{
return true;
}
else
{
return false;
}
}
size_t Size()
{
return _top;
}
void Print()
{
for (size_t i = 0; i < _top; i++)
{
cout << _arr[i] << " ";
}
cout << endl;
}
void RePrint()
{
if (0 == _top)
{
return;
}
for (int i = _top - 1; i >= 0; i--)
{
cout << _arr[i] << " ";
}
cout << endl;
}
protected:
void CheckCapacity()
{
if (_top == _capacity)
{
_capacity = _capacity + 3;
T *tmp = new T[_capacity];
for (size_t i = 0; i < _top; i++)
{
tmp[i] = _arr[i];
}
delete[] _arr;
_arr = tmp;
}
}
protected:
T *_arr;
size_t _top;
size_t _capacity;
};
--------------------------------------------------------------------------------
一、普通版本
栈的特点是“先入后出”，而队列的特点是“先入先出”。
所以可以定义一个类Queue,包含2个成员对象：
一个栈_stack1存放数据，另一个栈_stack2用来临时存放数据，通过一些压栈出栈的成员方法就可以实现对队列的入队、出队操作。
实现的2个栈组成的队列如下图所示，现在要将一组数据【1 2 3 4 5】放入队列中：
先将这组数依次压入_stack1中，然后再将_stack1中的元素依次出栈压入_stack2中：
这时候，_stack2中的元素依次出栈，就相当于队列的出队操作了。
用代码实现：
定义一个类模板Queue:
template
class Queue
{
Queue()
:_size(0)
{}
void Push(const T &data) //入队
{
_stack1.Push(data);
++_size;
}
void Pop() //出队
{
Converse(_stack2, _stack1);
_stack2.Pop();
Converse(_stack1, _stack2);
--_size;
}
protected:
void Converse(Stack &dst, Stack &src) //src->dst
{
while (size--)
{
dst.Push(src.Top());
src.Pop();
}
}
protected:
Stack _stack1;
Stack _stack2;
size_t _size;
};
其中，
成员方法Converse():作用是将栈src中的内容依次出栈，压入栈dst中。
成员方法Push（） :入队操作，每次将元素data存入成员对象_stack1中。
成员方法Pop() :出队操作，弹出第一个送入的元素。其中，第二个Converse的作用是还原。
可以看出，这种入队、出队的算法，需要保证元素始终在_stack1中维护，而只有在出栈的时候用到_stack2临时存放数据。
采用这种方式实现的队列，可以实现正常的入队、出队操作，但应该注意到，其中出队操作需要进行两次压栈，我们可以对一个细节稍作优化，进一步提高出队操作的执行效率。
下图为优化后的出队操作：
区别在于，在出队操作时，将_stack1中的(_size - 1)个元素弹出并压入_stack2中。
弹出后，也不需要将_stack2的元素“倒回”_stack1中。
二、代码优化
具体的实现步骤为：
出队操作时：
而是在每次执行出队的时候进行一次判断：
若_stack2为空，则将_stack1中的(_size - 1)个元素弹出并压入_stack2中，并弹出_stack中剩下的那个元素（就是我上面说的那个步骤）；
若_stack2不为空，则弹出_stack2中最顶层的元素。
在入队操作时，判断_stack1是否为空：
若为空，则先将_stack2中的元素依次弹出并压入_stack1中，然后再将入栈元素压入_stack1中（左图）
否则，直接将入栈元素压入_stack1中
优化后的方案用代码实现如下：
template
class queue
{
public:
queue()
:_size(0)
{}
queue(const queue &que)
{
_stack1 = que._stack1;
_size = que._size;
}
public:
void Push(const t &data)
{
if (_stack1.Empty() && !_stack2.Empty())
{
Converse(_stack1, _stack2);
}
_stack1.Push(data);
++_size;
}
void Pop()
{
if (_stack2.Empty())
{
if (_stack1.Empty())
{
return;
}
RemainConverse(_stack2, _stack1);
_stack1.Pop();
}
else
{
_stack2.Pop();
}
--_size;
}
void Print()
{
_stack1.Print();
_stack2.RePrint();
}
bool Empty()
{
return (0 == _size);
}
t& Front()
{
if (_stack1.empty())
{
return _stack2.top();
}
else
{
return _stack1.end();
}
}
t& Back()
{
if (_stack1.Empty())
{
return _stack2.End();
}
else
{
return _stack1.Top();
}
}
size_t Size()
{
return _size;
}
protected:
void RemainConverse(Stack &dst, Stack &src)
{
size_t count = src.Size() - 1;
while (count--)
{
dst.Push(src.Top());
src.Pop();
}
}
void Converse(Stack &dst, Stack &src) //src->dst
{
while (!src.Empty())
{
dst.Push(src.Top());
src.Pop();
}
}
protected:
Stack _stack1;
Stack _stack2;
size_t _size;
};
int main()
{
queue que1;
que1.Push(1);
que1.Push(2);
que1.Push(3);
que1.Push(4);
que1.Print();
que1.Pop();
que1.Print();
que1.Push(5);
que1.Print();
return 0;
}
到目前我们已经实现了2种不同的方式实现这个队列。
这两种方法相比，第一种方法每次进行出队操作都要移动2次栈中的全部数据
而对于第二种方法实现的队列，如果连续进行入队或者出队操作，则不需要移动2个栈中的数据，能一定程度上提高效率。
三、进一步优化
可以看出，_stack1和_stack2中全部元素（或者说，全部元素-1）转移的次数越少，程序的执行效率就越高。
还有一种方法可以进一步减少_stack1和_stack2中全部元素交换的次数：
出队：
检测_stack2是否为空：
若为空，则将_stack1中的元素依次弹出并压入_stack2中，
若不为空，则弹出_stack2中栈顶的元素
入队：
将元素压入_stack。
可以看出，这种实现方式入队永远是从_stack2中弹出元素，出队永远是向_stack1中压入元素
而只有当入栈时检测到_stack2为空时，才执行2个栈之间全部元素的转移。
用如下的图能更形象地表示：
实现代码如下：
template
class Queue
{
public:
Queue()
:_size(0)
{}
Queue(const Queue &que)
{
_stack1 = que._stack1;
_size = que._size;
}
public:
void Push(const T &data)
{
_stack1.Push(data);
++_size;
}
void Pop()
{
if (_size == 0) //异常
{
return;
}
if (_stack2.Empty())
{
Converse(_stack2, _stack1);
}
_stack2.Pop();
--_size;
}
void Print()
{
_stack2.RePrint();
_stack1.Print();
}
bool Empty()
{
return (0 == _size);
}
T& Front()
{
if (_stack2.Empty())
{
return _stack2.End();
}
else
{
return _stack2.Top();
}
}
T& Back()
{
return _stack1.Top();
}
size_t Size()
{
return _size;
}
protected:
void Converse(Stack &dst, Stack &src)
{
while (!src.Empty())
{
dst.Push(src.Top());
src.Pop();
}
}
protected:
Stack _stack1;
Stack _stack2;
size_t _size;
};
四、总结
这里一共提供了3种方法：
分享标题：用2个栈实现队列
文章源于：
http://cdxtjz.com/article/jjoihi.html
