1.3 队列的顺序存储实现和链式存储实现（C语言）

队列的存储实现

顺序存储实现源码运行

顺环队列

1. 使用额外标记：Size或者tag域2. 仅使用n-1个数组空间链式存储实现源码运行

链队列示意图 int data[]与int *data区别

顺序存储实现源码

数组的方式实现队列的顺序存储。用一个一维数组来存储队列的数据，对队列执行操作时，插入和删除分别是对数组头和数组尾进行操作，所以还要有两个指针变量来指示数组的头和尾

#include 
#include 
#define ERROR 0
#define MaxSize 5       

typedef int ElementType;  //给int取别名
typedef int Position;
struct QNode {
	ElementType *Data;     
	Position Front, Rear;  
};
typedef struct QNode *Queue;


Queue CreateQueue()
{
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
	Q->Front = Q->Rear = 0;

	return Q;
}


bool IsFull(Queue Q)
{
	return ((Q->Rear + 1) % MaxSize == Q->Front);
}


bool AddQ(Queue Q, ElementType X)
{
	if (IsFull(Q)) {
		printf("队列满");
		return false;
	}
	else {	
		
		Q->Rear = (Q->Rear + 1) % MaxSize;//循环队列：求余函数
		
		Q->Data[Q->Rear] = X;//注意这里Q->Rear=1，也就是说队尾是1，从第一位开始赋值
		return true;
	}
}


bool IsEmpty(Queue Q)
{
	return (Q->Front == Q->Rear);
}


ElementType DeleteQ(Queue Q)
{
	if (IsEmpty(Q)) {
		printf("队列空");
		return ERROR;
	}
	else {
		Q->Front = (Q->Front +1) % MaxSize;
		return  Q->Data[Q->Front];
	}
}


ElementType Queueshow(Queue Q)
{
	int i;
	i = Q->Front;
	if (IsEmpty(Q)) {
		printf("栈是空的");
	}else
	while ((i + Q->Front) != Q->Rear)
	{
		i = (i +1) % MaxSize; //初次时，i=1，从第一位开始输出
		printf("%dt",Q->Data[i]);	
	}
	printf("n");
	return 0;
}


int QueueLength(Queue Q)
{
	return  (Q->Rear - Q->Front + MaxSize) % MaxSize;
}

int  show(Queue Q) {
	printf("此时队列的长度为%d,此时队头Front指向的元素为%d,此时队尾Rear指向的元素为%dn", QueueLength(Q),Q->Front, Q->Rear);

	return 0;
}


int main() {
	Queue q;//结构体指针 
	int i = 0;
	q = CreateQueue();
	printf("此时队列的MaxSize大小为%dn", MaxSize);
	
	printf("此时队列q的元素有n");
	Queueshow(q);
	show(q);

	printf("若队列未满，将元素X插入队列n");
    for (i = 1; i < MaxSize; i++) {
		printf("将%d插入队列q为新的队尾元素n", i);
		AddQ(q, i);
	}
	show(q);

	printf("此时堆栈q的元素有n");
	Queueshow(q);
	printf("若队列不空，删除并返回队头元素n");
	for (i = 1; i < MaxSize; i++) {
		printf("将队头元素%d从队列q中删除并返回n", DeleteQ(q));
	}
	show(q);

	printf("此时堆栈q的元素有n");
	Queueshow(q);
	
	return 0;
}

运行

此时队列的MaxSize大小为5
此时队列q的元素有
栈是空的
此时队列的长度为0,此时队头Front指向的元素为0,此时队尾Rear指向的元素为0
若队列未满，将元素X插入队列
将1插入队列q为新的队尾元素
将2插入队列q为新的队尾元素
将3插入队列q为新的队尾元素
将4插入队列q为新的队尾元素
此时队列的长度为4,此时队头Front指向的元素为0,此时队尾Rear指向的元素为4
此时堆栈q的元素有
1       2       3       4
若队列不空，删除并返回队头元素
将队头元素1从队列q中删除并返回
将队头元素2从队列q中删除并返回
将队头元素3从队列q中删除并返回
将队头元素4从队列q中删除并返回
此时队列的长度为0,此时队头Front指向的元素为4,此时队尾Rear指向的元素为4
此时堆栈q的元素有
栈是空的

顺环队列

1. 使用额外标记：Size或者tag域

增加一个额外的标记，Size来记录当前队列元素的个数，删除元素-1，加入元素+1，由Size为0或n得知队列空满插入元素的时候，Tag设为1，删除一个元素的时候tag等于0，tag代表最后一次操作是插入还是删除，此时就知道队列到底是空或满

2. 仅使用n-1个数组空间

另外一种方法是，数组大小虽然是n，但是不放满，最多只放n-1个元素，就像上面的例子，数组有6，但是我最多放5个

链式存储实现源码

#include 
#include 
#define ERROR 0
#define NULL 0
#define MaxSize 5       

typedef int ElementType;  

typedef struct Node *PtrToNode;
struct Node {      
	ElementType Data;
	PtrTonode Next;
};
typedef PtrTonode Position;

struct QNode {      
	Position Front, Rear;  
};
typedef struct QNode *Queue;


