数组实现的循环队列

队列是一种常见的数据结构,是一个特殊的有序表,起插入操作都在表的一端进行,而删除操作都在表的另外一端进行,所以队列也称先进先出(FIFO)表。可以基于链表实现也可以基于数组实现。我们现在讲基于数组实现,队列的结构如下:

[cpp]
struct Queue {
T *queue; /* 存储用的数组 */
int capacity; /* 存放个数 */
int front ; /* 指向队首 */
int rear; /* 指向队尾 */
};
[/cpp]

基于数组实现的线性队列很好实现,但这种顺序存储表示存在缺陷,很显然,随着时间的推移,队列逐渐右移。这意味着队列尾下标最终等于MAX_QUEUE_SIZE – 1,说明队列已满,此时需要把整个队列向左移动,使得第一个元素再次位于queue[0],切front = -1,同时还要重新计算rear,使其处在正确的位置上。数组的移动开销很大,特别是当队列中包含大量元素时。

如果将数组queue[MAX_QUEUE_SIZE ]看成是循环的,那么我得到一种更有效的存储表示。这就是循环队列了。

由于必须班长下标front和rear能够循环移动,所以实现循环队列的插入和删除操作要稍微困难些,通常利用模运算可以达到此目的,在插入操作是,队尾下标的循环移动实现语句为:

rear  = (rear + 1)%MAX_QUEUE_SIZE ;

注意在插入时,首先循环移动rear,然后将元素存入队列queue[rear],类似的,在删除过程中,首先用下面语句循环移动front:

front= (front+ 1)%MAX_QUEUE_SIZE ;

然后再删除元素。

下面我们给出c++的实现:

[cpp]
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>

/*
* 功能:数组实现的循环队列,C++实现,供学习
*/

using namespace std;

template <typename T>
class CircleQueue {
private:
T *queue; /* 存储用的数组 */
int capacity; /* 存放个数 */
int front ; /* 指向队首 */
int rear; /* 指向队尾 */
public:
CircleQueue( int a ); /* 无参构造 */
CircleQueue(); /*有参构造 */
~CircleQueue(); /* 析构 */
bool isEmpty(); /* 判断空 */

int getSize(); /* 返回个数 */

bool push( T a ); /* 入队 */

T pop(); /* 出队 */

};

template<typename T>
CircleQueue<T>::CircleQueue( int a ) : front ( 0 ),
rear( 0 ), capacity( a ), queue( NULL )
{
queue = new T[capacity];
}
template<typename T>
CircleQueue<T>::CircleQueue() : CircleQueue( 10 )
{
};
template<typename T>
CircleQueue<T>::~CircleQueue()
{
delete[] queue;
}
template<typename T>
bool CircleQueue<T>::isEmpty()
{
if ( front == rear )
return(true);
else
return(false);
}
template<typename T>
int CircleQueue<T>::getSize()
{
return( (rear – front + capacity) % capacity);
}
template<typename T>
bool CircleQueue<T>::push( T a )
{
if ( (rear + 1) % capacity == front )
{
cout<<"queue is full"<<endl;
return(false);
}

queue[rear] = a;
rear = (rear + 1) % capacity;
return(true);
}
template<typename T>
T CircleQueue<T>::pop()
{
if ( rear == front)
{
cout<<"queue is empty"<<endl;
return NULL;
}

T elem;
elem = queue[front];
front = (front + 1) % capacity;
return elem;
}

int main()
{
CircleQueue<string> queue( 6 );
queue.push( "one" );
queue.push( "two" );
queue.push( "three" );
queue.push( "four" );
queue.push( "five" );
queue.push( "six" );//报满
cout << "队列长度" << queue.getSize() << endl;
while ( !queue.isEmpty() )
{
cout << queue.pop() << endl;
}
getchar();
return(0);
}
[/cpp]

运行输出:

queue is full
队列长度5
one
two
three
four
five