列可以想象成一种特殊的栈,我们在前面提到,栈遵循的原则是后进先出,列遵循的原则则是先进先出。
列只允许在一端进行插入数据 *** 作,在另一端进行删除数据 *** 作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列。
进行插入 *** 作的一端称为队尾。
出队列:进行删除 *** 作的一端称为队头。
那我们接下来就直接开始实现列吧。
首先明确一下我们需要实现哪些函数。
首先有一个初始化列的函数,一个入列的函数,一个出列的函数,一个显示列头的函数,一个显示列尾的函数,然后是一个获取列中有效元素个数的函数,然后是判断列是否为空的函数,以及销毁列的函数。
最后,为了方便显示结果,再实现一个列显示的函数。
typedef int QDataType;
// 链式结构:表示队列
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* front;
QNode* tail;
}Queue;
初始化队列
// 初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
QNode* tmp1 = (QNode*)malloc(sizeof(QNode));
QNode* tmp2 = (QNode*)malloc(sizeof(QNode));
if (tmp1 == NULL || tmp2 == NULL)
{
printf("Malloc Fail In QueueInit!\n");
exit(-1);
}
tmp1->next = NULL;
tmp2 = tmp1;
pq->front = tmp1;
pq->tail = tmp2;
}
入队列
// 队尾入队列
void QueuePush(Queue* pq, QDataType data)
{
assert(pq);
QNode* tmp = (QNode*)malloc(sizeof(QNode));
if (tmp == NULL)
{
printf("Malloc Fail In QueuePush!\n");
exit(-1);
}
(pq->tail)->data = data;
(pq->tail)->next = tmp;
pq->tail = tmp;
}
出队列
// 队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
if (pq->tail == pq->front)
return;
QNode* tmp = pq->front;
pq->front = (pq->front)->next;
free(tmp);
tmp = NULL;
}
获取头尾元素
// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
if (pq->front == pq->tail)
{
printf("Nothing!\n");
exit(-1);
}
return (pq->front)->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
if (pq->front == pq->tail)
{
printf("Nothing!\n");
exit(-1);
}
QNode* tmp = pq->front;
while (tmp->next != pq->tail)
tmp = tmp->next;
return tmp->data;
}
有效元素个数
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
if (pq->front == pq->tail)
return 0;
int num = 1;
QNode* tmp = pq->front;
while (tmp->next != pq->front)
{
tmp = tmp->next;
num++;
}
return num;
}
列判空
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
int QueueEmpty(Queue* pq)
{
assert(pq);
return pq->front == pq->tail;
}
列销毁
// 销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* tmp = pq->front;
QNode* next = tmp;
while (tmp != pq->tail)
{
next = tmp->next;
free(tmp);
tmp = next;
}
free(tmp);
next = tmp = NULL;
}
列打印
void QueuePrint(Queue* pq)
{
assert(pq);
if (pq->front != pq->tail)
{
QNode* tmp = pq->front;
do
{
printf("%d ", tmp->data);
tmp = tmp->next;
} while (tmp != pq->tail);
}
else
printf("Nothing!");
printf("\n");
}
测试
我们对代码进行测试
void test()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
QueuePush(&q, 6);
QueuePrint(&q);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
QueuePrint(&q);
printf("%d\n", QueueEmpty(&q));
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
printf("%d\n", QueueEmpty(&q));
QueuePrint(&q);
}
显示结果正常。
我发现写代码的人真是很神奇。
明明就是一个星期前写的代码,但是当你拿到他的时候,你会忘掉是自己写的。
以前我总是觉得我很难有东西去写成博客,但是或许是我想写博客的时候已经忘了我写了什么。
我想弄一个读书笔记的系列。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)