1.队列（Queue）是一种特殊的线性数据结构，它遵循FIFO（First In First Out，先进先出）的原则。这意味着元素被添加到队列的末尾（也称为enqueue操作）并从队列的开头被移除（也称为dequeue操作）。
队列的基本操作：
初始化：创建一个空的队列。
入队：在队列的末尾添加一个元素。
出队：从队列的开头移除一个元素并返回它。如果队列为空，此操作通常会导致错误或异常。
检查队列是否为空：检查队列中是否有元素。
查看队首元素：返回队列的第一个元素但不移除它。如果队列为空，此操作可能返回错误或异常。
销毁队列：释放队列所使用的所有内存。
C语言实现队列：
以下是一个简单的队列实现，使用数组作为底层数据结构：
|
#include <stdio.h> |
|
#include <stdlib.h> |
|
#include <stdbool.h> |
|
|
|
#define MAX_SIZE 1000 |
|
|
|
typedef struct Queue { |
|
int front, rear, size; |
|
unsigned capacity; |
|
int* array; |
|
} Queue; |
|
|
|
// 队列初始化 |
|
Queue* createQueue(unsigned capacity) { |
|
Queue* queue = (Queue*) malloc(sizeof(Queue)); |
|
queue->capacity = capacity; |
|
queue->front = queue->size = 0; |
|
queue->rear = capacity - 1; // 初始时，rear指向队列的最后一个位置 |
|
queue->array = (int*) malloc(queue->capacity * sizeof(int)); |
|
return queue; |
|
} |
|
|
|
// 入队操作 |
|
void enqueue(Queue* queue, int item) { |
|
if (queue->size == queue->capacity) return; // 队列满了 |
|
queue->rear = (queue->rear + 1) % queue->capacity; |
|
queue->array[queue->rear] = item; |
|
queue->size++; |
|
printf("%d enqueued to queue\n", item); |
|
} |
|
|
|
// 出队操作 |
|
int dequeue(Queue* queue) { |
|
if (queue->size == 0) return -1; // 队列为空 |
|
int item = queue->array[queue->front]; |
|
queue->front = (queue->front + 1) % queue->capacity; |
|
queue->size--; |
|
return item; |
|
} |
|
|
|
// 检查队列是否为空 |
|
bool isQueueEmpty(Queue* queue) { |
|
return queue->size == 0; |
|
} |
|
|
|
// 查看队首元素 |
|
int front(Queue* queue) { |
|
if (queue->size == 0) return -1; // 队列为空 |
|
return queue->array[queue->front]; |
|
} |
|
|
|
// 销毁队列 |
|
void destroyQueue(Queue* queue) { |
|
free(queue->array); |
|
free(queue); |
|
} |
|
|
|
int main() { |
|
Queue* queue = createQueue(MAX_SIZE); |
|
|
|
enqueue(queue, 10); |
|
enqueue(queue, 20); |
|
enqueue(queue, 30); |
|
|
|
printf("%d dequeued from queue\n\n", dequeue(queue)); |
|
|
|
printf("Front item is %d\n", front(queue)); |
|
|
|
destroyQueue(queue); |
|
|
|
return 0; |
|
} |
注意：上面的代码实现了一个循环队列，其中front和rear都使用模运算来循环回到队列的开头。这种实现方式避免了普通队列中可能出现的空间浪费问题。但是，当队列为空时，我们设定了一个特殊的值（在这里是-1）来表示错误或异常。在实际应用中，你可能需要使用更复杂的错误处理机制。
2.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; |
|
} |
|
|
|
// 判断队列是否为空 |
|
int isEmpty(Queue *q) { |
|
return q->front == q->rear; |
|
} |
|
|
|
// 判断队列是否已满 |
|
int isFull(Queue *q) { |
|
return (q->rear + 1) % MAX_SIZE == q->front; |
|
} |
|
|
|
// 入队操作 |
|
void enqueue(Queue *q, int value) { |
|
if (isFull(q)) { |
|
printf("Queue is full\n"); |
|
return; |
|
} |
|
q->data[q->rear] = value; |
|
q->rear = (q->rear + 1) % MAX_SIZE; |
|
} |
|
|
|
// 出队操作 |
|
int dequeue(Queue *q) { |
|
if (isEmpty(q)) { |
|
printf("Queue is empty\n"); |
|
return -1; |
|
} |
|
int value = q->data[q->front]; |
|
q->front = (q->front + 1) % MAX_SIZE; |
|
return value; |
|
} |
|
|
|
int main() { |
|
Queue q; |
|
initQueue(&q); |
|
|
|
enqueue(&q, 10); |
|
enqueue(&q, 20); |
|
enqueue(&q, 30); |
|
|
|
printf("Dequeued item: %d\n", dequeue(&q)); |
|
printf("Dequeued item: %d\n", dequeue(&q)); |
|
|
|
return 0; |
|
} |
基于链表的动态队列
动态队列意味着队列的大小可以在运行时改变。
|
#include <stdio.h> |
|
#include <stdlib.h> |
|
|
|
typedef struct Node { |
|
int data; |
|
struct Node* next; |
|
} Node; |
|
|
|
typedef struct { |
|
Node* front; |
|
Node* rear; |
|
} Queue; |
|
|
|
// 创建新节点 |
|
Node* createNode(int data) { |
|
Node* newNode = (Node*)malloc(sizeof(Node)); |
|
if (!newNode) { |
|
printf("Memory allocation failed\n"); |
|
exit(1); |
|
} |
|
newNode->data = data; |
|
newNode->next = NULL; |
|
return newNode; |
|
} |
|
|
|
// 初始化队列 |
|
void initQueue(Queue* q) { |
|
q->front = q->rear = NULL; |
|
} |
|
|
|
// 判断队列是否为空 |
|
int isEmpty(Queue* q) { |
|
return q->front == NULL; |
|
} |
|
|
|
// 入队操作 |
|
void enqueue(Queue* q, int data) { |
|
Node* newNode = createNode(data); |
|
if (isEmpty(q)) { |
|
q->front = q->rear = newNode; |
|
} else { |
|
q->rear->next = newNode; |
|
q->rear = newNode; |
|
} |
|
} |
|
|
|
// 出队操作 |
|
int dequeue(Queue* q) { |
|
if (isEmpty(q)) { |
|
printf("Queue is empty\n"); |
|
return -1; |
|
} |
|
int data = q->front->data; |
|
Node* temp = q->front; |
|
q->front = q->front->next; |
|
|
|
if (q->front == NULL) { |
|
q->rear = NULL; |
|
} |
|
|
|
free(temp); |
|
return data; |
|
} |
|
|
|
int main() { |
|
Queue q; |
|
initQueue(&q); |
|
|
|
enqueue(&q, 10); |
|
enqueue(&q, 20); |
|
enqueue(&q, 30); |
|
|
|
printf("Dequeued item: %d\n", dequeue(&q)); |
|
printf("Dequeued item: %d\n", dequeue(&q)); |
|
|
|
return 0; |
|
} |
在上面的代码中，基于数组的队列使用循环队列的实现方式，当rear到达数组的末尾时，它会循环回到数组的开始。这种方式避免了浪费数组中的任何空间。
基于链表的队列则更为灵活，因为可以在运行时动态地添加和删除节点。这种方式没有固定的大小限制，但是需要额外的空间来存储节点指针，并且需要处理内存分配和释放的问题。
3.循环队列是一种避免非环形队列中做出队操作时的数据搬移的队列。它通过使用取模操作来实现当队列满时，队尾指针重新指向队列开始的位置，形成一个环形的结构。同样地，当队列为空做了入队操作，队头指针也会重新指向队尾的位置。这样，我们就可以有效地利用数组空间，避免数据搬移带来的额外开销。
以下是C语言中循环队列的实现：
|
#include <stdio.h> |
|
#define QUEUE_SIZE 1000 // 定义队列大小 |
|
|
|
typedef struct { |
|
int data[QUEUE_SIZE]; |
|
int front; // 队头指针 |
|
int rear; // 队尾指针 |
|
} CycleQueue; |
|
|
|
// 初始化队列 |
|
void initQueue(CycleQueue *queue) { |
|
queue->front = 0; |
|
queue->rear = 0; |
|
} |
|
|
|
// 判断队列是否为空 |
|
int isEmpty(CycleQueue *queue) { |
|
return queue->front == queue->rear; |
|
} |
|
|
|
// 判断队列是否已满 |
|
int isFull(CycleQueue *queue) { |
|
return (queue->rear + 1) % QUEUE_SIZE == queue->front; |
|
} |
|
|
|
// 入队操作 |
|
void enqueue(CycleQueue *queue, int value) { |
|
if (isFull(queue)) { |
|
printf("Queue is full\n"); |
|
return; |
|
} |
|
queue->data[queue->rear] = value; |
|
queue->rear = (queue->rear + 1) % QUEUE_SIZE; // 更新队尾指针 |
|
} |
|
|
|
// 出队操作 |
|
int dequeue(CycleQueue *queue) { |
|
if (isEmpty(queue)) { |
|
printf("Queue is empty\n"); |
|
return -1; |
|
} |
|
int value = queue->data[queue->front]; |
|
queue->front = (queue->front + 1) % QUEUE_SIZE; // 更新队头指针 |
|
return value; |
|
} |
|
|
|
int main() { |
|
CycleQueue queue; |
|
initQueue(&queue); |
|
|
|
// 入队几个元素 |
|
enqueue(&queue, 1); |
|
enqueue(&queue, 2); |
|
enqueue(&queue, 3); |
|
|
|
// 出队并打印元素 |
|
printf("Dequeued item: %d\n", dequeue(&queue)); |
|
printf("Dequeued item: %d\n", dequeue(&queue)); |
|
|
|
// 再次入队一个元素 |
|
enqueue(&queue, 4); |
|
|
|
// 出队并打印剩余元素 |
|
printf("Dequeued item: %d\n", dequeue(&queue)); |
|
|
|
return 0; |
|
} |
在这段代码中，我们定义了一个结构体CycleQueue来表示循环队列，其中data数组用于存储队列中的元素，front和rear分别表示队头和队尾的指针。initQueue函数用于初始化队列，isEmpty和isFull函数分别用于判断队列是否为空和满，enqueue和dequeue函数分别用于入队和出队操作。
注意，在进行入队和出队操作时，我们需要对队尾和队头指针进行取模操作，以确保指针始终在数组范围内循环移动。这样，当队列满时，新的元素可以覆盖掉队头位置已经出队的元素的空间，达到循环使用的效果。同样地，当队列为空时，出队操作会导致队头指针移动到队尾的位置，等待新的元素入队。
