Skip to content

Instantly share code, notes, and snippets.

@Wollw
Created April 6, 2012 08:53
Show Gist options
  • Save Wollw/2318276 to your computer and use it in GitHub Desktop.
Save Wollw/2318276 to your computer and use it in GitHub Desktop.
Deque in C
#include <stdlib.h>
#include <assert.h>
#include "deque.h"
struct node_struct {
struct node_struct *next;
struct node_struct *prev;
deque_val_type val;
};
struct deque_struct {
struct node_struct *head;
struct node_struct *tail;
};
deque_type * deque_alloc() {
deque_type *d = malloc(sizeof(deque_type));
if (d != NULL)
d->head = d->tail = NULL;
return d;
}
void deque_free(deque_type *d) {
free(d);
}
bool deque_is_empty(deque_type *d) {
return d->head == NULL;
}
void deque_push_front(deque_type *d, deque_val_type v) {
struct node_struct *n = malloc(sizeof(struct node_struct));
assert(n != NULL);
n->val = v;
n->next = d->head;
n->prev = NULL;
if (d->tail == NULL) {
d->head = d->tail = n;
} else {
d->head->prev = n;
d->head = n;
}
}
void deque_push_back(deque_type *d, deque_val_type v) {
struct node_struct *n = malloc(sizeof(struct node_struct));
assert(n != NULL);
n->val = v;
n->prev = d->tail;
n->next = NULL;
if (d->head == NULL) {
d->head = d->tail = n;
} else {
d->tail->next = n;
d->tail = n;
}
}
deque_val_type deque_pop_front(deque_type *d) {
deque_val_type v = d->head->val;
struct node_struct *n = d->head;
if (d->head == d->tail)
d->head = d->tail = NULL;
else
d->head = n->next;
free(n);
return v;
}
deque_val_type deque_pop_back(deque_type *d) {
deque_val_type v = d->tail->val;
struct node_struct *n = d->tail;
if (d->head == d->tail)
d->head = d->tail = NULL;
else
d->tail = n->prev;
free(n);
return v;
}
deque_val_type deque_peek_front(deque_type *d) {
return d->head->val;
}
deque_val_type deque_peek_back(deque_type *d) {
return d->tail->val;
}
/* An implementation of a Double Ended Queue.
* Pushes, peeks, and pops from both ends can be done and
* an allocate and free function is provided to instantiate a
* deque. As the implementation of the deque struct is in the
* source file "deque.c" it is required that the deque_alloc function
* be used to create a new deque providing a form of encapsulation.
*/
#ifndef DEQUE_H
#define DEQUE_H
#include <stdbool.h>
/* deque_type is a deque object that the deque_foo functions
* act upon. New deque_type objects can be created with deque_alloc.
*/
typedef struct deque_struct deque_type;
/* This deque_val_type is the type of all values stored in the deque.
* Change this to the type you want to store in your deque.
*/
typedef int deque_val_type;
/* Instantiates a new deque_type.
* Returns a pointer to a new deque_type with memory allocated by malloc,
* returns NULL if it fails.
*/
deque_type * deque_alloc();
/* Frees a deque_type pointed to by *d */
void deque_free(deque_type *d);
/* Returns true if there are no values in the deque, false otherwise. */
bool deque_is_empty(deque_type *d);
/* Adds a new value to the front/back of the deque_type *d */
void deque_push_front(deque_type *d, deque_val_type v);
void deque_push_back(deque_type *d, deque_val_type v);
/* Removes and returns the front/back value of the deque *d */
deque_val_type deque_pop_front(deque_type *d);
deque_val_type deque_pop_back(deque_type *d);
/* Returns the front/back value of the deque *d */
deque_val_type deque_peek_front(deque_type *d);
deque_val_type deque_peek_back(deque_type *d);
#endif
#include <stdio.h>
#include <assert.h>
#include "deque.h"
int main() {
deque_type *d = deque_alloc();
assert(d != NULL);
for (int i = 1; i <= 256; i+=i) {
deque_push_back(d, i);
}
while (deque_is_empty(d) != true) {
printf("%d\n", deque_pop_front(d));
}
deque_free(d);
return 0;
}
@asmamaw
Copy link

asmamaw commented Jan 1, 2018

we can move the struct declaration to the header file so that more flexible.
thank you anyways

@NeraSnow
Copy link

I think your code will result in memory leak.

@traguill
Copy link

traguill commented Apr 8, 2018

If any of these functions is called when the deque is empty it will result in error:
deque_val_type deque_peek_front(deque_type *d) {
return d->head->val;
}
deque_val_type deque_peek_back(deque_type *d) {
return d->tail->val;
}

Check first if head or tail is not NULL to avoid it.

deque_val_type deque_peek_front(deque_type *d) {
return d->head ? d->head->val : NULL;
}
deque_val_type deque_peek_back(deque_type *d) {
return d->tail ? d->tail->val : NULL;
}

@bryan-lunt
Copy link

Can I use this code?
How is this licensed?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment