数据结构之Queue的实现

**数据结构之Queue的实现**

在计算机科学中，队列（Queue）是一种线性数据结构，它遵循先进先出（FIFO）的原则。也就是说，队列中的元素按照它们进入队列的顺序被访问和移除。

在本文中，我们将讨论队列的基本概念、实现方法以及相关代码示例。

**队列的基本概念**

队列是一种线性数据结构，它有以下几个特点：

1. **先进先出（FIFO）**: 队列中的元素按照它们进入队列的顺序被访问和移除。
2. **入队（Enqueue）**: 将新元素添加到队列尾部。
3. **出队（Dequeue）**: 移除队列头部的元素。
4. **查看队首元素（Peek）**: 查看队列头部的元素，但不移除。

**队列的实现方法**

队列可以使用数组或链表来实现。下面我们将分别讨论这两种实现方法。

### 队列使用数组实现当使用数组实现队列时，我们需要维护一个指针来表示当前队首元素的位置。入队和出队操作涉及到移动这个指针以及更新相关数据结构。

ctypedef struct {
 int* data;
 int front; // 队首元素的索引 int rear; // 队尾元素的索引 int size; // 队列中元素的数量} Queue;

void initQueue(Queue* q) {
 q->data = (int*)malloc(10 * sizeof(int));
 q->front = -1;
 q->rear = -1;
 q->size =0;
}

// 入队操作void enqueue(Queue* q, int value) {
 if (q->size ==10) {
 printf("Queue is full!
");
 return;
 }
 if (q->front == -1 && q->rear == -1) {
 q->data[q->rear++] = value;
 q->size++;
 return;
 }
 q->data[++q->rear] = value;
 q->size++;
}

// 出队操作int dequeue(Queue* q) {
 if (q->front == -1 && q->rear == -1) {
 printf("Queue is empty!
");
 return -1; // 返回-1表示出队失败 }
 int value = q->data[q->front++];
 q->size--;
 return value;
}

// 查看队首元素int peek(Queue* q) {
 if (q->front == -1 && q->rear == -1) {
 printf("Queue is empty!
");
 return -1; // 返回-1表示查看失败 }
 return q->data[q->front];
}

ctypedef struct Node {
 int value;
 struct Node* next;
} Node;

typedef struct {
 Node* head; // 队首元素的指针 Node* tail; // 队尾元素的指针} Queue;

void initQueue(Queue* q) {
 q->head = NULL;
 q->tail = NULL;
}

// 入队操作void enqueue(Queue* q, int value) {
 Node* newNode = (Node*)malloc(sizeof(Node));
 newNode->value = value;
 newNode->next = NULL;
 if (q->head == NULL) {
 q->head = newNode;
 q->tail = newNode;
 } else {
 q->tail->next = newNode;
 q->tail = newNode;
 }
}

// 出队操作int dequeue(Queue* q) {
 if (q->head == NULL) {
 printf("Queue is empty!
");
 return -1; // 返回-1表示出队失败 }
 int value = q->head->value;
 Node* temp = q->head;
 q->head = q->head->next;
 if (q->head == NULL) {
 q->tail = NULL;
 }
 free(temp);
 return value;
}

// 查看队首元素int peek(Queue* q) {
 if (q->head == NULL) {
 printf("Queue is empty!
");
 return -1; // 返回-1表示查看失败 }
 return q->head->value;
}