{"id":86,"date":"2026-02-12T07:30:00","date_gmt":"2026-02-12T07:30:00","guid":{"rendered":"https:\/\/mattbick.dev\/?p=86"},"modified":"2026-02-10T19:44:37","modified_gmt":"2026-02-10T19:44:37","slug":"data-structure-every-day-day-5-queue-and-deque","status":"publish","type":"post","link":"https:\/\/mattbick.dev\/?p=86","title":{"rendered":"Data Structure Every Day, Day 5: Queue and Deque"},"content":{"rendered":"\n

In my last post<\/a>, I showed how a simple Stack data structure could be implemented by simply reusing our already existing tailless linked list code. In today’s entry, we are are going to knock out TWO data structures following the same approach. The queue <\/strong>and the deque<\/strong>.<\/p>\n\n\n\n

\n\n\n\n

Little Refresher:<\/h2>\n\n\n\n

For those unfamiliar, here is a general look at how these data structures compare to each other:<\/p>\n\n\n\n

Stack:<\/strong><\/p>\n\n\n\n

One end only \u2192 LIFO<\/code><\/pre>\n\n\n\n
Queue:<\/strong><\/p>\n\n\n\n
Insert at tail\nRemove at head \u2192 FIFO<\/code><\/pre>\n\n\n\n
Deque<\/strong>:<\/p>\n\n\n\n
Insert\/remove at both ends<\/code><\/pre>\n\n\n\n
\n\n\n\n
What Is a Queue?<\/h1>\n\n\n\n
A queue follows a simple rule:<\/p>\n\n\n\n
First In, First Out (FIFO)<\/strong><\/p>\n\n\n\n
Example:<\/p>\n\n\n\n
enqueue A\nenqueue B\nenqueue C\n\ndequeue \u2192 A\ndequeue \u2192 B\ndequeue \u2192 C<\/code><\/pre>\n\n\n\n
\n\n\n\n
Queue API<\/h2>\n\n\n\n
Typical queue operations:<\/p>\n\n\n\n
enqueue()\ndequeue()\nfront()\nis_empty()<\/code><\/pre>\n\n\n\n
\n\n\n\n
What Is a Deque?<\/h1>\n\n\n\n
Deque = Double Ended Queue<\/strong><\/p>\n\n\n\n
You can:<\/p>\n\n\n\n
push_front()\npush_back()\npop_front()\npop_back()<\/code><\/pre>\n\n\n\n
\n\n\n\n
Why Our Previous Linked Lists Are Perfect For These<\/h1>\n\n\n\n
Let\u2019s think in terms of requirements.<\/p>\n\n\n\n
Queue Needs<\/h2>\n\n\n\n
Add at tail \u2192 O(1)\nRemove at head \u2192 O(1)<\/code><\/pre>\n\n\n\n
That means we need:<\/p>\n\n\n\n
head pointer\ntail pointer<\/code><\/pre>\n\n\n\n
Ring a bell? That is our tailed link list implementation, which can be found here<\/a>. <\/p>\n\n\n\n
\n\n\n\n
Deque Needs<\/h2>\n\n\n\n
Remove at tail \u2192 O(1)<\/code><\/pre>\n\n\n\n
To do that efficiently, we need:<\/p>\n\n\n\n
prev pointer<\/code><\/pre>\n\n\n\n
Our previous doubly linked list implementation fulfills this need! That can be found here<\/a>. <\/p>\n\n\n\n
\n\n\n\n
Implementation Strategy<\/h1>\n\n\n\n
Just like with our stack implementation, we are simply writing wrappers that use our pre-existing tailed linked list and doubly linked list code:<\/p>\n\n\n\n
queue.h<\/strong><\/p>\n\n\n\n
#ifndef QUEUE_H\n#define QUEUE_H\n\n#include "linked_list.h"\n#include <stddef.h>\n\nstruct Queue {\n        struct LinkedList list; \n        size_t size;            \n};\n\n\nvoid queue_init(struct Queue* q);\nvoid queue_destroy(struct Queue* q); \n\n\nint queue_enqueue(struct Queue* q, struct Node* n); \nint queue_dequeue(struct Queue* q);                 \nstruct Node* queue_peek(const struct Queue* q);     \n\nint queue_is_empty(const struct Queue* q);\nsize_t queue_size(const struct Queue* q);\n\n#endif<\/code><\/pre>\n\n\n\n
queue.c<\/strong><\/p>\n\n\n\n
#include "queue.h"\n\nvoid queue_init(struct Queue* q) {\n        if (!q) return;\n        list_init(&q->list);\n        q->size = 0;\n}\n\nvoid queue_destroy(struct Queue* q) {\n        if (!q) return;\n        free_list(&q->list); \/* frees nodes, leaves list usable *\/\n        q->size = 0;\n}\n\n\/*\n * enqueue = push_back\n *\/\nint queue_enqueue(struct Queue* q, struct Node* n) {\n        if (!q || !n) return -1;\n        push_back(&q->list, n);\n        q->size++;\n        return 0;\n}\n\n\/*\n * dequeue = pop_front\n *\/\nint queue_dequeue(struct Queue* q) {\n        if (!q) return -1;\n        if (q->list.head == NULL) return -1;\n\n        pop_front(&q->list);\n        q->size--;\n        return 0;\n}\n\nstruct Node* queue_peek(const struct Queue* q) {\n        if (!q) return NULL;\n        \/* front() takes non-const in your header, so cast is easiest *\/\n        return front((struct LinkedList*) &q->list);\n}\n\nint queue_is_empty(const struct Queue* q) {\n        return (!q || q->list.head == NULL);\n}\n\nsize_t queue_size(const struct Queue* q) {\n        return q ? q->size : 0;\n}<\/code><\/pre>\n\n\n\n
deque.h<\/strong><\/p>\n\n\n\n
#ifndef DEQUE_H\n#define DEQUE_H\n\n#include <stddef.h>\n#include "linked_list.h"\n\nstruct Deque {\n        struct LinkedList list; \n        size_t size;            \n};\n\n\nvoid deque_init(struct Deque* d);\nvoid deque_destroy(struct Deque* d); \n\nint deque_push_front(struct Deque* d, struct Node* n); \nint deque_push_back(struct Deque* d, struct Node* n); \n\nint deque_pop_front(struct Deque* d); \nint deque_pop_back(struct Deque* d);  \n\nstruct Node* deque_peek_front(const struct Deque* d);\nstruct Node* deque_peek_back(const struct Deque* d);\n\nint deque_is_empty(const struct Deque* d);\nsize_t deque_size(const struct Deque* d);\n\n#endif<\/code><\/pre>\n\n\n\n
deque.c<\/strong><\/p>\n\n\n\n
#include "deque.h"\n\nvoid deque_init(struct Deque* d) {\n        if (!d) return;\n        list_init(&d->list);\n        d->size = 0;\n}\n\nvoid deque_destroy(struct Deque* d) {\n        if (!d) return;\n        free_list(&d->list); \n        d->size = 0;\n}\n\nint deque_push_front(struct Deque* d, struct Node* n) {\n        if (!d || !n) return -1;\n        push_front(&d->list, n);\n        d->size++;\n        return 0;\n}\n\nint deque_push_back(struct Deque* d, struct Node* n) {\n        if (!d || !n) return -1;\n        push_back(&d->list, n);\n        d->size++;\n        return 0;\n}\n\nint deque_pop_front(struct Deque* d) {\n        if (!d) return -1;\n        if (d->list.head == NULL) return -1;\n\n        pop_front(&d->list);\n        d->size--;\n        return 0;\n}\n\nint deque_pop_back(struct Deque* d) {\n        if (!d) return -1;\n        if (d->list.tail == NULL) return -1;\n\n        pop_back(&d->list);\n        d->size--;\n        return 0;\n}\n\nstruct Node* deque_peek_front(const struct Deque* d) {\n        if (!d) return NULL;\n        return front((struct LinkedList*) &d->list);\n}\n\nstruct Node* deque_peek_back(const struct Deque* d) {\n        if (!d) return NULL;\n        return back((struct LinkedList*) &d->list);\n}\n\nint deque_is_empty(const struct Deque* d) {\n        return (!d || d->list.head == NULL);\n}\n\nsize_t deque_size(const struct Deque* d) {\n        return d ? d->size : 0;\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
The Big Takeaway<\/h1>\n\n\n\n
A stack, queue, and deque are not fundamentally different storage systems when compared to their corresponding linked list implementations. <\/p>\n\n\n\n
For my next post, I promise I will NOT be hitting you with another rehash of old code \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"
In my last post, I showed how a simple Stack data structure could be implemented by simply reusing our already existing tailless linked list code. In today’s entry, we are are going to knock out TWO data structures following the same approach. The queue and the deque. Little Refresher: For those unfamiliar, here is a […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-86","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/86","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=86"}],"version-history":[{"count":2,"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/86\/revisions"}],"predecessor-version":[{"id":88,"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/86\/revisions\/88"}],"wp:attachment":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=86"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=86"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=86"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}