数据结构

2024-07-12 05:12| 来源: 网络整理| 查看: 265

队列（queue）是一种采用先进先出(FIFO)策略的抽象数据结构，它的想法来自于生活中排队的策略。顾客在付款结账的时候，按照到来的先后顺序排队结账，先来的顾客先结账，后来的顾客后结账。

这里写图片描述

队列实现

同栈的实现一样，队列的实现也有数组实现和链表实现两种方式。

数组实现

先来看看数组实现的方法。栈使用top变量记录栈顶的位置，而队列则使用front和rear分别队列第一个元素和最后一个元素的位置。

这里写图片描述

#define SIZE 20 typedef struct queue { int arr[SIZE]; int front; int rear; } Queue;

入队、出队操作很简单。入队时，通过rear的位置判断队列是否已满。如果没有满，则将rear后移一位，将新元素放置在rear所在位置。出队时，也可以通过rear的位置判断队列是否为空。如果不空，则只需将front后移一位即可。获取队头元素，判断队列不空，则只需返回front指向位置的元素即可。

哇塞！好简单啊！这样就完成了队列的实现啊！太天真了。。。想一下，通过出队操作将数据弹出队列后，front之前的空间还能够再次得到吗？不能。所以使用普通数组实现队列，就再也不能使用front之前的空间了，这会导致大量空间丢失。

循环数组

为了解决这个问题，将普通数组换成循环数组。在循环数组中，末尾元素的下一个元素不是数组外，而是数组的头元素。这样就能够再次使用front之前的存储空间了。

循环数组

哇塞！有解决了这个问题。可以开始码代码了！且慢，在实现修改入队和出队操作之前，再深思一步，这时是否还能简单通过判断rear的位置来判断队列空或满呢？当然不可以。那是否可以考虑front和rear之间的位置关系呢？考虑如下两种边界情况：

这里写图片描述

在这两种情况下，rear都在front前一个位置，无法判断此时队列满还是空。为了解决这个问题，通常采用的最简单的方法就是，使用一个counter记录队列中元素个数。修改队列定义为下：

#define SIZE 20 typedef struct queue { int arr[SIZE]; int front; int rear; int counter; } Queue; Init(Queue *q) { q->front = 0; q->rear = -1; q->counter = 0; } bool IsFull(Queue *q) { return (q->counter >= SIZE); } void EnQueue(Queue *q, int val) { if(IsFull(q)) return; q->rear = (q->rear + 1) % SIZE; q->arr[q->rear] = val; q->counter++; } bool IsEmpty(Queue *q) { return (q->counter front = (q->front + 1) % SIZE; q->counter--; } //get the front element from queue int Front(Queue *q) { if (IsEmpty(q)) return; return q->arr[q->front]; }

另外一种方法是，在数组中空出一个位置，用以标记队列是否已满。这里写图片描述

这里写图片描述

bool IsFull(Queue *q) { return ((q->rear + 2) % SIZE == q->front); } bool IsEmpty(Queue *q) { return ((q->rear + 1) % SIZE == q->front); }

有时候，rear表示队尾元素的下一个位置，即表示即将插入元素的位置。这里写图片描述

此时，判断队列的操作应该修改如下：

#define SIZE 20 typedef struct queue { int arr[SIZE]; int front; int rear; } Queue; Init(Queue *q) { q->front = 0; q->rear = 0; } bool IsFull(Queue *q) { return ((q->rear + 1) % SIZE == q->front); } void EnQueue(Queue *q, int val) { if(IsFull(q)) return; q->arr[q->rear] = val; q->rear = (q->rear + 1) % SIZE; } bool IsEmpty(Queue *q) { return (q->rear == q->front); } void DeQueue(Queue *q) { if (IsEmpty(q)) return; q->front = (q->front + 1) % SIZE; } int Front(Queue *q) { if (IsEmpty(q)) return; return q->arr[q->front]; } 链表实现

队列的数组实现比较麻烦，需要考虑各种边界情况，所以通常使用链表形式来实现队列。

使用单向链表来实现链式队列，链式队列中存储front和rear即可。

typedef struct node { int val; struct node *next; }Node; typedef struct queue { Node *front; Node *rear; };

为了方便实现，链式队列中的front表示链表的头节点，而front的next才表示队头。链式队列的入队和出队操作如下图所示。从图中可以看出链式队列的实现采用尾进头出的策略。

链式队列

在链式队列中，不需要考虑队列是否已满，只要内存足够就可以一直分配空间。而当front和rear都指向头节点的时候，则表示此时队列为空。

bool IsEmpty(Queue *q) { return (q->front == q->rear); }

入队时移动rear指向最后一个元素即可。

Node* CreateNode(int val) { Node *newNode = (Node*)malloc(sizeof(Node)); if (newNode == NULL) return NULL; else { newNode->val = val; newNode->next = NULL; return newNode; } } void EnQueue(Queue *q, int val) { Node *newNode = CreateNode(val); if (newNode == NULL) return; else { q->rear->next = newNode; q->rear = q->rear->next; } }

出队时，不需要移动front指针，只需将其next指针指向下一个next元素即可。q->front->next = q->front->next->next; 但是需要考虑一种特殊情况，即当队列中只剩下一个元素时，还需要使rear指针重新指向头节点。

int Front(Queue *q) { if (IsEmpty(q)) return -1; else return (q->front->next->val); } void DeQueue(Queue *q) { if (IsEmpty(q)) return; else { Node *deNode = q->front->next; q->front->next = deNode->next; if (q->rear == deNode) //only one element q->rear = q->front; free(deNode); } }

【本文地址】

公司简介

联系我们