队列操作

队列操作说明

队列的常用操作主要包括，队列的初始化、判断是否为空、元素入队列、元素出队列、遍历以及给清空队列元素等。

队列定义

队列的结构如下：

typedef struct Node
{
	int data;  //队列每个结点的数据 
    struct Node *pNext; //当前结点的下一个结点的地址
}NODE, *PNODE;
typedef struct Queue
{
	PNODE pHead;   //头指针 
	PNODE pTail;   //尾指针 
}QUEUE, *PQUEUE;

我们定义了一个队列结点的结构 Node，其有两个成员，具体每个成员的意思见上面的注释。接着，我们定义了队列结构 Queue，其中包括了队列头元素和队列尾元素。

队列初始化

函数原型

int init(PQUEUE pQueue);//初始化队列

参数

参数	说明
pQueue	需要初始化的队列。

返回值

初始化成功，返回 1，否则，返回 0。

图解

具体实现

int init(PQUEUE pQueue)
{
	//为头结点分配内存 
	pQueue->pHead = (PNODE)malloc(sizeof(PNODE));
	if (pQueue->pHead == NULL)
	{
		return 0;
	}
	//为尾结点分配内存 
	pQueue->pTail = (PNODE)malloc(sizeof(PNODE));
	if (pQueue->pTail == NULL)
	{
		return 0;
	}
	//将头结点和尾结点指向一起 
	pQueue->pHead = pQueue->pTail;
	//设置头结点的Next指针为空 
	pQueue->pHead->pNext = NULL;
	return 1;
}

说明

我们只需要创建一个结点，并将队列头指针和队列尾指针指向该结点即可。

判断队列为空

函数原型

int isempty(Queue* pQueue);

参数

参数	说明
pQueue	需要判断的队列。

返回值

如果队列为空，返回 1，否则返回 0。

具体实现

int isempty(Queue* pQueue)
{
	//如果头指针和尾指针相等，则队列为空 
	if (pQueue->pHead == pQueue->pTail)
	{
		return 1;
	}
	return 0;
}

说明

如果队列头指针和队列尾指针相等，那么就说明队列为空。

元素入队列

函数原型

int inQueue(PQUEUE pQueue, int val);//将元素val入队

参数

参数	说明
pQueue	需要插入元素的队列。
val	需要入队列的元素。

返回值

如果入队列成功，则返回 1，否则，返回 0。

图解

具体实现

int inQueue(PQUEUE pQueue, int val)
{
	//创建一个要插入的结点 
	PNODE pInsertNode = (PNODE)malloc(sizeof(PNODE));
	if (pInsertNode == NULL)
	{
		return 0;
	}
	//将入队列的元素的结点的值设置为入队列的值
    pInsertNode->data = val;
	//将头结点的next指针指向要插入的结点 
	pQueue->pTail->pNext = pInsertNode;
	//插入节点的额next指针指向NULL 
	pInsertNode->pNext = NULL;
	//将队列的尾结点指向要插入的结点 
	pQueue->pTail = pInsertNode;
	return 1; 
}

说明

首先，我们分配一个要入队列的结点，接着，将入队列的元素的结点的值设置为入队列的值，并且将队列的尾结点的 Next 指针指向要插入的结点，最后，再次将队列尾指针指向新插入的结点即可（也就是新的队尾）。

元素出队列

函数原型

int outQueue(PQUEUE pQueue, int *pVal);

参数

参数	说明
pQueue	需要删除元素的队列。
pRetVal	出队列的元素的值。

返回值

如果出队列成功，则返回 1，否则，返回 0。

图解

具体实现

int outQueue(PQUEUE pQueue, int *pVal)
{
	//判断队列是否为空
	if (isempty(pQueue) == 1)
	{
		return 0;
	}
	//使用pDeleteNode指向要出队的结点 
	PNODE pDeleteNode = pQueue->pHead->pNext;
	//将队列的head的Next指针指向下一个结点
	pQueue->pHead->pNext = pDeleteNode->pNext;
	*pVal = pDeleteNode->data;
	//释放出队的结点 
	free(pDeleteNode);
	pDeleteNode = NULL;
	if (NULL == pQueue->pHead->pNext)
	{
		pQueue->pTail = pQueue->pHead;
	}
	return 1;
}

说明

首先，我们使用 pDeleteNode 指针指向队列头指针的下一个（也就是要删除的结点），接着，将队列头元素的值赋值给返回值，并将队列头指针的 Next 指针移到后一位，释放 pDeleteNode 即可。

遍历队列

函数原型

void travers(PQUEUE pQueue);

参数

参数	说明
pQueue	需要遍历的队列。

具体实现

void travers(PQUEUE pQueue)
{
	//判断队列是否为空
	if (isempty(pQueue) == 1)
	{
		return;
	}
	printf("队列元素为：[ ");
	PNODE pCurrentNode = pQueue->pHead->pNext;
	while (pCurrentNode != NULL)
	{
		printf("%d ", pCurrentNode->data);
		pCurrentNode = pCurrentNode->pNext;
	}
	printf("]\n");
}

说明

从队列头指针的下一个获取元素，每次将指针往下移一位即可。

