线性表7：队列的顺序存储——顺序队列_用顺序存储实现队列的基本操作,如创建、判空、判满、入队和出队等操作,如要做成循

从数据结构角度看，栈和队列也是线性表，只不过是操作受限的线性表。

队列：操作限制在两端的线性表，一端进行插入操作，称为队尾；另一端进行删除操作，称为队头。

顺序队列，又称之为循环队列，将队列循环处理，是为避免假溢出。下文的顺序队列都代表循环队列。
假溢出现象：队列里明明是有空间，但是不能再进行入队操作。

1.队列的特点

先进先出(FIFO)
存储：顺序存储、链式存储

2.顺序队列的描述

**描述：**数组+front指针+rear指针
front保存队头的前一个位置，rear保存队尾的下标

#define MAXSIZE 100

typedef int datatype;
typedef struct 
{
	datatype data[MAXSIZE];
	int front;//始终指向队首的前一个位置
	int rear;//始终指向队尾
}sequeue;
1
2
3
4
5
6
7
8
9

3.基本操作

3.1创建空顺序队列

sequeue * createSeQueue()
{
	//1.申请空间
	sequeue * Q = (sequeue *)malloc(sizeof(sequeue));
	if(NULL == Q)
	{
		printf("create: malloc fail\n");
		return NULL;
	}

	//2.初始化
	Q->front = Q->rear = MAXSIZE-1;

	return Q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.2判空

int isEmptySeQueue(sequeue * Q)
{
	return (Q->front == Q->rear)?1:0;
}
1
2
3
4

3.3判满

int isFullSeQueue(sequeue * Q)
{
	return ((Q->rear+1)%MAXSIZE == Q->front)?1:0;
}
1
2
3
4

3.4入队

int inSeQueue(sequeue * Q, datatype x)
{
	//非满则入队
	if(isFullSeQueue(Q))
	{
		printf("队列已满\n");
		return -1;
	}

	//入队操作rear
	Q->rear = (Q->rear+1)%MAXSIZE;
	Q->data[Q->rear] = x;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.5出队

int OutSeQueue(sequeue * Q, datatype *x)
{
	//非空则出队
	if(isEmptySeQueue(Q))
	{
		printf("队列是空\n");
		return -1;
	}

	//出队操作front
	Q->front = (Q->front+1)%MAXSIZE;
	*x = Q->data[Q->front];

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.6打印输出

void showSeQueue(sequeue * Q)
{
	int i = 0;
	for(i = (Q->front+1)%MAXSIZE; i != (Q->rear+1)%MAXSIZE; i = (i+1)%MAXSIZE)
	{
		printf("%d ", Q->data[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9

测试

	int i;
	sequeue * Q = createSeQueue();
	if(NULL == Q)
		return -1;

	for(i = 0; i < 10; i++)
	{
		if(!isFullSeQueue(Q))
			inSeQueue(Q, i);
	}
#if 0	//测试出队
	datatype x;
	while(!isEmptySeQueue(Q))
	{
		OutSeQueue(Q, &x);
		printf("%d ", x);
	}
	printf("\n");
#endif

	showSeQueue(Q);

    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