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

96 阅读 0 评论 64 点赞

我是靠谱客的博主发嗲项链，这篇文章主要介绍队列（一）——队列的数组实现方式，现在分享给大家，希望可以做个参考。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#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;
}