队列的实现

目录

1.队列的概念及结构

2.队列的实现

 初始化队列

队尾入队列

// 队头出队列

// 获取队列头部元素

// 获取队列队尾元素

// 获取队列中有效元素个数

// 销毁队列

---

1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾

                                        出队列：进行删除操作的一端称为队头

2.队列的实现

队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

typedef int QDataType;
// 链式结构：表示队列
typedef struct QListNode
{
    struct QListNode* _pNext;
    QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
    QNode* _front;
    QNode* _rear;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

 初始化队列

 void QueueInit(Queue* q);//无论什么结构，我们都需要先进行初始化。

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;

}

队尾入队列

void QueuePush(Queue*  q, QDataType data);//由于队列是先进先出，所以只能从尾部进行插入

void QueuePush(Queue* pq, QDataType x)//插入，在队尾插入；先进先出
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//每插入一个数据就开辟一个空间
	if (newnode == NULL)//判断是否开辟失败
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)//第一次插入没数据时
	{
		pq->head = pq->tail = newnode; 
	}
	else//有数据后
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

// 队头出队列

void QueuePop(Queue* q);//出队列，最先出的是队头那个数据，要保证是先进先出。

void QueuePop(Queue* pq)//等于是删队头数据
{
	assert(pq);
	assert(!QueueEmpty(pq));//判断队列是否为空
	//一个节点
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//多个节点
	else
	{
		Queue* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

// 获取队列头部元素

QDataType QueueFront(Queue* q);//先判断队列的容量，再返回队头元素

QDataType QueueFront(Queue* pq)//取对头数据
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

// 获取队列队尾元素

QDataType QueueBack(Queue* q);//先判断队列容量，再返回队尾数据

QDataType QueueBack(Queue* pq)//取队尾数据
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

// 获取队列中有效元素个数

int QueueSize(Queue* q);//创建一个当前指针，挨个往后遍历，size为大小统计数量。

int QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//创建一个当前元素指针
	int size = 0;//用于统计元素数量
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0

int QueueEmpty(Queue* q);//这里return是先判断pq->head是否等于空，等就返回真，不等就返回假。

bool QueueEmpty(Queue* pq)//判断容量；
{
	assert(pq);
	return pq->head == NULL;

}

// 销毁队列

void QueueDestroy(Queue* q);由于我们开辟了空间，所以我们在最后也要挨个释放。

void Queuestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)//挨个释放空间
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

扩展：

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。