通常與堆疊一起教授，隊列也是，抽象資料類型，它們是根據我們在其中執行的操作定義的。堆疊和佇列之間的最大區別在於，它們執行的操作順序，隊列是先進先出（FIRST IN FIRST OUT），即先進先出（FIFO），這意味著，首先進入隊列的東西最先出去，而堆疊是最後進入的FIRST OUT，所以我們最後放入的就是我們第一個回傳的
隊列由三個操作定義：
我們可以把隊列想像成餐廳裡的隊伍，當我們排隊時，我們必須等待前面的每個人都得到服務才能到我們的時間。
這是使用陣列的佇列的簡單實作：
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#define QUEUE_LEN 1024
struct queue_t {
uint32_t data[QUEUE_LEN];
size_t ptr;
};
void enqueue(struct queue_t *queue, uint32_t value)
{
if (queue->ptr + 1 >= QUEUE_LEN)
{
fprintf(stderr, "The queue is full");
exit(1);
}
queue->data[queue->ptr++] = value;
}
uint32_t dequeue(struct queue_t *queue)
{
if (queue->ptr == 0)
{
fprintf(stderr, "Cannot dequeue empty queue");
exit(1);
}
uint32_t val = queue->data[0];
for (size_t i = 1; i < queue->ptr; ++i)
{
queue->data[i - 1] = queue->data[i];
}
queue->ptr--;
return val;
}
uint32_t peek(struct queue_t *queue)
{
if (queue->ptr == 0)
{
fprintf(stderr, "Cannot peek empty queue");
exit(1);
}
return queue->data[0];
}
這裡有一個有趣的實作細節，每當我們出隊時，因為我們要從隊列前面刪除一個元素，
我們必須將以下所有元素移回原處，因此在這個實作中，佇列的複雜度為O(n)，為了避免這種情況，我們需要有一個LinkedList 作為底層資料結構，透過這樣做，我們可以只移動指向下一個的頭指針，而不必執行所有這些操作。
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
struct node_t {
uint32_t data;
struct node_t *next;
};
struct linked_list_t {
struct node_t *head;
struct node_t *tail;
size_t len;
};
void enqueue(struct linked_list_t *list, uint32_t data)
{
struct node_t *node = malloc(sizeof(struct node_t));
node->data = data;
node->next = NULL;
list->len++;
if (list->len == 1)
{
list->head = list->tail = node;
return;
}
list->tail->next = node;
list->tail = node;
}
uint32_t dequeue(struct linked_list_t *list)
{
if (list->len == 0)
{
fprintf(stderr, "Cannot dequeue empty list");
exit(1);
}
struct node_t *aux = list->head;
uint32_t data = aux->data;
list->head = list->head->next;
list->len--;
free(aux);
return data;
}
uint32_t peek(struct linked_list_t *list)
{
if (list->len == 0)
{
fprintf(stderr, "Cannot peek empty list");
exit(1);
}
return list->head->data;
}
void list_free(struct linked_list_t *list)
{
struct node_t *prev = NULL;
struct node_t *aux = list->head;
while (aux != NULL)
{
prev = aux;
aux = aux->next;
if (prev) {
free(prev);
}
}
}
這裡可以看到，入隊和出隊時都沒有迭代，我們只是調整指針，所以這個實現在出隊時有更好的時間複雜度。
不過，有一個小警告，由於快取局部性，即使這種實現在最壞的情況下更快，但在大多數情況下可能不是這樣。
以上是佇列資料結構的詳細內容。更多資訊請關注PHP中文網其他相關文章！
