做外汇应该看哪一家网站,谁会写网站代码,成都的网站建设开发公司,4399小游戏网页版在线欢迎各位看官^_^ 目录
1.队列的定义
2.队列的基本操作
2.1初始化队列
2.2判断队列是否为空
2.3判断队列是否已满
2.4入队
2.5出队
2.6完整代码
3.队列的顺序实现
4.队列的链式存储
5.双端队列
6.循环队列 1.队列的定义 队列#xff08;Queue#xff09;是一种先… 欢迎各位看官^_^ 目录
1.队列的定义
2.队列的基本操作
2.1初始化队列
2.2判断队列是否为空
2.3判断队列是否已满
2.4入队
2.5出队
2.6完整代码
3.队列的顺序实现
4.队列的链式存储
5.双端队列
6.循环队列 1.队列的定义 队列Queue是一种先进先出First In First OutFIFO的线性数据结构它只允许在队尾添加元素在队头删除元素不支持随机访问。队列常用的操作有入队enqueue、出队dequeue、队列长度size、队列是否为空empty等。队列可以用来实现很多算法如广度优先搜索算法BFS和消息传递等。
2.队列的基本操作
2.1初始化队列 可以使用数组或链表来实现队列。对于数组我们可以定义一个数组和两个指针front和rear来表示队列。对于链表我们可以创建一个链表并定义头节点指针和尾节点指针。队列是一种线性数据结构可以用数组或链表来实现。
以下是用数组实现队列的C语言代码示例
#include stdio.h#define MAX_SIZE 100int queue[MAX_SIZE];
int front 0, rear -1;void enqueue(int data) {if (rear MAX_SIZE - 1) {printf(Queue overflow\n);} else {rear;queue[rear] data;}
}int dequeue() {if (front rear) {printf(Queue underflow\n);return -1;} else {int data queue[front];front;return data;}
}int main() {enqueue(10);enqueue(20);enqueue(30);printf(%d , dequeue());printf(%d , dequeue());printf(%d , dequeue());printf(%d , dequeue());return 0;
}上述代码中queue为数组front和rear分别表示队列的前后指针初始化为0和-1。enqueue函数用于向队列中添加元素先判断队列是否已满若未满则将数据存入队列尾部。dequeue函数用于弹出队列头部元素先判断队列是否为空若非空则返回队列头部元素并将front指针后移一位。在main函数中先将元素10、20、30添加到队列中然后依次弹出队列头部元素并输出。
2.2判断队列是否为空
如果队列为空则front和rear指向同一个位置。
// 判断队列是否为空
int is_empty() {return front rear;
}
2.3判断队列是否已满
如果队列已满则rear指向的下一个位置就是front因为它是循环队列。
// 判断队列是否已满
int is_full() {return (rear 1) % MAX_SIZE front;
}2.4入队
当队列不满时我们将元素插入队列的rear位置并将rear指针后移。
// 入队
void enqueue(int data) {if (is_full()) {printf(Queue is full.\n);return;}queue[rear] data;rear (rear 1) % MAX_SIZE;
}2.5出队
当队列不为空时我们将front指向的元素从队列中删除并将front指针后移。
// 出队
int dequeue() {if (is_empty()) {printf(Queue is empty.\n);return -1;}int data queue[front];front (front 1) % MAX_SIZE;return data;
}2.6完整代码
#include stdio.h
#define MAX_SIZE 10 // 定义队列的最大容量为10int queue[MAX_SIZE]; // 定义数组队列
int front 0, rear 0; // front指向队首rear指向队尾的下一个位置// 判断队列是否为空
int is_empty() {return front rear;
}// 判断队列是否已满
int is_full() {return (rear 1) % MAX_SIZE front;
}// 入队
void enqueue(int data) {if (is_full()) {printf(Queue is full.\n);return;}queue[rear] data;rear (rear 1) % MAX_SIZE;
}// 出队
int dequeue() {if (is_empty()) {printf(Queue is empty.\n);return -1;}int data queue[front];front (front 1) % MAX_SIZE;return data;
}int main() {enqueue(1);enqueue(2);enqueue(3);printf(%d\n, dequeue());printf(%d\n, dequeue());enqueue(4);printf(%d\n, dequeue());printf(%d\n, dequeue());return 0;
}注意这是一个循环队列在计算rear的位置时需要使用取模运算。这是因为数组的最后一个位置后面没有下一个位置我们需要将rear回到数组的开头位置。
3.队列的顺序实现
C语言队列的顺序实现可以使用数组来实现。实现思路如下
定义一个数组和队列头尾指针。队列头指针指向队列的第一个元素队列尾指针指向队列的最后一个元素。入队操作时先判断队列是否已满如果已满则提示队列已满否则将元素加入到队列尾部并更新队列尾指针。出队操作时先判断队列是否为空如果为空则提示队列为空否则将队列头部的元素出队并更新队列头指针。获取队列头元素时先判断队列是否为空如果为空则提示队列为空否则返回队列头的元素。
以下是C语言队列的顺序实现示例代码
#include stdio.h
#define MAX_SIZE 100// 定义队列结构体
typedef struct {int data[MAX_SIZE]; // 存储队列的数组int front; // 队列头指针int rear; // 队列尾指针
} Queue;// 初始化队列
void initQueue(Queue *q) {q-front q-rear 0;
}// 入队
void enqueue(Queue *q, int x) {if ((q-rear 1) % MAX_SIZE q-front) {printf(Queue is full.\n);} else {q-data[q-rear] x;q-rear (q-rear 1) % MAX_SIZE;}
}// 出队
void dequeue(Queue *q) {if (q-front q-rear) {printf(Queue is empty.\n);} else {q-front (q-front 1) % MAX_SIZE;}
}// 获取队列头元素
int front(Queue *q) {if (q-front q-rear) {printf(Queue is empty.\n);return -1;} else {return q-data[q-front];}
}// 判断队列是否为空
int isEmpty(Queue *q) {return q-front q-rear;
}int main() {Queue q;initQueue(q);// 入队enqueue(q, 1);enqueue(q, 2);enqueue(q, 3);// 获取队列头元素printf(Front of queue: %d\n, front(q));// 出队dequeue(q);// 获取队列头元素printf(Front of queue: %d\n, front(q));return 0;
}4.队列的链式存储 队列和链表的关系队列和链表是两种不同的数据结构但是在实现队列时可以使用链表来表示。队列是一种先进先出First In First OutFIFO的数据结构可以理解为是一条通道从一端队尾加入数据从另一端队头取出数据。而链表是一种动态数据结构由节点之间的指针连接而成。每个节点包含一个数据元素和一个指向下一个节点的指针。在使用链表实现队列时可以将链表的头作为队列的队头将链表的尾作为队列的队尾使用链表的头插法或尾插法对队列进行入队操作使用链表的尾删除或头删除对队列进行出队操作。因此可以说队列和链表有一定的关系但二者仍然是不同的数据结构。 队列的链式存储是使用链表来实现队列的存储结构。队列的链式存储结构可以分为单向链表和双向链表两种。 单向链表的存储结构是每个节点包含一个数据元素和一个指向下一个节点的指针。队列的头指针指向链表的头节点队列的尾指针指向链表的尾节点。入队操作将元素添加到尾节点之后出队操作则删除头节点。 双向链表的存储结构是每个节点包含一个数据元素、一个指向前一个节点的指针和一个指向下一个节点的指针。队列的头指针指向链表头部队列的尾指针指向链表尾部。入队操作将元素添加到尾节点之后出队操作则删除头节点。 链式存储相比于顺序存储的优势在于可以更灵活地插入和删除元素但是在访问元素时需要通过指针遍历链表效率较低。 链式存储结构的队列通常包含一个头结点和一个尾结点其中头结点指向队列的头部尾结点指向队列的尾部。每个结点都包含一个数据域和一个指针域指针域指向下一个结点。
以下是C语言实现队列的链式存储的示例代码
#include stdio.h
#include stdlib.h// 队列结点定义
typedef struct queue_node{int data; // 数据域struct queue_node *next; // 指针域
} queue_node;// 队列定义
typedef struct {queue_node *front; // 队列头指针queue_node *rear; // 队列尾指针
} queue;// 初始化队列
void init_queue(queue *q)
{// 分配头结点q-front q-rear (queue_node *)malloc(sizeof(queue_node));if (!q-front) {printf(Memory allocation failed.\n);exit(-1);}q-front-next NULL;
}// 判断队列是否为空
int is_empty(queue *q)
{return q-front q-rear;
}// 入队
void enqueue(queue *q, int data)
{queue_node *new_node (queue_node *)malloc(sizeof(queue_node));if (!new_node) {printf(Memory allocation failed.\n);exit(-1);}new_node-data data;new_node-next NULL;q-rear-next new_node;q-rear new_node;
}// 出队
int dequeue(queue *q)
{if (is_empty(q)) {printf(Queue is empty.\n);exit(-1);}queue_node *p q-front-next;int data p-data;q-front-next p-next;if (q-rear p) {q-rear q-front;}free(p);return data;
}// 输出队列中元素
void print_queue(queue *q)
{queue_node *p q-front-next;while (p) {printf(%d , p-data);p p-next;}printf(\n);
}int main()
{queue q;init_queue(q);for (int i 1; i 5; i) {enqueue(q, i);}print_queue(q);dequeue(q);print_queue(q);return 0;
}5.双端队列 双端队列deque全名double-ended queue是一种具有队列和栈的性质的数据结构即两端都可以进行插入和删除操作。 双端队列有两个端点一个是“前端”front可以进行“出队”操作另一个是“后端”rear可以进行“入队”操作。因此双端队列支持的操作包括入队、出队、队头入队、队尾入队、队头出队、队尾出队等。 与单端队列相比双端队列的优势在于可以自由地从两端添加或删除元素更加灵活、方便地实现某些算法和数据结构。例如在实现图遍历算法中使用双端队列可以使得遍历的顺序更加合理减少搜索的时间和空间复杂度。 另外双端队列支持一些其他的操作如获取队列长度、获取队头/尾元素等。
以下是C语言实现双端队列的代码
#include stdio.h
#include stdlib.h
#include stdbool.h// 双端队列节点结构体
typedef struct DequeNode {int val;struct DequeNode* next;struct DequeNode* prev;
} DequeNode;// 双端队列结构体
typedef struct Deque {DequeNode* front; // 队头指针DequeNode* rear; // 队尾指针int size; // 队列元素个数
} Deque;// 初始化双端队列
void initDeque(Deque* deque) {deque-front NULL;deque-rear NULL;deque-size 0;
}// 判断双端队列是否为空
bool isEmptyDeque(Deque* deque) {return deque-size 0;
}// 获取双端队列的长度
int sizeDeque(Deque* deque) {return deque-size;
}// 获取双端队列队头元素
int frontDeque(Deque* deque) {return deque-front-val;
}// 获取双端队列队尾元素
int rearDeque(Deque* deque) {return deque-rear-val;
}// 在双端队列前端插入元素
void addFrontDeque(Deque* deque, int val) {DequeNode* new_node (DequeNode*)malloc(sizeof(DequeNode));new_node-val val;new_node-next deque-front;new_node-prev NULL;if (deque-front ! NULL) {deque-front-prev new_node;}deque-front new_node;if (deque-rear NULL) {deque-rear new_node;}deque-size;
}// 在双端队列后端插入元素
void addRearDeque(Deque* deque, int val) {DequeNode* new_node (DequeNode*)malloc(sizeof(DequeNode));new_node-val val;new_node-next NULL;new_node-prev deque-rear;if (deque-rear ! NULL) {deque-rear-next new_node;}deque-rear new_node;if (deque-front NULL) {deque-front new_node;}deque-size;
}// 在双端队列前端删除元素
void removeFrontDeque(Deque* deque) {if (deque-front NULL) {return;}DequeNode* temp deque-front;deque-front deque-front-next;if (deque-front ! NULL) {deque-front-prev NULL;} else {deque-rear NULL;}free(temp);deque-size--;
}// 在双端队列后端删除元素
void removeRearDeque(Deque* deque) {if (deque-rear NULL) {return;}DequeNode* temp deque-rear;deque-rear deque-rear-prev;if (deque-rear ! NULL) {deque-rear-next NULL;} else {deque-front NULL;}free(temp);deque-size--;
}// 测试
int main() {Deque deque;initDeque(deque);addFrontDeque(deque, 1);addRearDeque(deque, 2);addFrontDeque(deque, 3);addRearDeque(deque, 4);while (!isEmptyDeque(deque)) {printf(%d , frontDeque(deque));removeFrontDeque(deque);}printf(\n);return 0;
}6.循环队列 循环队列是一种环形数据结构它允许在一端添加数据元素同时在另一端删除数据元素。与线性队列不同的是在循环队列中队头和队尾是可以相互穿越的。这意味着队列的末尾可以连接到队列的开始形成一个环。这样可以使用有限的空间存储无限数量的数据元素。 循环队列通常使用数组来实现。它有一个前后指针称为队头和队尾。入队操作时将新元素加入队尾并将队尾指针向后移动。出队操作时将队头元素删除并将队头指针向后移动。当队列满时新元素无法插入即使队列前面有空位置。当队列为空时无法删除元素。 循环队列的主要优点是可以避免队列的前面空出大量空间同时保证队列的顺序性和完整性。缺点是在实现时需要注意控制队列满和空的情况以及指针的计算。 循环队列是一种特殊的队列其队尾指针指向数组的末尾后会回到数组的开头实现队列的循环利用。下面是C语言实现循环队列的示例代码
#include stdio.h
#include stdlib.h#define QUEUE_MAX_SIZE 5 // 队列的最大容量typedef struct {int* data; // 队列数据存储的位置int front; // 队首指针int rear; // 队尾指针
} Queue;// 初始化队列
void InitQueue(Queue* q) {q-data (int*)malloc(QUEUE_MAX_SIZE * sizeof(int)); // 分配队列空间q-front q-rear 0; // 初始化队首和队尾指针
}// 判断队列是否为空
int IsEmpty(Queue* q) {return q-front q-rear;
}// 判断队列是否已满
int IsFull(Queue* q) {return (q-rear 1) % QUEUE_MAX_SIZE q-front;
}// 入队操作
int EnQueue(Queue* q, int value) {if (IsFull(q)) {return 0; // 队列已满无法入队}q-data[q-rear] value; // 将数据存入队列q-rear (q-rear 1) % QUEUE_MAX_SIZE; // 队尾指针后移return 1; // 入队成功
}// 出队操作
int DeQueue(Queue* q, int* value) {if (IsEmpty(q)) {return 0; // 队列为空无法出队}*value q-data[q-front]; // 取出队首数据q-front (q-front 1) % QUEUE_MAX_SIZE; // 队首指针后移return 1; // 出队成功
}// 获取队首元素
int GetFront(Queue* q, int* value) {if (IsEmpty(q)) {return 0; // 队列为空无法获取队首元素}*value q-data[q-front]; // 获取队首元素return 1; // 获取成功
}// 获取队列长度
int GetLength(Queue* q) {return (q-rear - q-front QUEUE_MAX_SIZE) % QUEUE_MAX_SIZE;
}// 输出队列中的所有元素
void PrintQueue(Queue* q) {int i, len GetLength(q);for (i 0; i len; i) {int value;DeQueue(q, value);printf(%d , value);EnQueue(q, value);}printf(\n);
}// 测试代码
int main() {Queue q;InitQueue(q);EnQueue(q, 1);EnQueue(q, 2);EnQueue(q, 3);EnQueue(q, 4);EnQueue(q, 5);printf(Queue length: %d\n, GetLength(q)); // 5printf(Queue content: );PrintQueue(q); // 1 2 3 4 5int value;DeQueue(q, value);printf(DeQueue value: %d\n, value); // 1printf(Queue content: );PrintQueue(q); // 2 3 4 5EnQueue(q 在上面的代码中我们实现了循环队列的初始化、判断是否为空或已满、入队、出队、获取队首元素、获取队列长度和输出队列中的所有元素等操作。我们可以通过这些操作对循环队列进行基本的操作。 ❤️❤️❤️栈的知识点总结就到这里啦如果对博文还满意的话劳烦各位看官动动“发财的小手”留下您对博文的赞和对博主的关注吧❤️❤️❤️
