计算机队列模型可以通过多种数据结构和算法来实现,以下是几种常见的队列模型及其实现方法:
普通队列(FIFO Queue)
数组实现:使用数组来存储元素,`rear`指向队尾元素,`front`指向队首元素。入队操作在队尾添加元素,出队操作在队首移除元素。
链表实现:使用单向链表,`rear`指向队尾节点,`front`指向队首节点。入队操作在队尾添加节点,出队操作在队首移除节点。
循环队列(Circular Queue)
数组实现:使用固定大小的数组,通过取余操作实现循环利用空间。`rear`指向队尾元素的下一个位置,`front`指向队首元素。当`rear`到达数组末尾时,`rear`变为0。
链表实现:与顺序队列类似,但使用链表实现循环利用空间。
优先队列(Priority Queue)
数组实现:使用数组存储元素,每个元素包含一个优先级值。入队时按优先级插入,出队时移除优先级最高的元素。
堆实现:使用二叉堆(最小堆或最大堆)实现优先队列,入队和出队操作的时间复杂度为O(log n)。
双端队列(Deque, Double Ended Queue)
数组实现:使用数组存储元素,支持从队列的两端进行入队和出队操作。
链表实现:使用双向链表实现双端队列,支持从队列的两端进行入队和出队操作。
```c
include include define MAX_SIZE 10 typedef struct { int *array; int front; int rear; int size; int capacity; } Queue; Queue* createQueue(int capacity) { Queue *q = (Queue*)malloc(sizeof(Queue)); q->array = (int*)malloc(capacity * sizeof(int)); q->front = 0; q->rear = 0; q->size = 0; q->capacity = capacity; return q; } int isEmpty(Queue *q) { return q->size == 0; } int isFull(Queue *q) { return q->size == q->capacity; } void enqueue(Queue *q, int data) { if (isFull(q)) { printf("Queue is full.\n"); return; } q->array[q->rear] = data; q->rear = (q->rear + 1) % q->capacity; q->size++; } int dequeue(Queue *q) { if (isEmpty(q)) { printf("Queue is empty.\n"); return -1; // Assuming -1 as an error code } int data = q->array[q->front]; q->front = (q->front + 1) % q->capacity; q->size--; return data; } void printQueue(Queue *q) { if (isEmpty(q)) { printf("Queue is empty.\n"); return; } for (int i = q->front; i != q->rear; i = (i + 1) % q->capacity) { printf("%d ", q->array[i]); } printf("\n"); } int main() { Queue *q = createQueue(MAX_SIZE); enqueue(q, 60); enqueue(q, 70); enqueue(q, 80); enqueue(q, 90); printQueue(q); // Output: 60 70 80 90 dequeue(q); printQueue(q); // Output: 70 80 90 return 0; } ``` 这个示例展示了如何使用数组实现一个简单的循环队列,包括入队、出队和打印队列元素的操作。可以根据具体需求扩展这个基础结构,例如添加更多的队列操作函数,或者使用链表来实现队列