By choosing a subset of these operations, you can make the double-ended queue behave like a stack or like a queue. For instance, if you use only enq_front and deq_front you get a stack, and if you use only enq_front and deq_back you get a queue.
By now, the reader should be used to using header objects in order to obtain uniform reference semantics. We will therefore go directly to a version of the double-ended queue with a separate header file and implementation file.
#ifndef DQUEUE_H #define DQUEUE_H struct dqueue; typedef struct dqueue *dqueue; /* create an empty dqueue */ extern dqueue dq_create(void); /* insert an element at the front of the dqueue */ extern void dq_enq_front(dqueue q, void *element); /* insert an element at the back of the dqueue */ extern void dq_enq_back(dqueue q, void *element); /* delete an element from the front of the dqueue and return it */ extern void *dq_deq_front(dqueue q); /* delete an element from the back of the dqueue and return it */ extern void *dq_deq_back(dqueue q); /* return a true value if and only if the dqueue is empty */ extern int dq_empty(dqueue q); #endifThe implementation file
First, let us study an implementation without any particular tricks. Here is a possibility:#include "dqueue.h" #include "dlist.h" #include < stdlib.h> struct dqueue { dlist head; dlist tail; }; dqueue dq_create(void) { dqueue q = malloc(sizeof(struct dqueue)); q -> head = q -> tail = NULL; return q; } int dq_empty(dqueue q) { return q -> head == NULL; } void dq_enq_front(dqueue q, void *element) { if(dq_empty(q)) q -> head = q -> tail = dcons(element, NULL, NULL); else { q -> head -> prev = dcons(element, NULL, q -> head); q -> head -> prev -> next = q -> head; q -> head = q -> head -> prev; } } void dq_enq_back(dqueue q, void *element) { if(dq_empty(q)) q -> head = q -> tail = dcons(element, NULL, NULL); else { q -> tail -> next = dcons(element, q -> tail, NULL); q -> tail -> next -> prev = q -> tail; q -> tail = q -> tail -> next; } } void * dq_deq_front(dqueue q) { assert(!empty(q)); { dqueue temp = q -> head; void *element = temp -> element; q -> head = q -> head -> next; free(temp); if(q -> head == NULL) q -> tail = NULL; else q -> head -> prev = NULL; return element; } } void * dq_deq_back(dqueue q) { assert(!empty(q)); { dqueue temp = q -> tail; void *element = temp -> element; q -> tail = q -> tail -> prev; free(temp); if(q -> tail == NULL) q -> head = NULL; else q -> tail -> next = NULL; return element; } }Using two sentinels
In the first implementation, there are special cases both in the enqueue and dequeue operations concerning whether the queue is empty or not. We now study how we can improve the situation using two sentinels.The basic idea is that a queue will contain two additional dlist cells that are conceptually not part of the queue, one at the beginning and one at the end. The fields, head and tail will always point to these cells.
#include "dqueue.h" #include "dlist.h" #include < stdlib.h> struct dqueue { dlist head; dlist tail; }; dqueue dq_create(void) { dqueue q = malloc(sizeof(struct dqueue)); q -> head = dcons(NULL, NULL, NULL); q -> tail = dcons(NULL, NULL, NULL); q -> head -> next = q -> tail; q -> tail -> prev = q -> head; return q; } int dq_empty(dqueue q) { return q -> head -> next == q -> tail; } void dq_enq_front(dqueue q, void *element) { create_and_link(element, q -> head, q -> head -> next); } void dq_enq_back(dqueue q, void *element) { create_and_link(element, q -> tail -> prev, q -> tail); } void * dq_deq_front(dqueue q) { assert(!empty(q)); return unlink_and_free(q -> head -> next); } void * dq_deq_back(dqueue q) { assert(!empty(q)); return unlink_and_free(q -> tail -> prev); }Be sure to study and appreciate the simplicity of this implementation compared to the previous one. There are no special cases. The body of each enqueue function is now one line instead of eight. The body of each dequeue function is two lines instead of twelve.Using a single sentinel
There is a minor simplification that one can accomplish with respect to the previous implementation. It suffices to realize that in the first sentinel, only the next field is used, and in the second sentinel, only the prev field is used. Thus, it is possible to use half of a sentinel for the first, and the other half of the same for the second.Doing that makes the list into a circular doubly-linked list. Here is the implementation:
#include "dqueue.h" #include "dlist.h" #include < stdlib.h> struct dqueue { dlist sentinel; }; dqueue dq_create(void) { dqueue q = malloc(sizeof(struct dqueue)); q -> sentinel = dcons(NULL, NULL, NULL); q -> sentinel -> next = q -> sentinel -> prev = q -> sentinel; return q; } int dq_empty(dqueue q) { return q -> sentinel -> next == q -> sentinel; } void dq_enq_front(dqueue q, void *element) { create_and_link(element, q -> sentinel, q -> sentinel -> next); } void dq_enq_back(dqueue q, void *element) { create_and_link(element, q -> sentinel -> prev, q -> sentinel); } void * dq_deq_front(dqueue q) { assert(!empty(q)); return unlink_and_free(q -> sentinel -> next); } void * dq_deq_back(dqueue q) { assert(!empty(q)); return unlink_and_free(q -> sentinel -> prev); }No spectacular simplifications were accomplished, but a doubly linked list cell was saved, which probably does not matter very much.