数据结构——队列

逻辑结构：队列是一种操作受限的线性表，只允许从队尾入队，从队首出队。这个情形类型与排队

物理结构：分为顺序存储结构（一般通过循环队列实现），链式存储结构

1.队列的顺序存储

接下来主要介绍的是循环队列

1.1循环队列的初始化

typedef struct Queue
{
	int data[MaxSize];
	int front;//队首指针
	int rear;//队尾指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue* Q)
{
	Q->front = Q->rear = 0;
}

1.2判断队空

//队列的判空
bool Empty(SqQueue* Q)
{
	if (Q->front == Q->rear)
	{
		return true;
	}
	else
	{
		return false;
	}
}

1.3入队

//入队
bool EnQueue(SqQueue* Q)
{
	//判断队列是否满了
	if ((Q->rear + 1) % MaxSize == Q->front)
	{
		printf("队列已经满了\n");
		return false;
	}
	int x = 0;
	printf("请输入要插入的值:");
	scanf("%d", &x);
	Q->data[Q->rear] = x;
	Q->rear = (Q->rear + 1) % MaxSize;
	return true;
}

1.4出队

//出队
bool DeQueue(SqQueue* Q,int* x)
{
	//判断队列是否为空
	if (Q->front == Q->rear)
	{
		return false;
	}
	(*x) = Q->data[Q->front];
	Q->front = (Q->front + 1) % MaxSize;
	return true;
}

1.5读出队首元素

//获取队首元素
bool GetQueue(SqQueue* Q,int* x)
{
	//判断队列是否为空
	if (Q->front == Q->rear)
	{
		return false;
	}
	(*x) = Q->data[Q->front];
	return true;
}

1.6求队列元素个数

//求队列元素个数
int Length(SqQueue* Q)
{
	int len = ((Q->rear + MaxSize) - Q->front) % MaxSize;
	return len;
}

1.7循环队列整体代码

//顺序队列(也可以看做是循环队列）
typedef struct Queue
{
	int data[MaxSize];
	int front;//队首指针
	int rear;//队尾指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue* Q)
{
	Q->front = Q->rear = 0;
}

//队列的判空
bool Empty(SqQueue* Q)
{
	if (Q->front == Q->rear)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//入队
bool EnQueue(SqQueue* Q)
{
	//判断队列是否满了
	if ((Q->rear + 1) % MaxSize == Q->front)
	{
		printf("队列已经满了\n");
		return false;
	}
	int x = 0;
	printf("请输入要插入的值:");
	scanf("%d", &x);
	Q->data[Q->rear] = x;
	Q->rear = (Q->rear + 1) % MaxSize;
	return true;
}


//出队
bool DeQueue(SqQueue* Q,int* x)
{
	//判断队列是否为空
	if (Q->front == Q->rear)
	{
		return false;
	}
	(*x) = Q->data[Q->front];
	Q->front = (Q->front + 1) % MaxSize;
	return true;
}

//获取队首元素
bool GetQueue(SqQueue* Q,int* x)
{
	//判断队列是否为空
	if (Q->front == Q->rear)
	{
		return false;
	}
	(*x) = Q->data[Q->front];
	return true;
}

//求队列元素个数
int Length(SqQueue* Q)
{
	int len = ((Q->rear + MaxSize) - Q->front) % MaxSize;
	return len;
}


int main()
{
	SqQueue Q;
	int x = 0;
	//初始化顺序队列
	InitQueue(&Q);

	//入队，入队5个元素
	int i = 0;
	for (i = 0; i < 5; i++)
	{
		EnQueue(&Q);
	}

	//出队一个元素
	DeQueue(&Q,&x);
	printf("出队元素大小为%d\n", x);

	//获取当前队头元素
	GetQueue(&Q,&x);
	printf("当前队头元素大小为%d\n", x);
	return 0;
}

2.队列的链式存储

2.1队列的初始化

//队列节点
typedef struct LinkNode
{
	int data;
	struct LinkNode* next;
}LinkNode;

typedef struct
{
	LinkNode* front;//队首指针
	LinkNode* rear;//队尾指针,这两个都是指向节点的指针
}LinkQueue;//LinkQueue是包含两个节点指针的结构体的结构体类型

//队列的初始化，带头结点
void InitQueue(LinkQueue** Q)//传递的是队首指针和队尾指针
{
	(*Q)->front = (*Q)->rear = (LinkNode*)calloc(1, sizeof(LinkNode));
	(*Q)->front->next = NULL;
}




int main()
{
	LinkQueue* Q=(LinkQueue*)malloc(sizeof(LinkQueue));
	int x = 0;
	InitQueue(&Q);

	return 0;
}

2.2队列的判空

//队列的判空操作

bool Empty(LinkQueue** Q)
{
	if ((*Q)->front == (*Q)->rear)//还可以是Q->front->next==NULL;
	{
		return true;
	}
	else
	{
		return false;
	}
}

2.3入队操作

//入队
void EnQueue(LinkQueue** Q)
{
	//链表不存在队列已经满了，不需要判断

	// 创建新节点
	LinkNode* s = (LinkNode*)calloc(1, sizeof(LinkNode));
	if (s == NULL)
	{
		return;
	}
	int x = 0;
	printf("请输入要插入的节点的数据：");
	scanf("%d", &x);
	s->data = x;
	s->next = NULL;
	(*Q)->rear->next = s;
	(*Q)->rear = s;

}

2.4出队操作

// 出队

bool DeQueue(LinkQueue** Q,int* x)
{
	//先判断队列是否为空
	if ((*Q)->front == (*Q)->rear)
	{
		return false;
	}
	//出队从队首开始，也就是头结点
	LinkNode* p = (*Q)->front->next;//这个就是除头指针外队首的第一个节点地址
	(*x) = p->data;
	(*Q)->front->next = p->next;
	if ((*Q)->rear==p)//出队的是最后一个节点,修改队尾指针到头结点
	{
		(*Q)->rear = (*Q)->front;
	}
	free(p);//释放掉这一块空间
	return true;
}

2.5整体代码

//队列节点
typedef struct LinkNode
{
	int data;
	struct LinkNode* next;
}LinkNode;

typedef struct
{
	LinkNode* front;//队首指针
	LinkNode* rear;//队尾指针,这两个都是指向节点的指针
}LinkQueue;//LinkQueue是包含两个节点指针的结构体的结构体类型

//队列的初始化，带头结点
void InitQueue(LinkQueue** Q)//传递的是队首指针和队尾指针
{
	(*Q)->front = (*Q)->rear = (LinkNode*)calloc(1, sizeof(LinkNode));
	(*Q)->front->next = NULL;
}

//队列的判空操作

bool Empty(LinkQueue** Q)
{
	if ((*Q)->front == (*Q)->rear)//还可以是Q->front->next==NULL;
	{
		return true;
	}
	else
	{
		return false;
	}
}


//入队
void EnQueue(LinkQueue** Q)
{
	//链表不存在队列已经满了，不需要判断

	// 创建新节点
	LinkNode* s = (LinkNode*)calloc(1, sizeof(LinkNode));
	if (s == NULL)
	{
		return;
	}
	int x = 0;
	printf("请输入要插入的节点的数据：");
	scanf("%d", &x);
	s->data = x;
	s->next = NULL;
	(*Q)->rear->next = s;
	(*Q)->rear = s;

}

// 出队

bool DeQueue(LinkQueue** Q,int* x)
{
	//先判断队列是否为空
	if ((*Q)->front == (*Q)->rear)
	{
		return false;
	}
	//出队从队首开始，也就是头结点
	LinkNode* p = (*Q)->front->next;//这个就是除头指针外队首的第一个节点地址
	(*x) = p->data;
	(*Q)->front->next = p->next;
	if ((*Q)->rear==p)//出队的是最后一个节点,修改队尾指针到头结点
	{
		(*Q)->rear = (*Q)->front;
	}
	free(p);//释放掉这一块空间
	return true;
}

int main()
{
	LinkQueue* Q=(LinkQueue*)malloc(sizeof(LinkQueue));
	int x = 0;
	InitQueue(&Q);

	//入队 入队5个元素
	int i = 0;
	for (i = 0; i < 5; i++)
	{
		EnQueue(&Q);
	}

	//出队一个元素
	DeQueue(&Q,&x);
	printf("出队的元素是%d\n", x);
	return 0;
}