2.2.2. 队列的存储实现及运算实现

1. 顺序队
顺序存储的队称为顺序队。因为队的队头和队尾都是活动的，因此，除了队列的数据区外还有队头、队尾两个指针。顺序队的类型定义如下：


显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。

如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列"空"还是"满"。解决此问题的方法至少有三种：其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。

>" src="http://i1.w.hjfile.cn/doc/200811/32502.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/32502.gif">>" src="http://i1.w.hjfile.cn/doc/200811/26508.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/26508.gif">>" src="http://i1.w.hjfile.cn/doc/200811/52955.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/52955.gif">>" src="http://i1.w.hjfile.cn/doc/200811/71602.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/71602.gif">>" src="http://i1.w.hjfile.cn/doc/200811/11087.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/11087.gif">