Структуры данных Python3

В этой главе мы в основном объединяем изученные ранее знания, чтобы представить структуры данных Python.

Списки

В Python списки изменяемы, и это самая важная особенность, отличающая их от строк и кортежей. Одним предложением: списки можно изменять, а строки и кортежи — нет.

Ниже приведены методы списков в Python:

Метод Описание
list.append(x) Добавляет элемент в конец списка, что эквивалентно a[len(a):] = [x].
list.extend(L) Расширяет список, добавляя все элементы указанного списка, что эквивалентно a[len(a):] = L.
list.insert(i, x) Вставляет элемент в указанную позицию. Первый параметр — это индекс элемента, перед которым нужно вставить. Например, a.insert(0, x) вставляет в начало всего списка, а a.insert(len(a), x) эквивалентно a.append(x).
list.remove(x) Удаляет первый элемент в списке, значение которого равно x. Если такого элемента нет, возвращается ошибка.
list.pop([i]) Удаляет элемент в указанной позиции из списка и возвращает его. Если индекс не указан, a.pop() возвращает последний элемент. Элемент сразу удаляется из списка. (Квадратные скобки вокруг i в методе означают, что этот параметр необязателен, а не то, что нужно вводить пару квадратных скобок. Такую запись вы часто встретите в справочном руководстве по библиотеке Python.)
list.clear() Удаляет все элементы из списка, эквивалентно del a[:].
list.index(x) Возвращает индекс первого элемента в списке, значение которого равно x. Если подходящего элемента нет, возвращается ошибка.
list.count(x) Возвращает количество раз, которое x встречается в списке.
list.sort() Сортирует элементы в списке.
list.reverse() Обращает порядок элементов в списке.
list.copy() Возвращает поверхностную копию списка, эквивалентную a[:].

В следующем примере демонстрируется большинство методов списков:

Пример

>>> a = [66.25, 333, 333, 1, 1234.5]
>>> print(a.count(333), a.count(66.25), a.count('x'))
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.25, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.remove(333)
>>> a
[66.25, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.25]
>>> a.сортировка()
>>> a
[-1, 1, 66.25, 333, 333, 1234.5]

Примечание: такие методы, как insert, remove или sort, изменяющие списки, не возвращают значение.

Использование списков в качестве стеков

В Python можно использовать список для реализации функциональности стека. Стек — это структура данных, работающая по принципу «последним пришёл — первым вышел» (LIFO, Last-In-First-Out), то есть последний добавленный элемент удаляется первым. Списки предоставляют некоторые методы, которые делают их очень подходящими для операций со стеком, особенноappend()иpop()методы.

Используйте метод append() для добавления элемента на вершину стека, а метод pop() без индекса — для извлечения элемента с вершины стека.

Операции со стеком

  • Push: Добавить элемент на вершину стека.
  • Pop: Удалить и вернуть верхний элемент стека.
  • Peek/Top: Вернуть верхний элемент стека, не удаляя его.
  • IsEmpty: Проверить, пуст ли стек.
  • Size: Получить количество элементов в стеке.

Ниже приводится подробное объяснение того, как реализовать эти операции с помощью списков в Python:

1. Создать пустой стек

Пример

stack = []

2. Операция Push

Используйте метод append() для добавления элемента на вершину стека:

Пример

stack.append(1)
stack.append(2)
stack.append(3)
print(stack)  # Output: [1, 2, 3]

3. Операция Pop

Используйте метод pop() для удаления и возврата верхнего элемента стека:

Пример

top_element = stack.pop()
print(top_element)  # Вывод: 3
print(stack)        # Вывод: [1, 2]

4. Просмотр верхнего элемента стека (Peek/Top)

Прямой доступ к последнему элементу списка (без его удаления):

Пример

top_element = stack[-1]
print(top_element)  # Вывод: 2

5. Проверка на пустоту (IsEmpty)

Проверьте, пуст ли список:

Пример

is_empty = len(stack) == 0
print(is_empty)  # Вывод: False

6. Получение размера стека (Size)

Используйте функцию len(), чтобы получить количество элементов в стеке:

Пример

size = len(stack)
print(size)  # Вывод: 2

Пример

Ниже приведён полный пример, показывающий, как использовать приведённые выше операции для реализации простого стека:

Пример

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            raise IndexError("peek from empty stack")

    def is_empty(self):
        return len(self.stack) == 0

    def size(self):
        return len(self.stack)

# Пример использования
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print("Top element:", stack.peek())  # Вывод: Top element: 3
print("Stack size:", stack.size())    # Вывод: Stack size: 3

print("Popped element:", stack.pop())  # Вывод: Popped element: 3
print("Is the stack empty:", stack.is_empty())  # Вывод: Is the stack empty: False
print("Stack size:", stack.size())    # Вывод: Stack size: 2

