队列的顺序存储与链式存储_队列是顺序存储还是链式存储

队列的基本概念

队列的定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

 队头（Front）：允许删除的一端，又称队首。
队尾（Rear）：允许插入的一端。
空队列：不包含任何元素的空表。

队列的常见基本操作

InitQueue：初始化队列，构造一个空队列Q。
QueueEmpty：判队列空，若队列Q为空返回true，否则返回false。
pushQueue：入队，若队列Q未满，将新的值加入，使之成为新的队尾。
popQueue：出队，若队列Q非空，删除队头元素，并返回。
GetHead：读队头元素，若队列Q非空，则将队头元素赋值给返回。

队列的顺序存储

设计思想：

        队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front指向队头元素，队尾指针 rear 指向队尾元素的下一个位置。

顺序队列

typedef  int   mytype;
typedef struct  seqQueue
{
	int rear, front;
	mytype  data[N];
}*SQ;

初始状态（队空条件）：Q->front == Q->rear == 0。
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
出队操作：队不空时，先取队头元素值，再将队头指针加1。

        如上图所示，顺序队列的设计会出现一个问题，那就是，出队操作后，前面的空间无法在进行利用，这样造成的队溢出为假溢出，实际上并没有达到满队的情况。因此引入了顺序循环队列。

顺序循环队列

typedef struct  seqQueue
{
	int r, f, size;
	//r队尾，f队头，循环队列的实现：r=(r+1)%N,判空：r=f,判满：（r+1）%N=f,
	//这种方式必须少存储一个元素，故使用size来记录元素数量，可以存满数组
	mytype  data[N];
}*SQ;

        解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。当队首指针Q->front =N-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。

初始时：Q->front = Q->rear=0。
队首指针进1：Q->front = (Q->front + 1) % N。
队尾指针进1：Q->rear = (Q->rear + 1) % N。
队列长度：(Q->rear - Q->front + N) % N。

顺序循环队的设计相比较与顺序队主要的改进是在尾指针已经指向最大存储地址时，使用Q->rear = (Q->rear + 1) % N的方式来从新回到数组的首部，填充之前出队剩余的空间。

循环队列队空和队满的判断条件
显然，队空的条件是 Q->front == Q->rear 。若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针，此时可以看出队满时也有 Q ->front == Q -> rear 。

 为了区分队空还是队满的情况，有两种处理方式：

1、牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”，

队满条件： (Q->rear + 1)%N == Q->front
队空条件仍： Q->front == Q->rear
队列中元素的个数： (Q->rear - Q ->front + N)% N
2、类型中增设表示元素个数的数据成员。这样，队空的条件为 Q->size == 0 ；队满的条件为 Q->size== N 。

顺序循环队列基本算法 

初始化

//队初始化
SQ seQueue_init()
{
	SQ Q = malloc(sizeof(struct seqQueue));
	if (Q == NULL)
		return NULL;
	Q->r = 0;
	Q->f = 0;
	Q->size = 0;
	return Q;
}

这里我将size和头尾指针的方式均写出来供读者参考 

 判空

//判空
int empty_Queue(SQ Q)
{
	if (Q->size==0)
	{
		printf("队列为空\n");
		return 1;
	}
	//判空：Q->r==Q->f,这种方式必须少存一个数，不然满队时r和f重合会被认为是空
	return 0;
}

判满 

//判满
int full_Queue(SQ Q)
{
	/*if (Q->size == N)
	{
		//printf("队列已满\n");
		return 1;
	}*/
	if ((Q->r + 1) % N == Q->f)
	{
		return 1;
	}
	//判满：(Q->r+1)%N==Q->f,少存一个，代表满队。
	return 0;
}

入队

//入队
int push_Queue(SQ Q, mytype data)
{
	if (Q == NULL)
	{
		printf("队列不存在！！！\n");
		return 0;
	}
	if (full_Queue(Q) == 1)
	{
		printf("队列已满！！！\n");
		return 0;
	}
	Q->data[Q->r] = data;
	printf("%d\n", Q->data[Q->r]);
	Q->r = (Q->r + 1) % N;
	Q->size++;
	printf("入队成功\n");
	
	return 1;
}

 出队

//出队
int pop_Queue(SQ Q)
{
	//printf("!!!\n");
	if (empty_Queue(Q) == 1)
		return -1;
	int data = Q->data[Q->f];
	Q->f = (Q->f + 1) % N;
	Q->size--;
	return data;
}

清空

清空就如同清空数组一样，让头尾指针指向数组起始位置，size等于0。

