2014:02:03:TP:C:Dequeue

Introduction

Dans cette TP nous allons mettre en pratique les techniques de structures de données génériques vues en cours (version listes) pour implémenter des Double Ended Queues appelées dequeue (prononcer deck.)

Le principe est simple: on généralise la notion de file en ajoutant la possibilité d'ajouter les éléments en tête (front) et en queue (back) et symétriquement de les prendre (défiler) des deux côtés.

Nous utiliserons une implémentation classique à base de listes doublement chaînées.

En-tête

Voici l'en-tête que vous devrez implémenter:

/* dequeue.h : generic double ended queue */
/* header */
 
#ifndef _DEQUEUE_H_
#define _DEQUEUE_H_
 
typedef struct sdequeue        *dequeue;
 
/*
 * Create an empty dequeue
 */
dequeue dequeue_create();
 
/*
 * dequeue_is_empty(dq) return true (not 0) if dq contains no elements
 */
int dequeue_is_empty(dequeue dq);
 
/*
 * dequeue_push_back(dq,cell) bind cell at the end of dq
 * dequeue_push_front(dq,cell) bind cell at the begining of dq
 */
void dequeue_push_back(dequeue dq, void *cell);
void dequeue_push_front(dequeue dq, void *cell);
 
/*
 * dequeue_back(dq) returns the last cell of the dequeue
 * dequeue_front(dq) returns the first cell of the dequeue
 * both functions return NULL if the dequeue is empty
 */
void* dequeue_back(dequeue dq);
void* dequeue_front(dequeue dq);
 
/*
 * dequeue_pop_back(dq) returns and removes the last cell of the dequeue
 * dequeue_pop_front(dq) returns and removes the first cell of the dequeue
 * both functions return NULL if the dequeue is empty
 */
void* dequeue_pop_back(dequeue dq);
void* dequeue_pop_front(dequeue dq);
 
/* Iterators */
 
/*
 * dequeue_iterator_front(dq) get a valid iterator starting from front
 * dequeue_iterator_back(dq) get a valid iterator starting from back
 * If the queue is empty the 2 previous operations return the corresponding
 * end: back for front and front for back.
 *
 * dequeue_end_front(dq) returns before front invalid iterator
 * dequeue_end_back(dq) returns after back invalid iterator
 *
 * dequeue_next(iterator) go forward, if possible
 * dequeue_prev(iterator) go backward, if possible
 * when reaching the respective ends, the 2 previous functions return the
 * corresponding end: back for next and front for prev.
 */
 
void *dequeue_iterator_front(dequeue dq);
void *dequeue_iterator_back(dequeue dq);
void *dequeue_end_front(dequeue dq);
void *dequeue_end_back(dequeue dq);
void *dequeue_next(void *iterator);
void *dequeue_prev(void *iterator);
 
#endif

La structure

Pour notre dequeue nous allons utiliser une boite englobant les deux pointeurs sur la tête et la queue, ainsi qu'une indication de taille.

On utilisera également deux sentinelles vides de chaque côté qui serviront de repère pour les itérateurs. On notera que ces sentinelles ne seront pas forcément de même nature que les cellules de la liste puisque celles-ci seront allouées et définies par l'utilisateur de notre structure.

Voici un point de départ pour l'implémentation de cette structure:

/* dequeue.h : generic double ended queue */
/* implementation */
 
#include <stdlib.h>
 
#include "dequeue.h"
 
struct scell {
  struct scell *next, *prev;
};
 
struct sdequeue {
  struct scell *front, *back;
  size_t        size;
};
 
/*
 * We use two sentinel (front and back) without content
 */
 
dequeue dequeue_create() {
  dequeue       dq;
 
  dq        = malloc(sizeof (struct sdequeue));
  dq->front = malloc(sizeof (struct scell));
  dq->back  = malloc(sizeof (struct scell));
 
  dq->front->next = dq->back;
  dq->front->prev = NULL;
  dq->back->next  = NULL;
  dq->back->prev  = dq->front;
  dq->size = 0;
 
  return dq;
}

C'est parti !

• Vous devez maintenant implémenter toutes les opérations décrites dans l'en-tête.

Pour tester votre code, voici un petit exemple simple de programme de tests.

Il n'est pas complet (pas d'itérateur) et ne teste pas tous les cas d'utilisation (notamment mélange entre opération front et back.)

/* Testing dequeue */
 
#include <assert.h>
#include <stdlib.h>
 
#include "dequeue.h"
 
struct data {
  struct data  *next, *prev;
  unsigned      key;
};
 
#define MAX 10
 
int main() {
  dequeue       dq;
  dq = dequeue_create();
 
  // Testing front push and access
  for (unsigned i = 0; i < MAX; ++i) {
    struct data        *cell;
    cell = malloc(sizeof (struct data));
    cell->key = i;
    dequeue_push_front(dq, cell);
    assert(cell == dequeue_front(dq));
  }
 
  // Testing front pop
  for (unsigned i = MAX-1; !dequeue_is_empty(dq); --i) {
    struct data        *cell;
    assert((cell = dequeue_pop_front(dq)));
    assert(i == cell->key);
    free(cell);
  }
  assert(dequeue_pop_front(dq) == NULL);
 
  // Testing back push and access
  for (unsigned i = 0; i < MAX; ++i) {
    struct data        *cell;
    cell = malloc(sizeof (struct data));
    cell->key = i;
    dequeue_push_back(dq, cell);
    assert(cell == dequeue_back(dq));
  }
 
  // Testing back pop
  for (unsigned i = MAX-1; !dequeue_is_empty(dq); --i) {
    struct data        *cell;
    assert((cell = dequeue_pop_back(dq)));
    assert(i == cell->key);
    free(cell);
  }
  assert(dequeue_pop_front(dq) == NULL);
 
  return 0;
}