В приведённом выше коде мы определили класс Stack, который инкапсулирует список как базовую структуру данных и реализует основные операции стека.

Вывод следующий:

栈顶元素: 3
栈大小: 3
弹出元素: 3
栈是否为空: False
栈大小: 2

Использование списков в качестве очередей

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

Очередь — это структура данных «первым пришёл — первым вышел» (FIFO, First-In-First-Out), то есть элемент, добавленный раньше всех, удаляется первым.

При использовании списка, если вы часто вставляете или удаляете элементы в начале списка, производительность будет страдать, потому что временная сложность этих операций — O(n). Чтобы решить эту проблему, Python предоставляет collections.deque — двустороннюю очередь, которая позволяет эффективно добавлять и удалять элементы с обоих концов.

Реализация очереди с помощью collections.deque

collections.deque является частью стандартной библиотеки Python и очень хорошо подходит для реализации очередей.

Ниже приведён пример реализации очереди с помощью deque:

Пример

from collections import deque

# Создать пустую очередь
queue = deque()

# Добавить элементы в хвост очереди
queue.append('a')
queue.append('b')
queue.append('c')

print("Состояние очереди:", queue)  # Вывод: Состояние очереди: deque(['a', 'b', 'c'])

# Удалить элемент из головы очереди
first_element = queue.popleft()
print("Удалённый элемент:", first_element)  # Вывод: Удалённый элемент: a
print("Состояние очереди:", queue)            # Вывод: Состояние очереди: deque(['b', 'c'])

# Просмотреть головной элемент (не удаляя его)
front_element = queue[0]
print("Головной элемент:", front_element)    # Вывод: Головной элемент: b

# Проверить, пуста ли очередь
is_empty = len(queue) == 0
print("Пуста ли очередь:", is_empty)     # Вывод: Пуста ли очередь: False

# Получить размер очереди
size = len(queue)
print("Размер очереди:", size)            # Вывод: Размер очереди: 2
```

Реализация очереди с помощью списков

Хотя deque более эффективен, если вы настаиваете на использовании списка для реализации очереди, вы всё ещё можете это сделать. Ниже приведён пример того, как использовать список для реализации очереди:

1. Создайте очередь

Пример

queue = []

2. Добавьте элементы в конец очереди

Используйте метод append() для добавления элементов в конец очереди:

Пример

queue.append('a')
queue.append('b')
queue.append('c')
print("Состояние очереди:", queue)  # Вывод: Состояние очереди: ['a', 'b', 'c']

3. Удалите элементы из начала очереди

Используйте метод pop(0) для удаления элементов из начала очереди:

Пример

first_element = queue.pop(0)
print("Удалённый элемент:", first_element)  # Вывод: Удалённый элемент: a
print("Состояние очереди:", queue)            # Вывод: Состояние очереди: ['b', 'c']

4. Просмотреть первый элемент очереди (без удаления)

Прямой доступ к первому элементу списка:

Пример

front_element = queue[0]
print("Первый элемент:", front_element)    # Вывод: Первый элемент: b

5. Проверить, пуста ли очередь

Проверьте, пуст ли список:

Пример

is_empty = len(queue) == 0
print("Пуста ли очередь:", is_empty)     # Вывод: Пуста ли очередь: False

6. Получить размер очереди

Используйте функцию len() для получения размера очереди:

Пример

size = len(queue)
print("Размер очереди:", size)            # Вывод: Размер очереди: 2

Пример (реализация очереди с помощью списков)

Пример


class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            raise IndexError("dequeue из пустой очереди")

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            raise IndexError("peek из пустой очереди")

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

# Пример использования
queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')

print("Передний элемент:", queue.peek())    # Вывод: Передний элемент: a
print("Размер очереди:", queue.size())    # Вывод: Размер очереди: 3

print("Удалённый элемент:", queue.dequeue())  # Вывод: Удалённый элемент: a
print("Очередь пуста:", queue.is_empty())  # Вывод: Очередь пуста: False
print("Размер очереди:", queue.size())    # Вывод: Размер очереди: 2

Хотя для реализации очереди можно использовать список, использование collections.deque более эффективно и лаконично. Он обеспечивает временную сложность O(1) для операций добавления и удаления, что делает его очень подходящим для структуры данных «очередь».

Списковые включения

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

Списковое включение состоит из выражения, за которым следует предложение for, затем ноль или более предложений for или if. Результатом является список, сгенерированный из выражения в контексте следующих предложений for и if. Если вы хотите, чтобы выражение создавало кортеж, необходимо использовать круглые скобки.

Здесь мы умножаем каждое значение в списке на три, чтобы получить новый список:

>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]

Теперь давайте поиграем с несколькими приёмами:

>>> [[x, x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]

Здесь мы поочерёдно вызываем метод у каждого элемента последовательности:

Пример

>>> freshfruit = [' banana', ' loganberry ', 'passion fruit ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']

Мы можем использовать условие if в качестве фильтра:

>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]

Ниже приведены некоторые демонстрации циклов и других приёмов:

>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

Списковые включения могут использовать сложные выражения или вложенные функции:

>>> [str(round(355/113, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

Вложенные списковые включения

Списки Python также могут быть вложенными.

В следующем примере показан список матрицы 3X4:

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]

В следующем примере список матрицы 3X4 преобразуется в список 4X3:

>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Приведённый выше пример также можно реализовать следующим способом:

>>> transposed = []
>>> for i in range(4):
...     transposed.append([row[i] for row in matrix])
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Другой метод реализации:

>>> transposed = []
>>> for i in range(4):
...     # следующие 3 строки реализуют вложенное списочное включение
...     transposed_row = []
...     for row in matrix:
...         transposed_row.append(row[i])
...     transposed.append(transposed_row)
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Оператор del

Оператор del может использоваться для удаления элемента из списка по индексу, а не по значению. Это отличается от использования pop(), который возвращает значение. Оператор del может использоваться для удаления среза из списка или для очистки всего списка (метод, который мы представили ранее, заключается в присваивании пустого списка этому срезу). Например:

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:]
>>> a
[]

Вы также можете использовать del для удаления переменных:

>>> del a

Кортежи и последовательности

Кортеж состоит из нескольких значений, разделённых запятыми, например:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Кортежи могут быть вложенными:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

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

Множества

Множество — это неупорядоченная коллекция уникальных элементов. Основные возможности включают проверку принадлежности и устранение дублирующихся элементов.

Множества можно создавать с помощью фигурных скобок ({}). Примечание: чтобы создать пустое множество, нужно использовать set(), а не {}; последний вариант создаёт пустой словарь — структуру данных, которую мы представим в следующем разделе.

Ниже приведён простой пример:

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # Удалить дубликаты
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # Проверить принадлежность
True
>>> 'crabgrass' in basket
False

>>> # Следующее демонстрирует операции над двумя множествами
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # Уникальные буквы в a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # Буквы в a, но не в b
{'r', 'd', 'b'}
>>> a | b                              # Буквы в a или b
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # Буквы, входящие и в a, и в b
{'a', 'c'}
>>> a ^ b                              # Буквы в a или b, но не в обоих
{'r', 'd', 'b', 'm', 'z', 'l'}

Множества также поддерживают включения:

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

Словари

Ещё один очень полезный встроенный тип данных в Python — словарь.

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

Лучший способ понять словарь — рассматривать его как неупорядоченную коллекцию пар ключ=>значение. В одном и том же словаре ключи должны быть различными.

Пара фигурных скобок создаёт пустой словарь: {}.

Это простой пример использования словаря:

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> list(tel.keys())
['irv', 'guido', 'jack']
>>> sorted(tel.keys())
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

Конструктор dict() создает словари непосредственно из списка пар ключ-значение. Если имеется фиксированный шаблон, списковые включения могут задавать конкретные пары ключ-значение:

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'jack': 4098, 'guido': 4127}

Кроме того, словарные включения можно использовать для создания словарей с произвольными выражениями ключей и значений:

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

Если ключи — простые строки, иногда удобнее задавать пары ключ-значение с помощью именованных аргументов:

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'jack': 4098, 'guido': 4127}

Приёмы циклического обхода

При циклическом обходе словаря можно одновременно получать ключи и соответствующие значения с помощью метода items():

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items():
...     print(k, v)
...
gallahad the pure
robin the brave

При переборе последовательности позицию индекса и соответствующее значение можно получить одновременно с помощью функции enumerate():

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print(i, v)
...
0 tic
1 tac
2 toe

Чтобы одновременно перебирать две или более последовательности, используйте zip() для их объединения:

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print('Что такое ваш {0}? Это {1}.'.format(q, a))
...
Как вас зовут? Это Ланселот.
Какова ваша цель? Это Святой Грааль.
Какой ваш любимый цвет? Это синий.

Чтобы перебрать последовательность в обратном порядке, сначала укажите последовательность, а затем вызовите функцию reversed():

>>> for i in reversed(range(1, 10, 2)):
...     print(i)
...
9
7
5
3
1

Чтобы перебрать последовательность по порядку, используйте функцию sorted(), которая возвращает отсортированную последовательность, не изменяя исходную:

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print(f)
...
яблоко
банан
апельсин
pear

Справочная документация

Другие расширения