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 general look at how these data structures compare to each other:

Stack:

One end only → LIFO

Queue:

Insert at tail
Remove at head → FIFO

Deque:

Insert/remove at both ends

---

What Is a Queue?

A queue follows a simple rule:

First In, First Out (FIFO)

Example:

enqueue A
enqueue B
enqueue C

dequeue → A
dequeue → B
dequeue → C

---

Queue API

Typical queue operations:

enqueue()
dequeue()
front()
is_empty()

---

What Is a Deque?

Deque = Double Ended Queue

You can:

push_front()
push_back()
pop_front()
pop_back()

---

Why Our Previous Linked Lists Are Perfect For These

Let’s think in terms of requirements.

Queue Needs

Add at tail → O(1)
Remove at head → O(1)

That means we need:

head pointer
tail pointer

Ring a bell? That is our tailed link list implementation, which can be found here.

---

Deque Needs

Remove at tail → O(1)

To do that efficiently, we need:

prev pointer

Our previous doubly linked list implementation fulfills this need! That can be found here.

---

Implementation Strategy

Just like with our stack implementation, we are simply writing wrappers that use our pre-existing tailed linked list and doubly linked list code:

queue.h

#ifndef QUEUE_H
#define QUEUE_H

#include "linked_list.h"
#include <stddef.h>

struct Queue {
        struct LinkedList list; 
        size_t size;            
};


void queue_init(struct Queue* q);
void queue_destroy(struct Queue* q); 


int queue_enqueue(struct Queue* q, struct Node* n); 
int queue_dequeue(struct Queue* q);                 
struct Node* queue_peek(const struct Queue* q);     

int queue_is_empty(const struct Queue* q);
size_t queue_size(const struct Queue* q);

#endif

queue.c

#include "queue.h"

void queue_init(struct Queue* q) {
        if (!q) return;
        list_init(&q->list);
        q->size = 0;
}

void queue_destroy(struct Queue* q) {
        if (!q) return;
        free_list(&q->list); /* frees nodes, leaves list usable */
        q->size = 0;
}

/*
 * enqueue = push_back
 */
int queue_enqueue(struct Queue* q, struct Node* n) {
        if (!q || !n) return -1;
        push_back(&q->list, n);
        q->size++;
        return 0;
}

/*
 * dequeue = pop_front
 */
int queue_dequeue(struct Queue* q) {
        if (!q) return -1;
        if (q->list.head == NULL) return -1;

        pop_front(&q->list);
        q->size--;
        return 0;
}

struct Node* queue_peek(const struct Queue* q) {
        if (!q) return NULL;
        /* front() takes non-const in your header, so cast is easiest */
        return front((struct LinkedList*) &q->list);
}

int queue_is_empty(const struct Queue* q) {
        return (!q || q->list.head == NULL);
}

size_t queue_size(const struct Queue* q) {
        return q ? q->size : 0;
}

deque.h

#ifndef DEQUE_H
#define DEQUE_H

#include <stddef.h>
#include "linked_list.h"

struct Deque {
        struct LinkedList list; 
        size_t size;            
};


void deque_init(struct Deque* d);
void deque_destroy(struct Deque* d); 

int deque_push_front(struct Deque* d, struct Node* n); 
int deque_push_back(struct Deque* d, struct Node* n); 

int deque_pop_front(struct Deque* d); 
int deque_pop_back(struct Deque* d);  

struct Node* deque_peek_front(const struct Deque* d);
struct Node* deque_peek_back(const struct Deque* d);

int deque_is_empty(const struct Deque* d);
size_t deque_size(const struct Deque* d);

#endif

deque.c

#include "deque.h"

void deque_init(struct Deque* d) {
        if (!d) return;
        list_init(&d->list);
        d->size = 0;
}

void deque_destroy(struct Deque* d) {
        if (!d) return;
        free_list(&d->list); 
        d->size = 0;
}

int deque_push_front(struct Deque* d, struct Node* n) {
        if (!d || !n) return -1;
        push_front(&d->list, n);
        d->size++;
        return 0;
}

int deque_push_back(struct Deque* d, struct Node* n) {
        if (!d || !n) return -1;
        push_back(&d->list, n);
        d->size++;
        return 0;
}

int deque_pop_front(struct Deque* d) {
        if (!d) return -1;
        if (d->list.head == NULL) return -1;

        pop_front(&d->list);
        d->size--;
        return 0;
}

int deque_pop_back(struct Deque* d) {
        if (!d) return -1;
        if (d->list.tail == NULL) return -1;

        pop_back(&d->list);
        d->size--;
        return 0;
}

struct Node* deque_peek_front(const struct Deque* d) {
        if (!d) return NULL;
        return front((struct LinkedList*) &d->list);
}

struct Node* deque_peek_back(const struct Deque* d) {
        if (!d) return NULL;
        return back((struct LinkedList*) &d->list);
}

int deque_is_empty(const struct Deque* d) {
        return (!d || d->list.head == NULL);
}

size_t deque_size(const struct Deque* d) {
        return d ? d->size : 0;
}

---

The Big Takeaway

A stack, queue, and deque are not fundamentally different storage systems when compared to their corresponding linked list implementations.

For my next post, I promise I will NOT be hitting you with another rehash of old code 🙂