清空队列

函数原型

void clear(PQUEUE pQueue);

参数

参数	说明
pQueue	需要清空的队列。

具体实现

void clear(PQUEUE pQueue)
{	
	while(isempty(pQueue) == 0)
	{
		int val = 0;
		outQueue(pQueue, &val);
	}
}

说明

如果队列不为空，则一直调用出队函数，不停的出队即可。

案例

队列操作的综合案例如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node
{
	int data;  //队列每个结点的数据 
    struct Node *pNext; //当前结点的下一个结点的地址
}NODE, *PNODE;
typedef struct Queue
{
	PNODE pHead;   //头指针 
	PNODE pTail;   //尾指针 
}QUEUE, *PQUEUE;
int init(PQUEUE pQueue);//初始化队列，初始化成功返回1，失败返回0
int inQueue(PQUEUE pQueue, int val);//将元素val入队
int outQueue(PQUEUE pQueue, int *pVal);//出队，将出队的元素返回到pVal中 
int isempty(PQUEUE pQueue);//判断队列是否为空，如果为空，返回1，否则，返回0 
void travers(PQUEUE pQueue);//遍历
void clear(PQUEUE pQueue);//清空队列
int main()
{
	printf("嗨客网（www.haicoder.net）\n\n");
	PQUEUE pQueue = (PQUEUE)malloc(sizeof(PQUEUE));
	init(pQueue);
	if (isempty(pQueue) == 1)
	{
		printf("初始化队列后，队列为空\n");
	}
	else
	{
		printf("初始化队列后，队列不为空\n");
	}
	inQueue(pQueue, 10);
	inQueue(pQueue, 20);
	inQueue(pQueue, 30);
	if (isempty(pQueue) == 1)
	{
		printf("入队后，队列为空\n");
	}
	else
	{
		printf("入队后，队列不为空\n");
	}
	travers(pQueue);
	int retValue = 0;
	outQueue(pQueue, &retValue);
	printf("出队元素为：%d\n", retValue);
	outQueue(pQueue, &retValue);
	printf("出队元素为：%d\n", retValue);
	travers(pQueue);
	clear(pQueue);
	if (isempty(pQueue) == 1)
	{
		printf("清空队列后，队列为空\n");
	}
	else
	{
		printf("清空队列后，队列不为空\n");
	}
	return 0;
}
int init(PQUEUE pQueue)
{
	//为头结点分配内存 
	pQueue->pHead = (PNODE)malloc(sizeof(PNODE));
	if (pQueue->pHead == NULL)
	{
		return 0;
	}
	//为尾结点分配内存 
	pQueue->pTail = (PNODE)malloc(sizeof(PNODE));
	if (pQueue->pTail == NULL)
	{
		return 0;
	}
	//将头结点和尾结点指向一起 
	pQueue->pHead = pQueue->pTail;
	//设置头结点的Next指针为空 
	pQueue->pHead->pNext = NULL;
	return 1;
}
int inQueue(PQUEUE pQueue, int val)
{
	//创建一个要插入的结点 
	PNODE pInsertNode = (PNODE)malloc(sizeof(PNODE));
	if (pInsertNode == NULL)
	{
		return 0;
	}
	//将入队列的元素的结点的值设置为入队列的值
    pInsertNode->data = val;
	//将头结点的next指针指向要插入的结点 
	pQueue->pTail->pNext = pInsertNode;
	//插入节点的额next指针指向NULL 
	pInsertNode->pNext = NULL;
	//将队列的尾结点指向要插入的结点 
	pQueue->pTail = pInsertNode;
	return 1; 
}
int outQueue(PQUEUE pQueue, int *pVal)
{
	//判断队列是否为空
	if (isempty(pQueue) == 1)
	{
		return 0;
	}
	//使用pDeleteNode指向要出队的结点 
	PNODE pDeleteNode = pQueue->pHead->pNext;
	//将队列的head指针指向下一个结点
	pQueue->pHead->pNext = pDeleteNode->pNext;
	*pVal = pDeleteNode->data;
	//释放出队的结点 
	free(pDeleteNode);
	pDeleteNode = NULL;
	if (NULL == pQueue->pHead->pNext)
	{
		pQueue->pTail = pQueue->pHead;
	}
	return 1;
}
int isempty(PQUEUE pQueue)
{
	//如果头指针和尾指针相等，则队列为空 
	if (pQueue->pHead == pQueue->pTail)
	{
		return 1;
	}
	return 0;
}
void travers(PQUEUE pQueue)
{
	//判断队列是否为空
	if (isempty(pQueue) == 1)
	{
		return;
	}
	printf("队列元素为：[ ");
	PNODE pCurrentNode = pQueue->pHead->pNext;
	while (pCurrentNode != NULL)
	{
		printf("%d ", pCurrentNode->data);
		pCurrentNode = pCurrentNode->pNext;
	}
	printf("]\n");
}
void clear(PQUEUE pQueue)
{	
	while(isempty(pQueue) == 0)
	{
		int val = 0;
		outQueue(pQueue, &val);
	}
}

程序运行后，输出如下：

我们看到，整个队列的操作运行结果如上所示。