Блок задач

3. Структуры данных

Темы
Сложность 4

Задача «Динамическая очередь»

Реализовать очередь на базе кругового динамического массива (с указателями или индексами на голову и хвост очереди).

Операции вставки и удаления должны иметь сложность O(1) в том случае, если не вызывается функция realloc.

typedef struct tQueue {
    /* ... */
} Queue;

typedef void *Pointer;

/* Создать пустую очередь */
void queue_create(Queue *pqueue);

/* Уничтожить очередь, освободив выделенную память */
void queue_destroy(Queue *pqueue);

/* Поместить значение value в конец очереди */
void queue_enqueue(Queue *pqueue, Pointer value);

/* Возвращает количество элементов в очереди (0, если очередь пуста) */
size_t queue_size(Queue *pqueue);

/* Исключить и вернуть значение первого элемента очереди. 
   Если очередь пуста, возвращает 0 */
Pointer queue_dequeue(Queue *pqueue);

/*
 * Возвращает значение первого элемента, не удаляя его из очереди.
 * Если очередь пуста, возвращает 0 
 */
Pointer queue_peek(Queue *pqueue);

/* 
 * Настраивает параметры очереди. 
 * initial_size: начальный размер очереди, при первом выделении памяти
 *               (по умолч.: 50)
 * increment: на сколько элементов расширять очередь при последующих
 *            выделениях памяти
 */
void queue_tune(Queue *pqueue, size_t initial_size, size_t increment);

Тесты с помощью assert.