A double-ended queue, pronounced deque in short is a LIFO queue where entries can be pushed and popped at both the ends of the queue, apart from push and pop an additional peek method is also discussed which fetches the value at either ends without removing it. In this article, one such queue is implemented using the C language.
Environment
The code is executed in the following environment,
- Operating System - Windows 11
- Compiler - GCC 8.1.0
- Editor - Visual Studio code
The include files are determined based on the usage of certain functions, assert.h for assert(), errno.h for various error numbers, stdlib.h for malloc() and free().
#include <stdio.h> #include <errno.h> #include <assert.h> #include <stdlib.h>
Since the deque has two ends, there has to be two pointers to keep track of both the ends. These pointers are named front and back, and they point to one of the entry structures. Each entry structure contains an integer data, and pointers to next and previous entries. A double pointer approach is used to ease the addition and removal of entries from both ends ie., one end operates on the next, and the other on prev pointers respectively. These data structures are defined as follows,
typedef struct deque_entry { int data; struct deque_entry *next; struct deque_entry *prev; } deque_entry; typedef struct deque { deque_entry *front; deque_entry *back; } deque;
First step is initializing the deque data structure, without any elements in the queue, the pointers can only point to NULL. The initial state (or the empty state) is when both the ends point to NULL. An extra method dq_init_with_entry() is coded to initialize the deque with an entry. For example, when an entry is added at the empty state, both ends will point to the same entry. These methods are shown below,
void dq_init(deque *dq) { dq->front = NULL; dq->back = NULL; } void dq_init_with_entry(deque *dq, deque_entry *entry) { dq->front = entry; dq->back = entry; } int dq_is_empty(deque *dq) { return dq->front == NULL && dq->back == NULL; }
The next helper method is to allocate and initialize an entry data structure. The method takes care of error handling and return proper error to the caller.
deque_entry* dq_alloc_entry(int data) { deque_entry *entry = malloc(sizeof(*entry)); if (entry != NULL) { entry->data = data; entry->next = NULL; entry->prev = NULL; } return entry; }
One of the common operations is to push an entry at one of the ends. Once the entry is added, depending on the end, either front or back will point to the newly added entry and the entry is linked to the existing list. The next and prev pointers are adjusted to add the entry to the list. These method also allocates the entry data structure and handles cases where the deque is empty.
int dq_push_front(deque *dq, int data) { deque_entry *entry = dq_alloc_entry(data); if (entry == NULL) { return ENOMEM; } /* empty deque, front and back will point to the new element */ if (dq_is_empty(dq)) { dq_init_with_entry(dq, entry); return 0; } entry->next = dq->front; dq->front->prev = entry; dq->front = entry; return 0; } int dq_push_back(deque *dq, int data) { deque_entry *entry = dq_alloc_entry(data); if (entry == NULL) { return ENOMEM; } if (dq_is_empty(dq)) { dq_init_with_entry(dq, entry); return 0; } entry->prev = dq->back; dq->back->next = entry; dq->back = entry; return 0; }
The next operation is to pop an entry from either ends. To pop an entry, the list must contain at least one entry in it ie., deque is not empty. The code for pop also takes care of last entry removal, in such cases the deque moves to the initial state where front and back both point to NULL. Finally, the entry is freed and the data is returned to the caller.
int dq_pop_front(deque *dq, int *data) { deque_entry *entry; if (dq_is_empty(dq)) { return EINVAL; } entry = dq->front; dq->front = entry->next; /* last element popped */ if (dq->front == NULL) { dq_init(dq); } else { dq->front->prev = NULL; } *data = entry->data; free(entry); return 0; } int dq_pop_back(deque *dq, int *data) { deque_entry *entry; if (dq_is_empty(dq)) { return EINVAL; } entry = dq->back; dq->back = entry->prev; /* last element popped */ if (dq->back == NULL) { dq_init(dq); } else { dq->back->next = NULL; } *data = entry->data; free(entry); return 0; }
Peeking an entry is the simplest of all methods, returning the value from either the front or back. Of course, it needs to check whether the deque is empty before attempting to read the data.
int dq_peek_front(deque *dq, int *data) { if (dq_is_empty(dq)) { return EINVAL; } *data = dq->front->data; return 0; } int dq_peek_back(deque *dq, int *data) { if (dq_is_empty(dq)) { return EINVAL; } *data = dq->back->data; return 0; }
Cleaning up a deque involves freeing all the allocated entries for the list. Cleanup is achieved by popping elements from one end of the queue until the queue is empty, the logic of the pop takes care of the memory free for the entry.
void dq_cleanup(deque *dq) { int data; while (!dq_is_empty(dq)) { dq_pop_front(dq, &data); } }
The entries in the list can be printed to verify the order of the list and to look for any broken links during addition or removal of elements. Two methods are coded for printing the list, one in forward order and another in reverse order.
void dq_dump_reverse(deque *dq) { deque_entry *entry = dq->back; printf("List contents (dir = reverse): "); while (entry) { printf("(%d) -> ", entry->data); entry = entry->prev; } printf("\n\n"); } void dq_dump(deque *dq) { deque_entry *entry = dq->front; printf("List contents (dir = forward): "); while (entry) { printf("(%d) -> ", entry->data); entry = entry->next; } printf("\n"); dq_dump_reverse(dq); }
Test driven development is used to verify the behavior of the deque. The code is run with asserts for catching un-expected behavior under various conditions. The unit testing code is self-explanatory.
/* Unit test code */ void run_empty_test(deque *dq) { assert(dq_is_empty(dq) == 1); } void run_non_empty_test(deque *dq) { assert(dq_is_empty(dq) == 0); } void run_peek_front_test(deque *dq, int data) { int peeked_data; dq_peek_front(dq, &peeked_data); assert(data == peeked_data); } void run_peek_back_test(deque *dq, int data) { int peeked_data; dq_peek_back(dq, &peeked_data); assert(data == peeked_data); } void run_push_front_test(deque *dq, int data) { dq_push_front(dq, data); run_non_empty_test(dq); run_peek_front_test(dq, data); dq_dump(dq); } void run_push_back_test(deque *dq, int data) { dq_push_back(dq, data); run_non_empty_test(dq); run_peek_back_test(dq, data); dq_dump(dq); } void run_pop_front_test(deque *dq, int data) { int popped_data; run_peek_front_test(dq, data); dq_pop_front(dq, &popped_data); assert(data == popped_data); dq_dump(dq); } void run_pop_back_test(deque *dq, int data) { int popped_data; run_peek_back_test(dq, data); dq_pop_back(dq, &popped_data); assert(data == popped_data); dq_dump(dq); } void run_pop_empty_test(deque *dq) { int ret; int data; ret = dq_pop_back(dq, &data); assert(ret == EINVAL); ret = dq_pop_front(dq, &data); assert(ret == EINVAL); } void run_peek_empty_test(deque *dq) { int ret; int data; ret = dq_peek_back(dq, &data); assert(ret == EINVAL); ret = dq_peek_front(dq, &data); assert(ret == EINVAL); } void run_tests(deque *dq) { printf("Tests start.\n"); dq_init(dq); run_empty_test(dq); /* push data to front of the queue, peek and verify */ run_push_front_test(dq, 10); run_push_front_test(dq, 20); run_push_front_test(dq, 30); run_push_front_test(dq, 40); run_push_back_test(dq, 50); run_push_back_test(dq, 60); run_push_back_test(dq, 70); run_push_back_test(dq, 80); run_pop_front_test(dq, 40); run_pop_front_test(dq, 30); run_pop_front_test(dq, 20); run_pop_back_test(dq, 80); run_pop_back_test(dq, 70); run_pop_back_test(dq, 60); run_pop_back_test(dq, 50); run_pop_back_test(dq, 10); run_empty_test(dq); run_push_back_test(dq, 100); run_push_front_test(dq, 110); dq_cleanup(dq); run_empty_test(dq); run_pop_empty_test(dq); run_peek_empty_test(dq); printf("Tests end.\n"); } int main() { deque dq; run_tests(&dq); return 0; }
The tests include printing the lists, a sample run of tests would produce the following output.
> .\a.exe Tests start. List contents (dir = forward): (10) -> List contents (dir = reverse): (10) -> List contents (dir = forward): (20) -> (10) -> List contents (dir = reverse): (10) -> (20) -> List contents (dir = forward): (30) -> (20) -> (10) -> List contents (dir = reverse): (10) -> (20) -> (30) -> List contents (dir = forward): (40) -> (30) -> (20) -> (10) -> List contents (dir = reverse): (10) -> (20) -> (30) -> (40) -> List contents (dir = forward): (40) -> (30) -> (20) -> (10) -> (50) -> List contents (dir = reverse): (50) -> (10) -> (20) -> (30) -> (40) -> List contents (dir = forward): (40) -> (30) -> (20) -> (10) -> (50) -> (60) -> List contents (dir = reverse): (60) -> (50) -> (10) -> (20) -> (30) -> (40) -> List contents (dir = forward): (40) -> (30) -> (20) -> (10) -> (50) -> (60) -> (70) -> List contents (dir = reverse): (70) -> (60) -> (50) -> (10) -> (20) -> (30) -> (40) -> List contents (dir = forward): (40) -> (30) -> (20) -> (10) -> (50) -> (60) -> (70) -> (80) -> List contents (dir = reverse): (80) -> (70) -> (60) -> (50) -> (10) -> (20) -> (30) -> (40) -> List contents (dir = forward): (30) -> (20) -> (10) -> (50) -> (60) -> (70) -> (80) -> List contents (dir = reverse): (80) -> (70) -> (60) -> (50) -> (10) -> (20) -> (30) -> List contents (dir = forward): (20) -> (10) -> (50) -> (60) -> (70) -> (80) -> List contents (dir = reverse): (80) -> (70) -> (60) -> (50) -> (10) -> (20) -> List contents (dir = forward): (10) -> (50) -> (60) -> (70) -> (80) -> List contents (dir = reverse): (80) -> (70) -> (60) -> (50) -> (10) -> List contents (dir = forward): (10) -> (50) -> (60) -> (70) -> List contents (dir = reverse): (70) -> (60) -> (50) -> (10) -> List contents (dir = forward): (10) -> (50) -> (60) -> List contents (dir = reverse): (60) -> (50) -> (10) -> List contents (dir = forward): (10) -> (50) -> List contents (dir = reverse): (50) -> (10) -> List contents (dir = forward): (10) -> List contents (dir = reverse): (10) -> List contents (dir = forward): List contents (dir = reverse): List contents (dir = forward): (100) -> List contents (dir = reverse): (100) -> List contents (dir = forward): (110) -> (100) -> List contents (dir = reverse): (100) -> (110) -> Tests end.
Thanks for reading. Please leave comments/suggestions if any.
Comments
Post a Comment