首页 > 代码库 > 队列(一)——队列的数组实现方式

队列(一)——队列的数组实现方式

1.队列的概念
队列是一种特殊的线性表,仅仅同意在队列的一端进行插入而在还有一端进行删除。
队列一般拥有队首(front指针)和队尾(rear指针)。当一个队列并未存入数据的时候,front和rear指针均指向队首。
入队的操作:rear后移,存入数据在rear指向的单元,队满不可入队,这同一时候也表明front总是指向队首元素的前驱。
出队的操作:front后移,元素出队,队空不可出队。


注意:在这样的队列的实现方式下。浪费了一个单元,可是这样能够保证队满和队空是不同的条件来推断。
2.队列空和队列满
队列空:front = rear
队列满:rear的下一个单元就是front
3.队列的数组实现方式

#include <stdio.h>
#include <malloc.h>

typedef struct sq
{
	int maxsize;
	int front, rear;
	int *quence;
}Qs;

void init_quence(Qs *s, int ms) /*初始化队列*/
{
	s->maxsize = ms;
	s->quence = (int *)malloc(ms*sizeof(int));
	s->front = s->rear = 0;
}

void in_quence(Qs *s, int val) /*入队函数*/
{
	if((s->rear+1)%s->maxsize == s->front)
	{
		printf("Quence is full.\n");
		return;
	}
	s->rear = (s->rear+1)%s->maxsize;
	s->quence[s->rear] = val;
}

int out_quence(Qs *s) /*出队函数*/
{
	if(s->rear != s->front)
	{
		s->front = (s->front+1)%s->maxsize;
		return s->quence[s->front];
	}
}

void print_quence(Qs *s) /*打印队列中元素*/
{
	int i;
	i = s->front;

	if(s->rear == s->front)
		return;
	do
	{
		printf("%d ", s->quence[(i+1)%s->maxsize]);
		i = (i+1)%s->maxsize;
	}while(i != s->rear);
}

void clear_quence(Qs *s) /*清除队列*/
{
	free(s->quence);
	s->quence = 0;
	s->maxsize = 0;
	s->front = s->rear = 0;
}

int count_quence(Qs *s) /*统计队列个数*/
{
	int i, count = 0;

	i = s->front;
	if(s->rear == s->front)
		return 0;
	do
	{
		count ++;
		i = (i+1)%s->maxsize;
	}while(i != s->rear);
	return count;
}

int main()
{
	Qs s;
	int i;
	int dat[7] = {1, 2, 3, 4, 5, 6, 7};

	init_quence(&s, 7);
	for(i = 0; i < 7; i++)
	{
		in_quence(&s, dat[i]);
		printf("Quence number is: %d. ", count_quence(&s));
		print_quence(&s);
		printf("\n");
	}
	printf("Out quence number is: %d.\n", out_quence(&s));
	print_quence(&s);
	clear_quence(&s);
	return 0;
}

程序执行截图:

技术分享

队列(一)——队列的数组实现方式