Queue InitQueue()
{
	Queue Q=(Queue)malloc(sizeof(struct QNode));
	Q->Front = Q->Rear = (Position)malloc(sizeof(Node));
	if (!Q->Front)
		exit(false);//正常退出
	Q->Front->Next = NULL;
	return Q;
}

void DestroyQueue(Queue Q)
{
	while (Q->Front)
	{
		Q->Rear = Q->Front->Next;
		free(Q->Front);
		Q->Front = Q->Rear;
	}

}


Queue ClearQueue(Queue Q)
{
	Position p, q;
	Q->Rear = Q->Front;
	p = Q->Front->Next;
	Q->Front->Next = NULL;
	while (p)
	{
		q = p;
		p = p->Next;
		free(q);
	}
	return Q;
}


bool IsEmpty(Queue Q)
{
	return (Q->Front == NULL);
}


ElementType EnQueue(Queue Q, ElementType e)
{
	Position s = (Position)malloc(sizeof(Node));
	if (!s) 
		exit(false);
	s->Data = e;
	s->Next = NULL;
	Q->Rear->Next = s;	
	Q->Rear = s;		
	return 0;
}


ElementType DeleteQ(Queue Q)
{
	Position FrontCell;
	ElementType FrontElem;

	if (IsEmpty(Q)) {
		printf("队列空");
		return ERROR;
	}
	else {
		FrontCell = Q->Front->Next; 
		FrontElem = FrontCell->Data;
		Q->Front->Next = FrontCell->Next;
		if (Q->Front == Q->Rear) 
			Q->Front = Q->Rear = NULL; 

		free(FrontCell);  
		return  FrontElem;
	}
}


ElementType Queueshow(Queue Q)
{
	Position p;
	p = Q->Front->Next;
	if (Q->Front->Next==NULL) {
		printf("队列是空的");
		return false;
	}else
	while (p)
	{
		printf("%dt",p->Data);
		p = p->Next;
	}
	printf("n");
	return 0;
}


int QueueLength(Queue Q)
{
	int i = 0;
	Position p ;
	p = Q->Front;
	if (p->Next == NULL) {
		//printf("队列是空的n");
		return false;
	}
	else
	while (Q->Rear != p)
	{
		i++;
		p = p->Next;
	}
	return i;
}

void  show(Queue Q) {
	Position p,p2;
	if (Q->Front == Q->Rear|| Q->Front->Next==NULL)
	{
		printf("链队列为空，无法返回队头数据n"); 
	}else
	{
		p = Q->Front->Next;//队头
		printf( "此时队头Front指向的元素为%d,n" ,p->Data );
		p2 = Q->Rear;
		printf("此时队尾Rear指向的元素为%dn", p2->Data);
	}
	printf("此时队列的长度为%d,n", QueueLength(Q));
}


int main() {
	Queue q;//结构体指针 
	int i = 0;
	q = InitQueue();
	ClearQueue(q);
	printf("此时队列的MaxSize大小为%dn", MaxSize);
	printf("此时队列q的元素有n");
	Queueshow(q);
	show(q);

	printf("若队列未满，将元素X插入队列n");
    for (i = 1; i < MaxSize; i++) {
		printf("将%d插入队列q为新的队尾元素n", i);
		EnQueue(q, i);
	}
	printf("此时队列q的元素有n");
	Queueshow(q);
	show(q);

	printf("若队列不空，删除并返回队头元素n");
	for (i = 1; i < MaxSize; i++) {
		printf("将队头元素%d从队列q中删除并返回n", DeleteQ(q));
	}
	printf("此时队列q的元素有n");	
	Queueshow(q);
	show(q);
	DestroyQueue(q);
	
	return 0;
}

运行

此时队列的MaxSize大小为5
此时队列q的元素有
队列是空的链队列为空，无法返回队头数据
此时队列的长度为0,
若队列未满，将元素X插入队列
将1插入队列q为新的队尾元素
将2插入队列q为新的队尾元素
将3插入队列q为新的队尾元素
将4插入队列q为新的队尾元素
此时队列q的元素有
1       2       3       4
此时队头Front指向的元素为1,
此时队尾Rear指向的元素为4
此时队列的长度为4,
若队列不空，删除并返回队头元素
将队头元素1从队列q中删除并返回
将队头元素2从队列q中删除并返回
将队头元素3从队列q中删除并返回
将队头元素4从队列q中删除并返回
此时队列q的元素有
队列是空的链队列为空，无法返回队头数据
此时队列的长度为0,

链队列示意图

int data[]与int *data区别

做形参的时候，int data[]与int *data无任何区别。

int data[]申请的是一个静态数组，在设计时就需要考虑其大小，这样带来的缺点是空间大小固定，导致空间不够用或者浪费
int *data申请的是一个指针变量(申请一个路标)，然后通过malloc函数申请一片空间(在建设工程中申请一片空地，这样可以按照需求确定大小，然后让路标指向这片空地)，得到动态数组(即申请的空间可以由变量大小确定)。

data[i]本来就是*(data+i)
如果要访问int data[5]实际上是先获得这个数组的头指针int *data，然后在内存中偏移5个int的数据长度int *(data+5)，也就是从代码的理解上，可以认为int data[5]与 int *(data+5)等价

1.3 队列的顺序存储实现和链式存储实现（C语言）

C/C++/C#相关栏目本月热门文章