网站建设维护价格,怎么开发微信网站,网站建设公司响应式网站模板,网络安全厂家排名文章目录 一、队列1. 定义2. 基本操作 二、顺序队列三、链式队列0. 链表1. 头文件2. 队列结构体3. 队列的初始化4. 判断队列是否为空5. 入队6. 出队7. 存取队首元素8. 主函数9. 代码整合 堆栈Stack 和 队列Queue是两种非常重要的数据结构#xff0c;两者都是特殊的线性表… 文章目录 一、队列1. 定义2. 基本操作 二、顺序队列三、链式队列0. 链表1. 头文件2. 队列结构体3. 队列的初始化4. 判断队列是否为空5. 入队6. 出队7. 存取队首元素8. 主函数9. 代码整合 堆栈Stack 和 队列Queue是两种非常重要的数据结构两者都是特殊的线性表 对于堆栈所有的插入和删除以至几乎所有的存取都是在表的同一端进行对于队列所有的插入都是在表的一端进行所有的删除以至几乎所有的存取都是在表的另一端进行。 一、队列
1. 定义 队列是一种操作受限的线性表对于它的所有插入都在表的一端进行所有的删除以至几乎所有的存取都在表的另一端进行且这些操作又都是按照先进先出FIFO的原则进行的。进行删除的一端称为队头front进行插入的一端称为队尾rear。没有元素的队列称为空队列简称空队。 队列就像生活中排队购物新来的人只能加入队尾假设不允许插队购物结束后先离开的总是队头假设无人中途离队。也就是说先加入队列的成员总是先离开队列因此队列被称为先进先出First In First Out的线性表简称为FIFO表。如图在空队列中依次加入元素a1a2a3a4a5出队次序仍然是a1a2a3a4a5 .
2. 基本操作 队列是受限的线性表其基本操作包括 IsEmpty() : 判断队列是否为空isFull()判断队列是否为满enqueue() 向队尾添加元素入队dequeue() 删除队首元素出队peek()获取队首的元素值存取 同普通线性表一样队列也可以用顺序存储和链接存储两种方式来实现
二、顺序队列 参考前文线性表八队列顺序队列及其基本操作初始化、判空、判满、入队、出队、存取队首元素
三、链式队列 用链接存储方式实现的队列称为链式队列。队列的主要操作都在队首和队尾进行所以链式队列应包含两个指针队首指针front和队尾指针rear分别存放队首和队尾结点的地址信息。链式队列中没有哨位结点。 分析链式队列的结构不难看出当创建一个链式队列时队列的首尾指针均为NULL。
0. 链表 参考前文线性表二单链表及其基本操作创建、插入、删除、修改、遍历打印
1. 头文件
#include stdio.h
#include stdlib.h两个头文件 stdio.h用于输入输出操作stdlib.h用于内存分配和释放
2. 队列结构体
// 定义队列节点
typedef struct Node {int data;struct Node* next;
} Node;// 定义链式队列
typedef struct Queue {Node* front; // 队头指针Node* rear; // 队尾指针
} Queue;Node 结构体表示队列的节点 包含一个整数类型的数据成员 data以及一个指向下一个节点的指针 next。 Queue 结构体表示链式队列 包含两个指针成员 front 和 rear分别指向队头和队尾节点。
3. 队列的初始化
void initQueue(Queue* queue) {queue-front NULL;queue-rear NULL;
}将队头和队尾指针都设置为 NULL表示队列为空。
4. 判断队列是否为空
int isQueueEmpty(Queue* queue) {return queue-front NULL;
}如果队头指针为空即 front 为 NULL则队列为空返回值为 1否则返回值为 0。
5. 入队
void enqueue(Queue* queue, int data) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data data;newNode-next NULL;if (isQueueEmpty(queue)) {queue-front newNode;queue-rear newNode;} else {queue-rear-next newNode;queue-rear newNode;}
}创建一个新的节点并将数据存储在新节点的 data 成员中将新节点的 next 指针设置为 NULL。根据队列是否为空将新节点插入队列的末尾。 如果队列为空即队头指针和队尾指针都为空那么将队头和队尾指针都指向新节点。如果队列不为空即队尾指针不为空则将队尾节点的 next 指针指向新节点并更新队尾指针为新节点。
6. 出队
int dequeue(Queue* queue) {if (isQueueEmpty(queue)) {printf(Error: Queue is empty\n);return -1;}Node* temp queue-front;int data temp-data;queue-front queue-front-next;free(temp);if (queue-front NULL) {queue-rear NULL;}return data;
}dequeue 函数用于将元素出队并返回出队的元素值。
判断队列是否为空 如果为空则打印错误信息并返回 -1。如果队列不为空则获取队头节点的数据值然后更新队头指针为下一个节点并释放原来的队头节点的内存空间。 如果队头指针更新后为空则表示队列已经为空将队尾指针也设置为空。最后返回出队的数据值。
7. 存取队首元素
int peek(Queue* queue) {if (isQueueEmpty(queue)) {printf(Error: Queue is empty\n);return -1;}return queue-front-data;
}peek 函数用于获取队列的队首元素值但不进行出队操作。
判断队列是否为空 如果为空则打印错误信息并返回 -1。如果队列不为空则直接返回队头节点的数据值。
8. 主函数
int main() {Queue queue;initQueue(queue);enqueue(queue, 10);enqueue(queue, 20);enqueue(queue, 30);printf(Peek: %d\n, peek(queue));printf(Dequeued: %d\n, dequeue(queue));printf(Dequeued: %d\n, dequeue(queue));printf(Peek: %d\n, peek(queue));enqueue(queue, 40);printf(Peek: %d\n, peek(queue));return 0;
}声明 Queue 类型的变量 queue并调用 initQueue 函数对其进行初始化使用 enqueue 函数将三个元素10、20、30依次入队使用 peek 函数获取队首元素并打印使用 dequeue 函数进行两次出队操作并使打印出队的元素值使用 peek 函数获取队首元素并打印使用 enqueue 函数将元素 40 入队使用 peek 函数获取队首元素并打印。 9. 代码整合
#include stdio.h
#include stdlib.h// 定义队列节点
typedef struct Node {int data;struct Node* next;
} Node;// 定义链式队列
typedef struct Queue {Node* front; // 队头指针Node* rear; // 队尾指针
} Queue;// 初始化链式队列
void initQueue(Queue* queue) {queue-front NULL;queue-rear NULL;
}// 判断链式队列是否为空
int isQueueEmpty(Queue* queue) {return queue-front NULL;
}// 入队
void enqueue(Queue* queue, int data) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data data;newNode-next NULL;if (isQueueEmpty(queue)) {queue-front newNode;queue-rear newNode;} else {queue-rear-next newNode;queue-rear newNode;}
}// 出队
int dequeue(Queue* queue) {if (isQueueEmpty(queue)) {printf(Error: Queue is empty\n);return -1;}Node* temp queue-front;int data temp-data;queue-front queue-front-next;free(temp);if (queue-front NULL) {queue-rear NULL;}return data;
}// 获取队首元素
int peek(Queue* queue) {if (isQueueEmpty(queue)) {printf(Error: Queue is empty\n);return -1;}return queue-front-data;
}
int main() {Queue queue;initQueue(queue);enqueue(queue, 10);enqueue(queue, 20);enqueue(queue, 30);printf(Peek: %d\n, peek(queue));printf(Dequeued: %d\n, dequeue(queue));printf(Dequeued: %d\n, dequeue(queue));printf(Peek: %d\n, peek(queue));enqueue(queue, 40);printf(Peek: %d\n, peek(queue));return 0;
}
