Структура данных типа дек

Структура данных типа дек (C, Очередь, Список, Стек)Мы с Вами рассмотрели уже довольно много структур данных, но я и не думал на этом останавливаться, так что в данной статье предлагаю рассмотреть еще одну структуру, название которой дек.

Определение

Дек (от англ. deque — double ended queue; двусвязная очередь, очередь с двумя концами) — линейная структура (последовательность), в которой операции включения и исключения элементов могут выполняться как с одного, так и с другого конца последовательности.

Дек — симбиоз стека и очереди, то есть дисциплинами обслуживания являются одновременно LIFO и FIFO.

Допустимые операции

  1. Инициализация
  2. Включение элемента в начало / конец дека
  3. Исключение элемента из начала / конца дека
  4. Проверка: дек пуст / не пуст
  5. Удаление дека

Реализация дека

Обычно для реализации дека используют двусвязный линейный список, то есть на основе готовых функций списка создают новые для дека. Иными словами, для реализации нам придется написать несколько оберток, как мы это делали при реализации стека на ОЛС.

Файл "Deck_List_Two.h"

/****************************************/
/*		Дек на двусвязном списке		*/
/****************************************/
#ifndef _DECK_LIST_TWO_H_
#define _DECK_LIST_TWO_H_
#include "List_Two.h"
/*Описание исключительных ситуаций*/
const int deckOk = listTwoOk;
const int deckNoMem = listTwoNoMem;
const int deckEmpty = listTwoEmpty;
/**********************************/
/*Переменная ошибок*/
extern int listTwoError;
/*Базовый тип дека*/
typedef listTwoBaseType deckBaseType;
/*Описание типа дек*/
typedef ListTwo Deck;
/*Функции работы с деком*/
void initDeck(Deck *D);							// Инициализация дека
void putDeckLeft(Deck *D, deckBaseType E);		// Включение в начало дека
void getDeckLeft(Deck *D, deckBaseType *E);		// Исключение из начала дека
void putDeckRight(Deck *D, deckBaseType E);		// Включение в конец дека
void getDeckRight(Deck *D, deckBaseType *E);	// Исключение из конца дека
void doneDeck(Deck *D);							// Удаление дека
int isDeckEmpty(Deck *D);						// Предикат: пуст ли дек
/************************/
#endif

Файл "Deck_List_Two.c"

/****************************************/
/*		Дек на двусвязном списке		*/
/****************************************/
#include "Deck_List_Two.h"
/*Инициализация дека*/
void initDeck(Deck *D) {
initListTwo(D);
listTwoError = deckOk;
}
/*Включение в начало дека*/
void putDeckLeft(Deck *D, deckBaseType E) {
beginPtrListTwo(D);
postPut(D, E);
}
/*Исключение из начала дека*/
void getDeckLeft(Deck *D, deckBaseType *E) {
beginPtrListTwo(D);
postGet(D, E);
}
/*Включение в конец дека*/
void putDeckRight(Deck *D, deckBaseType E) {
endPtrListTwo(D);
predPut(D, E);
}
/*Исключение из конца дека*/
void getDeckRight(Deck *D, deckBaseType *E) {
endPtrListTwo(D);
predGet(D, E);
}
/*Удаление дека*/
void doneDeck(Deck *D) {
doneListTwo(D);
}
/*Предикат: пуст ли дек*/
int isDeckEmpty(Deck *D) {
return isEmptyListTwo(D);
}

Дек готов! Вот мы и пополнили запас знаний еще одной структурой данных. Также напоминаю, если у Вас возникли вопросы, пишите их в комментариях. А на этом все. Удачи!

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

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