数据结构 &栈和队列（二）

队列是一种先进先出的线性表，只允许在表的一端进行插入另一端进行删除。允许插入的一端称为队尾，允许删除的一端称为队头。

同样的我们先来设计队列的结构：

typedef int ElemType;//类型重定义
#define MAXSIZE 10//队列的最大容量为10
typedef struct Queue
{
	ElemType *base;
	int head;//队头
	int rear;//队尾
}Que,*pQue;
1
2
3
4
5
6
7
8

和栈一样，对一个空队列（不存在的队列）进行操作是毫无意义的，因此在进行所有操作之前需要对队列进行判空。

static void DeterPointIsNull(pQue que)
{
	assert(que!=NULL);
	if(que==NULL)
	{
		printf("error\n");
	}
	exit(0);//退出
}
1
2
3
4
5
6
7
8
9

接下来我们对队列进行初始化：

void Initqueue(pQue que)
{
	DeterPointIsNull(que);
	que->base=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);//为队列开辟空间
	que->head=que->rear=0;//初始时队中没有元素
}
1
2
3
4
5
6

判断队列是否为空：如果队头变量的值和队尾变量的值相等，此时队列为空队列。

int Emptyque(pQue que)
{
	DeterPointIsNull(que);
	if(que->head==que->rear)
	{
		return 1;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9

除了判空，还有给队列判满操作：

int Fullque(pQue que)
{
	DeterPointIsNull(que);
	if((que->rear+1)/MAXSIZE==que->head)
	{
		return 1;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9

在这里我们解释一下判满的条件，由于队列的大小是固定的，依次从下面两个例子中我们就可以很容易发现判断队列满的条件是如何来的了。

接着我们完成入队列的操作：

int Pushque(pQue que,ElemType val)
{
	DeterPointIsNull(que);
	if(Fullque(que))
	{
		return 0;
	}
	que->base[que->rear]=val;
	que->rear=(que->rear+1)%MAXSIZE;
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11

获得队头元素：

int GetHead(pQue que,ElemType *val)
{
	DeterPointIsNull(que);
	if(Emptyque(que))
	{
		return 0;
	}
	*val=que->base[que->head];
	return 1;
}
1
2
3
4
5
6
7
8
9
10

出对列操作：

int Popque(pQue que,ElemType *val)
{
	DeterPointIsNull(que);
	if(!GetHead(que,val))
	{
		return 0;
	}
	que->head=(que->head+1)%MAXSIZE;
	return 1;
}
1
2
3
4
5
6
7
8
9
10

当我们不需要队列时，需要对队列进行销毁，操作如下：

void Destroy(pQue que)
{
	DeterPointIsNull(que);
	free(que->base);
	que->base=NULL;
	que->head=que->rear=0;
}
1
2
3
4
5
6
7