队列举例

队列举例

【例1】 假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(enqueue)和删除(dlqueue)元素的操作。 【解答】

循环队列类定义

template class Queue { public:

Queue ( int=10 );

~Queue ( ) { delete [ ] elements; } int EnQueue ( Type & item ); Type *DeQueue ( ); Type *GetFront ( );

void MakeEmpty ( ) { length = 0; }

//置空队列 //判队列空否 //判队列满否

int IsEmpty ( ) const { return length == 0; } private:

int rear, length; int maxSize; }

template

Queue:: Queue ( int sz ) : rear (maxSize-1), length (0), maxSize (sz) {

//建立一个最大具有maxSize个元素的空队列。 elements = new Type[maxSize];

//创建队列空间

//队尾指针和队列长度 //存放队列元素的数组 //队列最大可容纳元素个数

Type *elements;

//循环队列的类定义

int IsFull ( ) const { return length == maxSize; }

构造函数

if (elements == NULL)

{cerr<<\动态存储分配失败!\endl;exit (1);}

}

template

int Queue :: EnQueue ( Type &item ) {

}

template

Type *Queue :: DeQueue ( ) {

插入函数

if (IsFull ( )) {cerr<<\队列已满，不能入队列!\endl; return 0;} //判队列满则

length++;

//长度加1 //队尾位置进1 //进队列

出错处理

rear = ( rear +1) % maxSize; elements[rear] = item;

return 1;

删除函数

if (IsEmpty ( ))return NULL; //判断队列是否为空，空则返回NULL

length--;

//队列长度减1

1

return &elements[(rear-length+maxSize) % maxSize];

}

template

Type *Queue :: GetFront ( ) {

}

//返回原队头元素的地址

读取队头元素值函数

if (IsEmpty ( ))return NULL; //判断队列是否为空，空则返回NULL

return &elements[(rear-length+1+maxSize) % maxSize];

//返回队头元素的地址

【例2】 假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。 【解答】

循环队列类定义

template class Queue { public:

Queue ( int=10 ); ~Queue ( ) { delete [ ] Q; } int EnQueue ( Type & item ); Type *DeQueue ( ); Type *GetFront ( );

void MakeEmpty ( ) { front = rear = tag = 0; }

//置空队列

//判队列空否

int IsEmpty ( ) const { return front == rear && tag == 0; } private:

int rear, front, tag; Type *Q; int m; }

template

Queue:: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) {

//建立一个最大具有m个元素的空队列。 Q = new Type[m];

//创建队列空间

//队尾指针、队头指针和队满标志

//存放队列元素的数组 //队列最大可容纳元素个数

//循环队列的类定义

int IsFull ( ) const { return front == rear && tag == 1; } //判队列满否

构造函数

if (Q == NULL)

{cerr<<\动态存储分配失败!\endl;exit (1);}

}

template

int Queue :: EnQueue ( Type &item ) {

插入函数

if (IsFull ( )) {cerr<<\队列已满，不能入队列!\endl; return 0;} //判队列满则

rear = ( rear + 1 ) % m; Q[rear] = item;

//队尾位置进1, 队尾指针指示实际队尾位置 //进队列

出错处理

2

}

tag = 1; //标志改1，表示队列不空，因为入队只会变满

return 1;

位置

删除函数

template

Type *Queue :: DeQueue ( ) {

if (IsEmpty ( ))return NULL; //判断队列是否为空，空则返回NULL

front = ( front + 1 ) % m; tag = 0;

//队头位置进1, 队头指针指示实际队头的前一//标志改0, 表示栈不满，因为出队只会变空

//返回原队头元素的地址

return &Q[front];

}

template

读取队头元素函数

Type *Queue :: GetFront ( ) { }

if (IsEmpty ( ))return NULL; //判断队列是否为空，空则返回NULL

return &Q[(front + 1) % m];

//返回队头元素的地址

【例3】 若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入(enqueue)和删除(dequeue)算法，并给出p为何值时队列空。 【解答】 链式队列的类定义

template class Queue { public:

Queue ( ) : p ( NULL ) { } ~Queue ( );

//构造函数

//将item加入到队列中 //删除并返回队头元素 //查看队头元素的值

//置空队列，实现与~Queue ( ) 相同

//析构函数

//链式队列类定义

template class Queue; friend class Queue; private: Type data; public:

QueueNode ( Type d = 0, QueueNode *l = NULL ) : data (d), link (l) { } };

//构造函数

//数据域 //链域

QueueNode *link;

//链式队列类的前视定义 //链式队列结点类定义

template class QueueNode {

void EnQueue ( const Type & item ); Type DeQueue ( ); Type GetFront ( );

void MakeEmpty ( ); private:

QueueNode *p;

int IsEmpty ( ) const { return p == NULL; }

//判队列空否

//队尾指针（在循环链表中）

3

};

template Queue::~Queue ( ) { QueueNode *s;

while ( p != NULL ) { s = p; p = p->link; delete s; } //逐个删除队列中的结点 }

template

void Queue::EnQueue ( const Type & item ) {

if ( p == NULL ) { }

//队列不空, 新结点链入p之后 //结点p指向新的队尾

QueueNode *s = new QueueNode ( item, NULL ); s->link = p->link; p = p->link = s;

//队列空, 新结点成为第一个结点

//队列的析构函数

队列的析构函数

队列的插入函数

p = new QueueNode ( item, NULL ); p->link = p;

else {

}

}

队列的删除函数

template Type Queue::DeQueue ( ) {

if ( p == NULL ) { cout << \队列空, 不能删除！\endl; return 0; } if (p->link==p) {

Type retvalue = p->data; delete p; 为空

p=NULL; }

return retvalue;

//返回数据

//若为唯一一个结点，则删除后队列

点

QueueNode *s = p->link;

p->link = s->link; }

//队头结点为p后一个结点

//重新链接, 将结点s从链中摘下 //保存原队头结点中的值, 释放原队头结//返回数据

Type retvalue = s->data; delete s; return retvalue;

队空条件 p == NULL。

4