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

队列（一）——队列的数组实现方式

2024-07-15 17:24:01   220人阅读

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;
}

程序运行截图：


联系
我们