//清空
int clear_Queue(SQ Q)
{
 
	Q->size = 0;
	Q->r = 0;
	Q->f = 0;
 
	return 1;
}

销毁 

//销毁
int destroy_Queue(SQ *Q)
{
	clear_Queue(*Q);
	free(*Q);
	*Q = NULL;
	return 1;
}

返回队列有效数据数量 

统计数据个数有两种方式，若定义了size这个属性，则直接返回size的值即可，若使用头尾指针的方式，则有三种情况：

Q->r == Q->f        return 0;       

 首尾指针相等，说明为空
Q->r > Q->f          return Q->r - Q->f; 

 尾指针在后，直接相减即为数据个数
 Q->r > Q->f          return  Q->r - Q->f + N;       

尾指针在前，则需要用尾指针减去头指针，代表未存数据的空间个数，值为负，再加上空间大小N即为有效元素个数。

//统计个数
int sum_Queue(SQ Q)
{
	if (Q->r == Q->f)
		return 0;
	else if (Q->r > Q->f)
		return Q->r - Q->f;
	else
		return  Q->r - Q->f + N;
		
}

 

队列的链式存储结构

链队列

队列的链式存储结构表示为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表，只不过它只能尾进头出而已。

 空队列时，front和real都指向头结点。

链队的基本算法

链队的存储类型

typedef  int  mytype;
//节点结构体
typedef struct node
{
	mytype data;
	struct node* next;
}*pnode;
 
//队列结构体
typedef struct linkQueue
{
	pnode f;//存储头结点
	pnode r;//存储尾结点
}*LQ;

初始化

//初始化
LQ linkQueue_init()
{
	LQ Q = malloc(sizeof(struct linkQueue));
	if (Q == NULL)
		return NULL;
	Q->f = (struct node*)malloc(sizeof(struct node));
	if (Q->f == NULL)
		return NULL;
	Q->f->next= NULL;
	Q->r = Q->f;
	return Q;
}

 初始化时需要注意的是，因为链队的成员也是结构体类型的变量，故不仅需要对队列进行空间开辟，对于队列的每一个节点也需要进行开辟空间。

判空

//判空
int empty_linkQueue(LQ Q)
{
	if (Q->f->next == NULL)
		return 1;
	return 0;
 
}

入队

//入队
void  push_linkQueue(LQ Q, mytype data)
{
	pnode p = malloc(sizeof(struct node));
	p->data = data;
	p->next = Q->r->next;
	Q->r->next = p;
	Q->r = p;
	//printf("%p\n", Q->r);
	printf("%d已入队\n", data);
}

出队

        出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点。

 

//出队
mytype pop_linkQueue(LQ Q)
{
	if (empty_linkQueue(Q))
	{
		printf("队列为空！！！\n");
		return -1;
	}
	pnode p = Q->f->next;
	mytype data = p->data;
	Q->f->next = p->next;
	if (p == Q->r)//判断是否出队到最后一个节点
	{
		Q->r = Q->f;
		//Q->f->next = NULL;后面p置空了，这里就不需要了
		//printf("%p\n", Q->r->next);
	}
	
	free(p);
	p = NULL;
	return data;
}

 出队时需要注意的一个点是，当出队到最后一个接待时，需要将尾指针指向头结点，不然尾指针会因为对出队节点的释放一并被释放掉，下次进行入队操作时，由于尾指针并未指向头结点，导致入队异常。

清空

//清空
int clear_linkQueue(LQ Q)
{
	if (empty_linkQueue(Q))
	{
		printf("队列已为空！！！\n");
		return 1;
	}
	pnode p = Q->f->next;
	pnode q = p;
	while (p)
	{
		
		q = q->next;
		free(p);
		p = q;
	}
	Q->f->next = NULL;
	Q->r = Q->f;
	printf("队列已清空！！！\n");
	return 1;
}

销毁

销毁队列时记得将其头结点也释放掉 

//销毁
void destroy_linkQueue(LQ* Q)
{
	if (empty_linkQueue(*Q))
	{
		free((*Q)->f);
		(*Q)->f = NULL;//后面的*Q也会释放，所以这里置空与否不重要了
		free(*Q);
		*Q = NULL;
		printf("队列已销毁！！！\n");
		return;
	}
	else
	{
		clear_linkQueue(*Q);
		free((*Q)->f);
		(*Q)->f = NULL;
		free(*Q);
		*Q = NULL;
		printf("队列已销毁！！！\n");
		return;
	}
}