Deque - newell-romario/DSA GitHub Wiki

A deque or double ended queue is a linear data structure where insertion and deletion is allowed to happen at both ends. Our deque implementation can be accessed by including the header file r2_deque.h.

Representation

A deque is represented by the structure below:

struct r2_deque{
        struct r2_dequenode  *front;/*Front of deque*/
        struct r2_dequenode  *rear;/*Rear of deque*/
        r2_cmp cmp;/*A comparison callback function*/
        r2_cpy cpy;/*A callback function to copy values*/
        r2_fd fd;/*A callback function that release memory*/
        r2_uint64 dsize; /*Number of elements in deque*/
};

The fields front, rear and dsize should not be modified or accessed.

Creation

struct r2_deque *deque = r2_create_deque(cmp, cpy, fd);

Destruction

r2_destroy_deque(deque);

Insertion

int first = 1; 
int last  = 5; 

if(r2_deque_insert_at_front(deque, &first))
     printf("\nSuccessfully inserted the first number.");


if(r2_deque_insert_at_back(deque, &last))
   printf("\nSuccessfully inserted the last number.");


int skip = 2; 
if(r2_deque_insert_at_front(deque, &skip))
     printf("\nI was moved to the front of line.");

Deletion

/*Removing the last element in the deque*/
if(r2_deque_delete_at_back(deque))
   printf("\nWe deleted the last element!"); 

/*Removing the first element in the deque*/
if(r2_deque_delete_at_front(deque))
  printf("\nWe deleted the first element!"); 

Rear

/*Getting last element in deque.*/
struct r2_dequenode *rear = r2_deque_rear(deque); 
int *rear = rear->data; 
printf("\nRear: %ld", *rear);

Front

/*Getting first element in deque.*/
struct r2_dequenode *front = r2_deque_front(deque); 
int *front = front->data; 
printf("\nFront: %ld", *front);