队列的基本操作

目录

1.1队列的定义

1.2队列的特点

 2.1队列存储的说明

 2.2队列的定义

2.3队列的初始化

2.4队列的判空操作

2.5队列的入队操作

 2.6 队列的出队操作

2.7 队列的获取队首元素操作

2.8 队列的获取队尾元素操作

2.9 队列的计算队列元素数量操作

2.10 队列的销毁操作

3，测试代码

---

1.1队列的定义

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

 

1.2队列的特点

• 队列是一种操作受限的线性表
• 队头(首)：允许删除的一端
• 队尾：允许插入的一端
• 空队列：没有元素的队列
• 删除操作叫做出队,插入操作叫做入队

 2.1队列存储的说明

front指针:指向队头元素
rear指针:指向队尾元素的下一个位置
空队时：rear == front
队列初始化：rear = front = 0
入队：队未满时，先送值到队尾，再队尾指针加一
出队：队为空时，先取队头元素，再队头指针加一

 2.2队列的定义

这里选择实现链表链式结构的队列

• 链队本质上是一个同时带有队头指针、队尾指针的单链表
• 头指针指向队头结点
• 尾指针指向队尾结点
• 链式队列适合于数据元素变化较大的情形，不存在上溢
• 当使用多个队列时，最好使用链式队列，可以避免存储分配不合理下的溢出问题。

typedef int QDataType;
 
typedef struct QueueNode//定义队列结点
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;
 
typedef struct Queue//定义队列
{
	QueueNode* head;//队头
	QueueNode* tail;//队尾
}Queue;

2.3队列的初始化

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

2.4队列的判空操作

只要头指针没有指向任何空间就说明队列为空

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}

2.5队列的入队操作

因为是链式结构，无需检查队列是否满了，直接开辟一个新空间存储数据，向新结点的数据域赋值，然后**tail->next指向新结点**。

void QueuePush(Queue* pq, QDataType x) 
{
	assert(pq);
	QueueNode* newnode =(QueueNode*) malloc(sizeof(QueueNode));
	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;
	}
}

 2.6 队列的出队操作

1.先判断是否是空队,保存下一个结点

2.free释放头结点

3.指向所保存的下一个结点

（上述过程要小心出现队列内元素全部清完，pq->tail变成野指针的情况）

 

 此时tail为野指针

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
 
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
 
	QueueNode* next = pq->head->next;
	free(pq->head);
}

2.7 队列的获取队首元素操作

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
 
	return pq->head->data;
}

2.8 队列的获取队尾元素操作

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

2.9 队列的计算队列元素数量操作

int QueueSize(Queue* pq)
{
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

2.10 队列的销毁操作

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(next);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

3，测试代码

#include "Queue.h"
 
void TestQueue()
{
	Queue q;
	QueuInit(&p);
	QueuePush(&q,1);
	QueuePush(&q,2);
	QueuePush(&q,3);
	QueuePush(&q,4);
 
	while (!QueueEmpty(&q))
	{
		printf("%d", QueueFront(&q));
		QueuePop(&q);
	}
	QueueDestroy(&q);
}
 
int main()
{
	TestQueue(&q);
 
	return 0;
}