计算机队列模型怎么做的

时间:2025-01-20 07:43:50 计算机

计算机队列模型可以通过多种数据结构和算法来实现,以下是几种常见的队列模型及其实现方法:

普通队列(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;

}

```

这个示例展示了如何使用数组实现一个简单的循环队列,包括入队、出队和打印队列元素的操作。可以根据具体需求扩展这个基础结构,例如添加更多的队列操作函数,或者使用链表来实现队列