上文已写队列的顺序存储,本文介绍队列的链式存储
1 队列构造
typedef struct Node{//节点数据
void *data;
struct Node *next;
} Node;
typedef struct Queue//队列构造
{
Node firstNode;
int size;//队列大小
} Queue;
2 队列初始化
Queue *initQueue()//队列初始化
{
Queue *queue = (Queue *)malloc(sizeof(Queue));//在堆区申请内存
if (queue == NULL)
return NULL; //内存分配失败
queue->firstNode.data = NULL;//初始化
queue->firstNode.next = NULL;
queue->size = 0;
return queue;
}
3 入队列
int push(void *data, Queue *queue) //入队列,本质是尾插
{
if (data == NULL || queue == NULL)
return 0; //空指针判断,入队列失败
Node *node = (Node *)malloc(sizeof(Node));//根据data创建链表节点
node->data = data;
node->next = NULL;
Node *pointer = &queue->firstNode;
while(pointer->next)//当pointer.next为NULL时跳出循环,即pointer已经指向末位节点
pointer = pointer->next;
pointer->next = node;
queue->size++; //队列大小+1
return 1;
}
4 出队列
void *pop(Queue *queue) //出队列,即pop出首个元素
{
if (queue == NULL || queue->size == 0)
return NULL;
Node *popNode = queue->firstNode.next;//首个有效节点即为出队列的节点
queue->firstNode.next = queue->firstNode.next->next;
queue->size--; //队列大小减1
return popNode->data;//返回节点的数据域
}
5 队列空与队列大小判断
int isEmptyQueue(Queue *queue)//判断队列是否为空
{
if (queue == NULL)
return -1;
return queue->size == 0; //空时返回1
}
int sizeOfQueue(Queue *queue)//返回队列的大小
{
if (queue == NULL)
return -1;
return queue->size;
}
6函数测试与运行
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Student//以队列存储Student类型数据为例
{
int id;
char name[20];
} Student;
int main()
{
Student stu[6] = {
{1, "jakes1"},
{2, "jakes2"},
{3, "jakes3"},
{4, "jakes4"},
{5, "jakes5"},
{6, "jakes6"},
};
Queue *queue = initQueue();//队列初始化
int pushCount = 0;
for (int i = 0; i < 6; i++)
{
push(&stu[i], queue);//入队列
printf("第%d次入队列-->id:%d_name:%s\t 队列大小:%d\t队列为空:%d\t\n", ++pushCount, stu[i].id, stu[i].name, sizeOfQueue(queue), isEmptyQueue(queue));
}
puts("\n");
int popCount = 0;
while (!isEmptyQueue(queue))
{
void *popdata = pop(queue);
Student *stu = (Student *)popdata;//出队列
printf("第%d次出队列-->id:%d_name:%s\t 队列大小:%d\t队列为空:%d\t\n", ++popCount, stu->id, stu->name, sizeOfQueue(queue), isEmptyQueue(queue));
free(popdata);
popdata = NULL;
}
return 0;
}
运行结果如下: