Самостоятельная работа по дисциплине " Структуры данных и алгоритмы" на тему " Дек, реализация при помощи списков и операции над ними"


Download 158.17 Kb.
bet2/3
Sana23.03.2023
Hajmi158.17 Kb.
#1288911
TuriСамостоятельная работа
1   2   3
Bog'liq
075-19 Шукруллаев А.Ш СР

1. ОСНОВНАЯ ЧАСТЬ

    1. Теоретический материал



Описание структуры данных "дек" и его основных операций
Дек (от англ. deque - double-ended queue, двусторонняя очередь) - это абстрактный тип данных, который подобен очереди, но в отличие от нее позволяет добавлять и удалять элементы не только с одного, а с двух концов структуры. Дек может использоваться как стек, очередь или промежуточная структура данных в алгоритмах обхода деревьев.
Основные операции, которые можно выполнять над деком, включают:

  1. Добавление элемента в начало дека (push_front) - добавляет элемент в начало дека.

  2. Добавление элемента в конец дека (push_back) - добавляет элемент в конец дека.

  3. Удаление элемента из начала дека (pop_front) - удаляет элемент из начала дека.

  4. Удаление элемента из конца дека (pop_back) - удаляет элемент из конца дека.

  5. Получение элемента из начала дека (front) - возвращает элемент, находящийся в начале дека.

  6. Получение элемента из конца дека (back) - возвращает элемент, находящийся в конце дека.

  7. Проверка наличия элементов в деке (empty) - возвращает true, если дек пуст, и false в противном случае.

  8. Получение размера дека (size) - возвращает количество элементов в деке.

Дек является очень гибкой и мощной структурой данных, которая может быть использована во многих алгоритмах и программных приложениях. Операции над деком могут быть реализованы различными способами, в том числе при помощи списков, массивов или других структур данных.
Реализация дека при помощи списка
Реализация дека при помощи списка может быть достаточно простой и эффективной. Для этого мы можем использовать встроенную структуру данных Python - список.
Для добавления элемента в начало дека мы можем использовать метод insert() списка, а для добавления элемента в конец дека - метод append(). Аналогично, для удаления элемента из начала дека мы можем использовать метод pop() с параметром 0, а для удаления элемента из конца дека - метод pop() без параметров. Наконец, для получения элемента из начала дека мы можем использовать индекс 0, а для получения элемента из конца дека - индекс -1.

В этом примере мы создали класс Deque, который содержит методы для добавления элемента в начало и конец дека, удаления элемента из начала и конца дека, проверки на пустоту дека, получения размера дека, получения элемента из начала и конца дека.

В данном примере мы создали объект класса Deque, добавили в начало дека элементы 1 и 2, а в конец дека элемент 3. Затем мы получили первый и последний элементы дека при помощи методов get_front() и get_rear(). Далее мы удалили первый элемент дека и снова получили первый элемент.


Download 158.17 Kb.

Do'stlaringiz bilan baham:
1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling