网站排名优化软件学校网站建设调查表

1 静态数组队列

循环队列通常使用数组来实现，判别循环队列是否满或空，可以借助两个变量front和rear。

1. 判空：当front和rear相等时，队列为空。

2. 判满：当(front + 1) % n = rear时，队列为满，其中n为循环队列的长度。需要注意的是，为了区分队列满和队列空的情况，队列中必须要有一个空间不存储元素。

下面是一个简单的循环队列的实现示例：

#define MAXSIZE 10 // 定义循环队列的最大容量typedef struct {int data[MAXSIZE]; // 存储队列元素int front; // 队头指针int rear; // 队尾指针
} CircularQueue;// 初始化循环队列
void initCircularQueue(CircularQueue *q) {q->front = q->rear = 0;
}// 判断循环队列是否为空
bool isEmpty(CircularQueue *q) {return q->front == q->rear;
}// 判断循环队列是否已满
bool isFull(CircularQueue *q) {return (q->rear + 1) % MAXSIZE == q->front;
}

在实现过程中，需要留出一位空间来区分队列为满和队列为空的情况。这里我们设置循环队列的最大容量为MAXSIZE，因此循环队列的存储空间实际上是MAXSIZE-1。当队尾指针rear指向数组最后一个位置时，如果再插入一个元素就会导致rear指向第一个位置，此时队列为满；而当队头指针front和队尾指针rear相同时，队列为空。

2 动态数组队列

动态数组队列是一种数据结构，在队列的基础上，使用动态数组来实现队列的操作。它允许在队列中添加和删除元素，具有先进先出（FIFO）的特点。

在动态数组队列中，元素存储在数组中，并通过一个指针来跟踪队列的头部和尾部。当队列长度增长时，内部数组也随之扩容。相反，当队列长度减小，内部数组也会缩小以减少内存占用。

动态数组队列的时间复杂度如下：

• 入队：O(1) 或 O(n)（需要扩容）
• 出队：O(1)
• 获取队列大小：O(1)

需要注意的是，当需要频繁添加和删除元素时，使用动态数组队列比静态数组队列更加高效。但对于需要快速访问队列任意位置的应用，链表队列可能更适合。

#include <stdio.h>
#include <stdlib.h>// 定义队列结构体
typedef struct queue {int *data;      // 存储队列元素的数组指针int front;      // 队头下标int rear;       // 队尾下标int size;       // 队列大小int capacity;   // 队列容量
} Queue;// 初始化队列
void initQueue(Queue *queue, int capacity) {// 申请存储队列元素的数组空间queue->data = (int*) malloc(sizeof(int) * capacity);if (!queue->data) {printf("Memory allocation failed.\n");exit(1);}// 初始化队列参数queue->front = 0;queue->rear = -1;queue->size = 0;queue->capacity = capacity;
}// 判断队列是否为空
int isEmpty(Queue *queue) {return queue->size == 0;
}// 判断队列是否已满
int isFull(Queue *queue) {return queue->size == queue->capacity;
}// 入队
void enqueue(Queue *queue, int element) {if (isFull(queue)) {printf("Queue is full.\n");return;}// 计算新的队尾下标int newRear = (queue->rear + 1) % queue->capacity;queue->data[newRear] = element;queue->rear = newRear;queue->size++;
}// 出队
int dequeue(Queue *queue) {if (isEmpty(queue)) {printf("Queue is empty.\n");return -1;}int element = queue->data[queue->front];queue->front = (queue->front + 1) % queue->capacity;queue->size--;return element;
}// 打印队列元素
void printQueue(Queue *queue) {if (isEmpty(queue)) {printf("Queue is empty.\n");return;}printf("Queue elements: ");for (int i = 0; i < queue->size; i++) {int index = (queue->front + i) % queue->capacity;printf("%d ", queue->data[index]);}printf("\n");
}// 销毁队列
void destroyQueue(Queue *queue) {free(queue->data);
}int main() {Queue queue;initQueue(&queue, 5);// 入队enqueue(&queue, 1);enqueue(&queue, 2);enqueue(&queue, 3);enqueue(&queue, 4);enqueue(&queue, 5);printQueue(&queue);     // 队列元素: 1 2 3 4 5// 出队dequeue(&queue);dequeue(&queue);printQueue(&queue);     // 队列元素: 3 4 5// 入队enqueue(&queue, 6);enqueue(&queue, 7);printQueue(&queue);     // 队列元素: 3 4 5 6 7destroyQueue(&queue);return 0;
}

链式队列

#include <stdio.h>
#include <stdlib.h>// 定义队列结构体
typedef struct node {int data; // 数据域struct node *next; // 指针域，指向下一个节点
} Node;// 定义队列结构体，包含头节点和尾节点
typedef struct queue {Node *front; // 头节点Node *rear; // 尾节点
} Queue;// 初始化队列
Queue *init() {Queue *q = (Queue*)malloc(sizeof(Queue)); // 创建队列内存空间Node *p = (Node*)malloc(sizeof(Node)); // 创建头节点内存空间p->next = NULL;q->front = p; // 队列的头指针指向头节点q->rear = p; // 队列的尾指针也指向头节点return q;
}// 入队操作
void enqueue(Queue *q, int data) {Node *p = (Node*)malloc(sizeof(Node)); // 创建新节点内存空间p->data = data;p->next = NULL;q->rear->next = p; // 将新节点接到队列尾部q->rear = p; // 更新队列尾指针
}// 出队操作
int dequeue(Queue *q) {if (q->front == q->rear) { // 队列为空printf("queue is empty\n");return -1;}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;
}// 获取队列长度
int length(Queue *q) {int len = 0;Node *p = q->front->next;while (p != NULL) {len++;p = p->next;}return len;
}// 打印队列
void print(Queue *q) {Node *p = q->front->next;printf("queue: ");while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n");
}int main() {Queue *q = init(); // 初始化队列enqueue(q, 1); // 入队操作enqueue(q, 2);enqueue(q, 3);print(q); // 打印队列dequeue(q); // 出队操作print(q); // 打印队列printf("queue length: %d\n", length(q)); // 获取队列长度return 0;
}