数据结构——队列（十）

数据结构

一、什么是队列

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

入队：进行插入操作的一端称为队尾。

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

队列也是分为顺序队列和链式队列

二、队列的实现

1.队列的结构

队列需要同时在队头和队尾进行操作，这里使用链表实现。
但由于链表访问队尾时效率较低，所以用tail结构体指针指向链表的末尾。

typedef int QNDataType;
typedef struct QueueNode//对列结点的结构体
{
	struct QueueNode* next;
	QNDataType val;
}QueueNode;

//队列
typedef struct Queue
{
	QueueNode* head;//指向队头结点
	QueueNode* tail;//指向队尾结点
}Queue;

2.队列的初始化

//队列的初始化
void QueueInit(Queue* pq)
{
	pq->head = NULL;
	pq->tail = NULL;
	printf("队列初始化成功\n"); 
}

3.入队

//入队 
void QueuePush(Queue* pq, QNDataType x)
{
	assert(pq);

	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		exit(-1);//创建新结点失败，直接退出
	}
	newnode->val = x;
	newnode->next = NULL;
	
	//队列中一个结点都没有
	if (pq->tail == NULL)
	{
		//新结点即使队头也是队尾
		pq->head = newnode;
		pq->tail = newnode;
	}
	else
	{
		//队列中有结点，在队尾插入新结点
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
		printf("%d入队成功\n",x); 
}

4.出队

//出队 
void QueuePop(Queue* pq)
{
	assert(pq);
//	assert(!QueueEmpty(pq));//没有结点不进行删除操作
	 
	//只有一个结点，删除该结点后将head，tail置空
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL; 
		i++;
	}
	//多个结点
	else
	{
		//保留头结点的下一个结点，下一个结点为新的头
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
		i++;
	}
		printf("第%d个数出队成功\n",i); 
}

5.队列的判断

//判断队列是否为空
void QueueEmpty(Queue* pq)
{
	assert(pq);
	//头结点为空则队列为空
	if(pq->head == NULL)
	printf("队列为空\n");
	else
	printf("队列不为空\n"); 
}

//计算队列的结点个数
int QueueSize(Queue* pq)
{
	int size = 0;
	QueueNode* cur = pq->head;

	while (cur)
	{
		size++;
		cur = cur->next;
	}

	printf("队列长度为%d\n",size);
}

6.队头队尾的获取

//得到队头的数据
QNDataType QueueFront(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));
    if(pq->head!=NULL) 
	printf("队头数据为%d\n",pq->head->val);
	else
	printf("无队头");
}

//得到队尾的数据
QNDataType QueueBack(Queue* pq)
{
	assert(pq);
//	assert(!QueueEmpty(pq));
 if(pq->tail!=NULL) 
		printf("队尾数据为%d\n",pq->tail->val);
			else
	printf("无队尾");
}

总结

附上完整代码

 //队列
 #include<stdio.h> 
 #include<assert.h>
 static i=0;
 typedef int QNDataType;
typedef struct QueueNode//对列结点的结构体
{
	struct QueueNode* next;
	QNDataType val;
}QueueNode;

//队列
typedef struct Queue
{
	QueueNode* head;//指向队头结点
	QueueNode* tail;//指向队尾结点
}Queue;
//队列的初始化
void QueueInit(Queue* pq)
{
	pq->head = NULL;
	pq->tail = NULL;
	printf("队列初始化成功\n"); 
}
//入队 
void QueuePush(Queue* pq, QNDataType x)
{
	assert(pq);

	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		exit(-1);//创建新结点失败，直接退出
	}
	newnode->val = x;
	newnode->next = NULL;
	
	//队列中一个结点都没有
	if (pq->tail == NULL)
	{
		//新结点即使队头也是队尾
		pq->head = newnode;
		pq->tail = newnode;
	}
	else
	{
		//队列中有结点，在队尾插入新结点
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
		printf("%d入队成功\n",x); 
}
//出队 
void QueuePop(Queue* pq)
{
	assert(pq);
//	assert(!QueueEmpty(pq));//没有结点不进行删除操作
	 
	//只有一个结点，删除该结点后将head，tail置空
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL; 
		i++;
	}
	//多个结点
	else
	{
		//保留头结点的下一个结点，下一个结点为新的头
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
		i++;
	}
		printf("第%d个数出队成功\n",i); 
}
//判断队列是否为空
void QueueEmpty(Queue* pq)
{
	assert(pq);
	//头结点为空则队列为空
	if(pq->head == NULL)
	printf("队列为空\n");
	else
	printf("队列不为空\n"); 
}

//得到队列的结点个数
int QueueSize(Queue* pq)
{
	int size = 0;
	QueueNode* cur = pq->head;

	while (cur)
	{
		size++;
		cur = cur->next;
	}

	printf("队列长度为%d\n",size);
}
//得到队头的数据
QNDataType QueueFront(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));
    if(pq->head!=NULL) 
	printf("队头数据为%d\n",pq->head->val);
	else
	printf("无队头");
}

//得到队尾的数据
QNDataType QueueBack(Queue* pq)
{
	assert(pq);
//	assert(!QueueEmpty(pq));
 if(pq->tail!=NULL) 
		printf("队尾数据为%d\n",pq->tail->val);
			else
	printf("无队尾");
}

int main()
{
	
	QueueNode que;
	QueueInit(&que);
	QueuePush(&que,1) ;
	QueuePush(&que,5) ;
	QueueEmpty(&que);
	QueueSize(&que);
	QueueFront(&que);
	QueueBack(&que);
	QueuePop(&que); 
	QueuePop(&que); 
	QueueEmpty(&que);
	QueueSize(&que);
	QueueFront(&que);
	QueueBack(&que);
}