队列的代码实现

更多数据结构的实现

文章目录

队列的分类：

队列是一种运算受限的线性表，在队列上，插入限定在某一端进行，删除限定在另一端进行。允许插入的一端称为队尾，允许删除的一端称为队头。新插入的结点只能添加到队尾，被删除的只能是排在队头的结点。

进行插入操作的一端称为队尾（入队列）
进行删除操作的一端称为队头（出队列）
队列具有先进先出的特性

队列的分类：

顺序队列

由一个一维数组及两个分别指向队头front和队尾rear的变量组成。

它的操作有两种方式：

队头指针不动，队头元素出队后后面的所有元素向队头移动。缺陷：操作时如果出队列比较多，要搬移大量元素。
队头移动，出队时队头向后移动一个位置。如下图，此时如果再有F、G进栈，就会出现假溢出的情况。

循环队列（环形队列）

为了能够充分利用数组的存储空间，可以把数组的前端和后端连接起来，形成一个环形的表，这个环形的表称为循环队列。

那循环队列如何判断队列空和满呢？

少用一个存储单元
设置一个标记位
设置一个计数器

顺序队列进行入队列和出队列时时间性能不是很好，循环队列虽然能够解决假溢出的问题，但循环队列又面临着真溢出的问题。

循环队列的代码实现

#define _CRT_SECURE_NO_WARNINGS 1


#include<assert.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define QueueSize 6   //队列的容量
typedef int DataType;

typedef struct SqQueue
{
	DataType data[QueueSize];  //存放队列的元素
	int front, rear;   //队头和队尾指针
}SqQueue;

//为了区分队列空与满，我们少用一个存储单位，这样的话：
//1.队空条件： front = rear
//2.队满条件： front = (rear +1 )%QueueSize
//3.进队操作： rear循环进1
//4.出队操作：front循环进1

//初始化
void InitQueue(SqQueue &qu)
{
	qu.rear = qu.front = 0;//初始化指针
}

//入队：先判断队列是否已满
void Push(SqQueue &qu, DataType x)
{
	if (qu.front == (qu.rear+1)%QueueSize)
	{
		printf("队列已满\n");
		return;
	}
	else //不满，队尾指针+1，该位置存放x
	{
		qu.rear = (qu.rear+1)%QueueSize;//循环+1
		qu.data[qu.rear] = x;
	}

}

//出队：先判断队列是否已空，若不空，让队头指针循环加1；并将该位置的元素赋值给x
void Pop(SqQueue &qu, DataType &x)
{
	if (qu.front == qu.rear)
	{
		printf("队列为空\n");
		return;
	}
	else 
	{
		qu.front = (qu.front + 1) % QueueSize;
		x = qu.data[qu.front];
		return;
	}
}

//查看队列顶元素：先判断队列是否已空，若不空；将队头指针上一个位置的元素返回
DataType GetTop(SqQueue &qu)
{
	if (qu.front == qu.rear)
	{
		printf("队列为空\n");
		return -1;
	}
	else
	{
		int tmp = (qu.front + 1) % QueueSize;
		return qu.data[tmp];
	}
		
}

//判断队列是否为空
void StackEmpty(SqQueue qu)
{
	if (qu.front == qu.rear)
	{
		printf("队列为空\n");
	}
	else
		printf("队列不为空\n");
}

//打印
void SeqListPrint(const SqQueue qu)
{
	int i = 0;
	printf("队列元素为：");
	for (i = 1; i < QueueSize; i++)
	{
		printf("%d ", qu.data[i]);
	}
	printf("\n");
}

void Test()
{
	SqQueue s;
	SqQueue &ps = s;
	
	InitQueue(ps);
	
	Push(ps, 1);
	Push(ps, 2);
	Push(ps, 3);
	Push(ps, 4);
	Push(ps, 5);
	SeqListPrint(s);

	printf("此时队列顶元素为：%2d\n", GetTop(s));

	int x = 0;
	int &px = x;
	Pop(ps, px);
	printf("出队列元素为：%2d,", px);
	printf("此时队列顶元素为：%2d\n", GetTop(s));

	StackEmpty(s);
}

int main()
{
	Test();
	system("pause");
	return 0;
}

结果展示：

链式队列

链式队列实际上是一个同时带有一个首指针和尾指针的单链表，首指针指向头结点，尾指针指向队尾节点。

链式队列的代码实现

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

typedef int DataType;

//队列中结点的结构体
typedef struct SLQNode
{
	struct SLQNode *next;  //指针域
	DataType data;  //数据域

}SLQNode;

//队头队尾指针的结构体
typedef struct SLQptr
{
	SLQNode *front;
	SLQNode *rear;
}SLQptr;

//  分析：
//  队空的条件：front == rear == NULL;
//   一般不会出现队满的情况
//  进队：创建结点并将其插入到队尾
//  出队：删除队头的节点

//初始化
void InitQueue(SLQptr *&lq)
{
	lq = (SLQptr*)malloc(sizeof(SLQptr));
	lq->rear = lq->front = NULL;
}

//入队：创建结点并将其插入到队尾
void Push(SLQptr *&lq, DataType x)
{
	SLQNode *newNode = (SLQNode*)malloc(sizeof(SLQNode));
	newNode->data = x;
	newNode->next = NULL;

	if (NULL == lq->front && NULL == lq->rear)//空队
	{
		lq->front = lq->rear = newNode;
	}
	else 
	{
		lq->rear->next = newNode;
		lq->rear = newNode;
	}

}

//出队：删除队头的节点
void Pop(SLQptr *&lq)
{
	SLQNode *newNode = lq->front;
	if (NULL == lq->front && NULL == lq->rear)
	{
		printf("队列为空，不可以出队\n");
		return;
	}
	else if (lq->front == lq->rear)//队列只有一个节点，删除后变为空队列
	{
		lq->front = lq->rear = NULL;
		printf("出队成功\n");
	}
	else
	{		
		lq->front = newNode->next;
		printf("出队成功\n");
	}
	free(newNode);
}

//查看队列顶元素
void GetTop(SLQptr *lq)
{
	int x = -1;
	if (NULL == lq->front && NULL == lq->rear)
	{
		printf("队列为空\n");
		return;
	}
	else
	{
		x = lq->front->data;
		printf("队列的顶元素为：%2d\n",x);
		
	}

}

//判断队列是否为空
void QueueEmpty(SLQptr *lq)
{
	if (NULL == lq->front && NULL == lq->rear)
	{
		printf("队列为空\n");
		return;
	}
	else
		printf("队列不为空\n");
}

//打印
void SLQueuePrint(SLQptr *lq)
{
	SLQNode * cur = lq->front;
	for (; cur != NULL; cur = cur->next)
	{
		printf("%2d->", cur->data);
	}
	printf("NULL\n");

}

void Test()
{
	SLQptr *s;
	SLQptr *&ps = s;

	InitQueue(ps);

	Push(ps, 1);
	Push(ps, 2);
	Push(ps, 3);
	Push(ps, 4);
	Push(ps, 5);
	SLQueuePrint(s);

	GetTop(s);
	Pop(ps);
	GetTop(s);
	Pop(ps);
	GetTop(s);

	QueueEmpty(s);

}

int main()
{
	Test();
	system("pause");
	return 0;
}

结果展示：

优先级队列

带有优先级的队列称为优先级队列

队列具有先进先出的特性，即最先进入队列的元素将被最先出队列，有时也需要把进入队列中的元素分优先级(比如线程调度)，出队列时首先选择优先级最高的元素出队列，对于优先级相同的元素则按照先进先出的原则出队列

队列的应用

生产者消费者模型
消息队列
排队现象
网络数据传输