用2个栈实现队列

下面这段代码是我定义的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种方法：