Самостоятельная работа по дисциплине " Структуры данных и алгоритмы" на тему " Дек, реализация при помощи списков и операции над ними"
Download 158.17 Kb.
|
075-19 Шукруллаев А.Ш СР
- Bu sahifa navigatsiya:
- Реализация дека при помощи списка
1. ОСНОВНАЯ ЧАСТЬ
Теоретический материал Описание структуры данных "дек" и его основных операций Дек (от англ. deque - double-ended queue, двусторонняя очередь) - это абстрактный тип данных, который подобен очереди, но в отличие от нее позволяет добавлять и удалять элементы не только с одного, а с двух концов структуры. Дек может использоваться как стек, очередь или промежуточная структура данных в алгоритмах обхода деревьев. Основные операции, которые можно выполнять над деком, включают: Добавление элемента в начало дека (push_front) - добавляет элемент в начало дека. Добавление элемента в конец дека (push_back) - добавляет элемент в конец дека. Удаление элемента из начала дека (pop_front) - удаляет элемент из начала дека. Удаление элемента из конца дека (pop_back) - удаляет элемент из конца дека. Получение элемента из начала дека (front) - возвращает элемент, находящийся в начале дека. Получение элемента из конца дека (back) - возвращает элемент, находящийся в конце дека. Проверка наличия элементов в деке (empty) - возвращает true, если дек пуст, и false в противном случае. Получение размера дека (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: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling