队列-队列的顺序表示和实现

原创
2014/05/22 20:29
阅读数 1.2K

队列-队列的顺序表示和实现

参考:http://kjwy.5any.com/sjjg/content/sjjg03/030403d.htm

和顺序栈相类似,在利用顺序分配存储结构实现队列时,除了用一维数组描述队列中数据元素的存储区域之外,尚需设立两个指针front和rear分别指示“队头”和“队尾”的位置。

为了在C语言中描述方便,在此我们约定:初始化建空队列时,令front=rear=0。每当插入新的队列尾元素时,“尾指针增1”;每当删除队列头元素时,“头指针增1”。因此,在非空队列中,头指针始终指向队列头元素位置,队尾指针始终指向队列尾元素的下一个位置。如图所示:

 

        

从图中可以看到,随着入队出队的进行,会使整个队列整体向后移动,这样就出现了循环队列操作示意图(d)中的现象(假溢出现象):队尾指针已经移到了最后,再有元素入队就会出现溢出,而事实上此时队中并未真的“满员”,这种现象为“假溢出”,这是由于“队尾入队头出”这种受限制的操作所造成。解决假溢出的方法之一是将队列看成头尾相接的循环结构,头尾指针的关系不变,将其称为“循环队列”,“循环队列”的示意图如下图所示:

因为是头尾相接的循环结构,

入队时的队尾指针加1操作修改为:q.rear=(q.rear+1) % MAXSIZE;

出队时的队头指针加1操作修改为:q.front=(q.front+1) % MAXSIZE;

设MAXSIZE=10,下图是循环队列操作示意图。

如上图所示的循环队可以看出,(a)中具有a5、a6、a7、a8四个元素,此时front=5,rear=9;随着a9~a14相继入队,队中具有了10个元素--队满,此时front=5,rear=5,如(b)所示,可见在队满情况下有:front==rear。若在(a)情况下,a5~a8相继出队,此时队空,front=9,rear=9,如(c)所示,即在队空情况下也有:front==rear。就是说“队满”和“队空”的条件是相同的了。这显然是必须要解决的一个问题。

方法之一是附设一个存储队中元素个数的变量如num,当num==0时队空,当num==MAXSIZE时为队满。

另一种方法是少用一个元素空间,把图(d)所示的情况就视为队满,此时的状态是队尾指针加1就会从后面赶上队头指针,这种情况下队满的条件是:(q->rear+1) % MAXSIZE == q->front,也能和空队区别开。

 

队列的顺序存储结构

typedef struct {
	QElemtype *base;//初始化的动态分配存储空间
	int front;//队头指针
	int rear;//队尾指针
}SqQueue;

 

循环队列的实现

下面的循环队列及操作按第二种方法实现。

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10

#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef int QElemtype;

typedef struct {
	QElemtype *base;//初始化的动态分配存储空间
	int front;//队头指针
	int rear;//队尾指针
}SqQueue;//循环队列
//--------------------循环队列的基本操作的算法描述------------------
Status InitQueue(SqQueue *q)
{//构造一个空队列Q
	q->base=(QElemtype*)malloc(MAXSIZE*sizeof(QElemtype));
	if(!q->base)exit(OVERFLOW);//存储分配失败
	q->front= q->rear =0;
	return OK;
}

int queuelength(SqQueue q)
{//返回Q的元素个数,即队列的长度
	return (q.rear - q.front + MAXSIZE) % MAXSIZE;
}

Status EnQueue (SqQueue *q,QElemtype e)
{//插入元素e为Q的新的队尾元素
	if ((q->rear+1) % MAXSIZE == q->front) return ERROR;//队列满,不进行任何操作,不能再入队
	q->base[q->rear]=e;
	//入队的操作
	q->rear=(q->rear+1) % MAXSIZE;
	return OK;
}

Status DeQueue (SqQueue *q,QElemtype *e)
{//若队列不空,则删除Q的对头元素,用e返回其值,并返回OK;否则返回ERROR
	if (q->front==q->rear) return ERROR;//队列满
	*e=q->base[q->front]; //指针的下标运算
	q->front=(q->front+1) % MAXSIZE;
	return OK;
}

void display_queue(SqQueue *q){
	if(q->front==q->rear){
		printf("queue is empty!!\n");
	}else {
		//遍历该循环队列
		int front = q->front;
		int rear = q->rear;
		while(front!=rear){
			printf("%d\n",q->base[front]);
			++front;
		}
	}
	
}

int main(){
	SqQueue q;
	InitQueue(&q);
	int i;
	for(i=0;i<11;i++){
		if(EnQueue(&q,i)==ERROR){
			printf("循环队列已满,该队列长度为9 \n");
		}
	}
	printf("the length of queue is %d \n",queuelength(q)); //the length of queue is 9
	int e1,e2,e3,e4,e5;
	DeQueue(&q,&e1);
	DeQueue(&q,&e2);
	DeQueue(&q,&e3);
	DeQueue(&q,&e4);
	DeQueue(&q,&e5);
    printf("%d--%d--%d--%d--%d \n",e1,e2,e3,e4,e5);
	printf("the length of queue is %d \n",queuelength(q));
	printf("循环队列的遍历\n");
	display_queue(&q);
	int e6;
	DeQueue(&q,&e6);
	printf("循环队列的遍历\n");
	display_queue(&q);
	system("pause");
	return 0;
}

运行结果:

循环队列已满,该队列长度为9
循环队列已满,该队列长度为9
the length of queue is 9
0--1--2--3--4
the length of queue is 4
循环队列的遍历
5
6
7
8
循环队列的遍历
6
7
8
请按任意键继续. . .

 

注:数学中的余数其实就是取模运算

如,m模n (c语言表示 m%n )

  x mod y = x % y

数学中的余数概念和我们的计算机中的余数概念一致,但实现却不一致。

========END========

展开阅读全文
打赏
0
2 收藏
分享
加载中
更多评论
打赏
0 评论
2 收藏
0
分享
返回顶部
顶部