Теоретическая часть



страница1/4
Дата12.08.2022
Размер1,04 Mb.
#188273
  1   2   3   4
Связанные:
kursovaya


Теоретическая часть.
Дек (от англ. deq - double ended queue, т.е. очередь с двумя концами), представляет собой структуру данных, в которой можно добавлять и удалять элементы с двух сторон.
Задачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо реже, чем задачи, реализуемые на структуре стека или очереди. Как правило, вся организация дека выполняется программистом без каких-либо специальных средств системной поддержки.
Примером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.
Реализация дека в программе.
В программе для реализации дека создаётся абстрактный тип данных Deque, который содержит размер дека, указатель на первый и последний элементы дека. Элемент состоит из значения, указателя на следующий и предыдущий элементы. Изначально хвост, голова и размер дека равны нулю.
При добавлении элементы слева, если дек не имеет элементов, то:

  1. динамически выделяется память на новый элемент.

  2. поля следующего и предыдущего элемента равны нулю.

  3. значение элемента становится равным заданному

  4. голова дека указывает на новый элемент

  5. размер дека увеличивается на еденицу

При добавлении элементы слева, если дек имеет элементы, то:

  1. динамически выделяется память на новый элемент.

  2. поле следующего элемента равно голове, а предыдущего элемента равно нулю.

  3. значение элемента становится равным заданному

  4. указатель головы на предыдущий элемент равен новому элементу.

  5. голова дека указывает на новый элемент

  6. размер дека увеличивается на единицу

Операции добавления элементов справа аналогичны вышеприведённым.
При проверке дека на пустоту, проверяется не равен ли нулю размер дека.
При удалении элементов слева, проверяем дек на пустоту. Если голова равна хвосту, то голову дека приравниваем к нулю и уменьшаем его размер. Если голова не равна хвосту, то объявляем новый указатель на элемент, присваиваем ему значение головы. Присваиваем голове значение поля некст указателя и удаляем указатель, уменьшаем размер дека.
Операции удаления элементов справа аналогичны вышеприведённым.


Поделитесь с Вашими друзьями:
  1   2   3   4




База данных защищена авторским правом ©psihdocs.ru 2022
обратиться к администрации

    Главная страница