Очередь на односвязном списке

Сегодня я предлагаю Вам вспомнить о том, что такое очередь. Не ту очередь, что в магазине, а структуру данных :). Об очередях в блоге уже есть две статьи: "Очередь на массиве и ее реализация на языке Си" и "Очередь с приоритетами". Для полной, так сказать, коллекции не хватает очереди на списке, которой мы сейчас с Вами и займемся.

Мы будем поступать таким же способом, как и тогда, когда реализовывали стек на списке, а именно, в заголовочном файле очереди подключим модуль со списком. Затем, имея все функции списка, напишем обертки для очереди.

Реализация очереди

Перед началом, хочу заметить, что реализация очереди будет иметь небольшое отличие от той же реализации стека на списке. Дело в том, что добавлять новый элемент нужно в конец очереди, а исключать — элемент, стоящий в начале. Если вспомнить, то в стеке мы включение и исключение элемента производили с одной стороны (с начала).

Теперь, когда все нюансы уточнены, можем смело браться за реализацию.

Файл "Queue_List.h"

/****************************************/
/*			Очередь на списке			*/
/****************************************/
#ifndef _QUEUE_LIST_H_
#define _QUEUE_LIST_H_
#include "List_One.h"
/*Описание исключительных ситуаций*/
const int queueListOk = listOneOK;
const int queueListEmpty = listOneEmpty;
const int queueListNoMem = listOneNoMem;
/**********************************/
/*Переменная ошибок*/
extern int listOneError;
/*Базовый тип очереди на списке*/
typedef listOneBaseType QueueListBaseType;
/*Тип очереди на списке*/
typedef ListOne QueueList;
/*Функции работы со очередью*/
void initQueueList(QueueList *S);						// Инициализация очереди
void putQueueList(QueueList *S, QueueListBaseType E);	// Включение в очередь
void getQueueList(QueueList *S, QueueListBaseType *E);	// Исключение из очереди
void doneQueueList(QueueList *L);						// Удаление очереди
int isEmptyQueueList(QueueList *S);						// Предикат: пуста ли очередь
/**************************/
#endif

Файл "Queue_List.c"

/****************************************/
/*			Очередь на списке			*/
/****************************************/
#include "Queue_List.h"
/*Инициализация очереди*/
void initQueueList(QueueList *S) {
initListOne(S);
listOneError = queueListOk;
}
/*Включение в очередь*/
void putQueueList(QueueList *S, QueueListBaseType E) {
endPtrListOne(S);
putListOne(S, E);
}
/*Исключение из очереди*/
void getQueueList(QueueList *S, QueueListBaseType *E) {
beginPtrListOne(S);
getListOne(S, E);
}
/*Удаление очереди*/
void doneQueueList(QueueList *L) {
doneListOne(L);
}
/*Предикат: пуста ли очередь*/
int isEmptyQueueList(QueueList *S) {
return isEmptyListOne(S);
}

Вот и все. Не так уж и сложно было. Не так ли? :). Также напоминаю, если Вам что-то не понятно и/или возникли вопросы, Вы можете задать их в комментариях под статьей. Удачи!

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *