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

· stack() создаёт новый пустой стек. Параметры не нужны, возвращает пустой стек.

· push(item) добавляет новый элемент на вершину стека. В качестве параметра выступает элемент; функция ничего не возвращает.

· pop() удаляет верхний элемент из стека. Параметры не требуются, функция возвращает элемент. Стек изменяется.

· peek() возвращает верхний элемент стека, но не удаляет его. Параметры не требуются, стек не модифицируется.

· isEmpty() проверяет стек на пустоту. Параметры не требуются, возвращает булево значение.

· size() возвращает количество элементов в стеке. Параметры не требуются, тип результата – целое число

Пример реализации стека:

class Stack:

def __init__(self) :

self.items=[]

def isEmpty(self) :

return self.items=[]

def push(self,item) :

self.items.append(item)

def pop(self) :

return self.items.pop()

def peek(self) :

return self.items[len(self.items)-1]

def size(self) :

return len(self.items)

from python.basic.stack import Stack

s=Stack

print(s.isEmpty

s.push(4)

s.push(‘dog’)

print(s.speek())

s.push(True)

print(s.size())

print(s.isEmpty())

print(s.pop())

print(s.pop())

print(s.size())

Множества

Множество – структура данных из различных элементов, где порядок элементов не определён. Элементы можно добавлять и удалять, перебирать. Можно выполнять операции над множествами (объединение, пересечение, разность). Можно проверять принадлежность элемента множеству.

Элементами множества могут быть объекты с неизменяемыми типами данных: числа, строки, кортежи (неизменяемые списки). Значения с изменяемым типом не могут быть элементами множества – список (но можно сделать кортеж) или другое множество. Это связано с особенностями представления множества в памяти компьютера.

Множество задается перечислением элементов в фигурных скобках. Например:

A={1,2,3}

Функция set() создает пустое множество. Функция set с параметрами в виде списка, строки или кортежа вернет множество, составленное из элементов списка, строки, кортежа. Например:

A = set('один')

print(A)

выведет {'д', 'и', 'н', 'о'}.

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

A = set('абракадабра') # A={‘a’, ‘б’, ‘д’, ‘к’, ‘р’}

B = set('бардак') # В={‘a’, ‘б’, ‘д’, ‘к’, ‘р’}

print(A==B)

выдаст значение True.

Примеры присвоения значений:

a=set() # a – пусто

b = {‘б’, ‘e’, ‘р’}

c= set('хан') # с={‘х’, ‘а’, ‘н’}

d={2*i for i in range(5)} # d={0, 2, 4, 6, 8}

e=set([‘бер’, ‘один’, ‘один’, ‘one’, ‘one’, ‘ein’]) # е={‘бер’, ‘один’, ‘one’, ‘ein’}

Число элементов определяет функция len(a). Например:

print(len(set(‘четыре’))) # выведет число 5

Перебор вех элементов множества можно осуществить при помощи цикла for

f={1,3,4,7}

for san in f : print(san) # напечатает 7 1 4 3

Принадлежность элемента можно проверить с помощью операции in .

print(3 in {1,3,4,7}) # напечатает True

Новый элемент добавляет метод add.

a={1,3,4,7}

a.add(6) # a= {1,3,4,6,7}

Метод pop удаляет из множества один случайный элемент, возвращая его значение. При пустом множестве генерируется исключение KeyError

Функция list из множества формирует список.

Операции с множествами:

len(s) – число элементов в множестве

x in s – принадлежность x s

s.isdisjoint(s1) – истина в случае пустого пересечения множеств

s==s1 – истина в случае совпадения множеств

s.issubset(s1) – s подмножество s1

s.issuperset(s1) – s1 подмножество s

s.union(s1,s2…) – объединение множеств

s.intersection(s1,s2,…) – пересечение s с остальными множествами

s.difference(s1,s2…) – вычитание из s подмножеств

s.simmetric_difference(s1) – исключающее или

s.copy(s1) – копирование.

Операции изменения множества:

s.update(s1,s2,…) – добавляет элементы в множество

s.intersection_update(s1,s2,…) – пересечение в множестве оставляет

s.difference_update(s1,s2,…) – вычитает из множества

s.simmetric_difference_update(s1,s2,…) – оставляет элементы, встречающиеся только в одном множестве

s.add(b) – добавляет элемент

s.remove(b) – удаляет элемент. При удалении несуществующего элемента формируется исключение KeyError.

s.discard(b) – удаляет элемент

s.pop() – удаляет случайный элемент

s.clear() – очищает множество.

Пример: Удалить все повторяющиеся элементы из списка.

a=[7,9,9,4,2,6,5,9,4] # a - множество

s=set(arr) # преобразует список во множство s=[2,4,5,7,9]

arr=list(s) # преобразует множество в список без повторений значений