Введение в структуры данных Python

Массив, Стек, Очередь, Связанный список

Предпосылка

Вы должны иметь базовые знания языка программирования Python.

Вся часть кода этой статьи доступна в моем репозитории git-hub.

Что такое структуры данных?

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

Структуры данных - это способ хранения и организации данных в вашей программе. с помощью различных DS мы можем эффективно хранить и систематизировать данные. Использование DS повысит эффективность нашей программы. Проще говоря, DS - это контейнер, который может хранить данные и выполнять с ними несколько операций (PUSH, POP, SEARCH… ETC).

Но не все структуры данных работают эффективно для каждой задачи, проблемы или программы. Некоторые DS работают эффективно для одних задач, а другие - нет. И для некоторых других задач другие DS работают отлично, а некоторые нет (для EX. Graph эффективно работает для поиска маршрута, но не для задачи операции Undo, где Stack работает отлично).

Вот почему мы должны знать все основные DS, чтобы вы могли понять различные проблемы и найти эффективное решение для этой проблемы.

Зачем использовать Python для понимания структур данных?

Python - это высокоуровневый интерпретируемый объектно-ориентированный язык сценариев. И Python очень легко понять и новичкам. Таким образом, используя python, вы можете очень легко понять концепции DS и то, как реализовать DS. И использование этого также очистит ваши основы Python. Так что в целом было бы полезно использовать python вместо любого другого языка для учебника DS.

Какие бывают типы структур данных?

В основном мы можем разделить DS на две основные части.

1. Линейные структуры данных.
2. Нелинейные структуры данных.

Линейные структуры данных

1. Массивы
2. Связанный список
3. Стек
4. Очередь

Нелинейные структуры данных

1. Дерево
2. Хеш-таблица
3. График

Линейные структуры данных

1. Массивы

Массивы - один из самых распространенных и наиболее часто используемых DS. В Array есть выделенный блок памяти, в котором последовательно хранятся элементы одних и тех же типов данных. Вы можете сохранить фиксированное количество элементов в этом блоке памяти.

Существует концепция ИНДЕКС, с помощью которой вы можете элементы. Обычно в каждом языке программирования индекс начинается с 0. Таким образом, вы можете получить доступ к любому элементу. из массива с помощью индекса (для EX, если вы хотите получить доступ к элементу массива, вы можете получить его как имя_массива [0]).

Массив - это самый простой и базовый тип DS, с помощью которого вы можете реализовать множество DS, таких как Stack, Queue или Linked Lists.

Основные операции, которые можно выполнять с массивом

1. Траверс - распечатать все элементы массива.
2. Вставить - вставить элемент в массив.
3. Удалить - удалить элемент из массива.
4. Обновить - обновить элемент в массиве.

Реализация массивов с использованием Python

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

Вы можете использовать List вместо Arrays или можете использовать ‘Array’, ‘N umpy’ для реализации массивов в Python .

Реализация одномерного массива с использованием списка

# Creating Single-dimensional Array using List
cars = ["Ford", "Volvo", "BMW"]
# Accessing Element of array using INDEX
x = cars[0]
# Updating Element of array
cars[0] = "Toyota"
# Getting Length of Array 
x = len(cars)
# Traversing Array
for x in cars:
  print(x)
# Inserting Element at end of Array
cars.append("Honda")
# Removing Element of array using Value
cars.remove("Volvo")

Для Numpy и Arrays нажмите на ссылки, указанные на них.

2. Стек

Stack DS чем-то похож на массивы, но при условии соблюдения правила LIFO (Last In First Out). Это означает, что элемент, который был вставлен в стопку последним, будет удален первым (для стопки книг или стопки посуды).

В стеке вставка называется PUSH, а удаление называется POP.

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

Основные операции, которые вы можете выполнять со стеком

1. Печать - распечатать все элементы стопки.
2. Нажать - вставить элемент в стопку.
3. Pop - удалить элемент из стопки.
4. Peek - возвращает элемент, находящийся на вершине стека.

Реализация стека с использованием Python

Вы можете реализовать стек в Python, используя списки и используя библиотеку python коллекций

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

# Implementation of Stack using List
class Stack:
    def __init__(self):
        self.stack = []
        
    def pop(self):
        if self.is_empty():
            return
        return self.stack.pop()
  
    def push(self,data):
        self.stack.append(data)
    
    def is_empty(self):
        if len(self.stack) == 0:
            return True
        return False
    
    def get_peek(self):
        return self.stack[-1]
    
    def print_stack(self):
        print_str = ''
        if self.is_empty() is False:
            for element in self.stack:
                    print_str += str(element) + '---'
            print(print_str)
        else:
            print('Stack is Empty')

Объяснение кода

• Здесь, прежде всего, мы создали класс стека, который будет иметь все различные методы, которые будут выполнять операции PUSH, POP, PEEK.
• __init_ Метод инициализирует переменную стека пустым списком.
• Теперь метод push примет data в качестве параметра, а затем добавит этот data к этому self.stack (stack variable of class).
• В методе is_empty он проверяет, пуст ли список или нет, и если он пуст, то if вернет True, иначе if вернет False.
• pop проверяет, пуст ли список или нет, и если он пуст, то if вернет None, иначе if удалит последний в списке элемент и вернет этот элемент.
• get_peek вернет последний элемент, вставленный в self.stack variable.
• Метод print_stack сначала проверяет, пуст ли стек или нет, и если он пуст, то он печатает Stack is Empty, иначе он пройдет через все элементы в стеке, добавит его к элементу print_str и распечатает после завершения цикла.

Использование модуля "Коллекции"

#Implementation of Stack using Collections
import collections
class Stack:
    
    def __init__(self):
        self.stack = collections.deque()
    
    def push(self,data):
        self.stack.append(data)
        
    def pop(self):
        if self.is_empty():
            return
        return self.stack.pop()
        
    def is_empty(self):
        if len(self.stack) == 0 :
            return True
        else:
            return False
    def get_peek(self):
        return self.stack[-1]
        
    def print_stack(self):
        print_str = ''
        if self.is_empty() is False:
            for element in self.stack:
                print_str += str(element)+'---'
            print(print_str)
        else:
            print('List is Empty')

Объяснение кода

• Сначала мы импортируем модуль коллекций, используя import collections.
• Затем мы создадим класс стека, который будет иметь все различные методы, которые будут выполнять операции PUSH, POP, PEEK, как указано выше.
• __init_ Метод инициализирует переменную стека с помощью collections.deque(), это инициализирует self.stack, чтобы очистить двустороннюю очередь.
• В остальном все методы в этом коде такие же, как и реализация списка стека, поэтому все будет понятно.

Чтобы узнать больше о модуле коллекций, нажмите здесь.

3. Очередь

Очередь - это линейный DS, похожий на массивы и стеки, но единственное и главное отличие очереди - это метод FIFO (первый пришел - первый ушел) для вставки и удаления элемента из очереди.

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

Это разные типы очередей

1. Простая очередь (это простая очередь, которая следует за FIFO.)
2. Приоритетная очередь (в этом типе очереди каждый элемент связан с определенным приоритетом, а затем обрабатывается в соответствии с их приоритетом.)
3. Очередь с двойным завершением (в этой очереди будет два конца очереди, и вы можете вставлять или удалять элементы с любой стороны концов, чтобы эта очередь не следовала за операцией FIFO.)
4. Циклическая очередь (в Циклической очереди последний элемент очереди указывает на первый элемент очереди.)

Количество основных операций, выполняемых в очереди -

1. Enque - вставка элементов в очередь.
2. Deque - удаление элементов из очереди.
3. Печать - печать всей очереди.

Как и стек, вы можете реализовать очередь, используя списки, а также модуль коллекций. Но здесь мы реализуем очередь только с помощью модуля коллекций.

# Implementation of Queue using Collections Module
import collections
class Queue():
    def __init__(self):
        self.queue = collections.deque()
        
    def enque(self,data):
        self.queue.appendleft(data)
    
    def deque(self):
        if self.is_empty():
            return
        return self.queue.pop()
    
    def is_empty(self):
        if len(self.queue) == 0:
            return True
        return False
    
    def print_queue(self):
        print_str = ''
        if self.is_empty():
            print('Queue is empty')
            return
        for element in self.queue:
            print_str = print_str + str(element) +"<---"
        print(print_str)

Объяснение кода

• Прежде всего, как и в случае со стеком, мы создадим класс очереди, который будет иметь все основные методы, которые будут реализовывать операции ENQUE и DEQUE.
• В методе __init__ мы инициализируем переменную self.queue как двояковую очередь с помощью модуля коллекций.
• Теперь в enquemethod он будет принимать data в качестве параметра, а затем добавить слева от self.queue, поэтому использование метода appendleft if добавит новые данные в начало очереди.
• is_empty проверит, пуста ли данная очередь или нет, и если она пуста, то он вернет True, иначе вернет False.
• В методе deque он будет проверять, пуста ли очередь или нет, используя метод is_empty, и если очередь пуста, то этот метод вернет None , в противном случае он вернет элемент с правой стороны очереди (это означает, что элемент, который вставлен первым) используя self.queue.pop()method.
• Метод print_queue проверит, пуста ли очередь, затем он напечатает “queue is empyt”, в противном случае он переберет все элементы в очереди и добавит их в переменную pritn_str, а печать будет после завершения цикла.

4. Связанный список

Связанный список также является линейным DS, но он немного отличается от других DS, таких как Stack, queue. Связанный список имеет специальную структуру, называемую узлом, которая имеет два поля данных и адрес следующего узла.

В части Data узла хранятся данные, а в части Next узла хранится адрес или указатель следующего узла.

Таким образом, в связанном списке все узлы содержат адрес или указатель на следующий узел связанного списка. Таким образом, нам не нужно выделять конкретный блок памяти для хранения данных, мы можем добавить новый узел без какого-либо конкретного выделения памяти перед созданием связанного списка.

Это различные типы связанных списков

1. Простой связанный список (это простой связанный список).
2. Двусвязный список (в этом типе связанного списка, который имеет указатель, один - это предыдущий указатель, а один - следующий указатель, предыдущий указатель хранит ссылку на предыдущий узел, а следующий указатель сохраняет ссылку на следующий узел.)
3. Круговой связанный список (в этом связанном списке последний узел содержит указатель первого узла.)

Основные операции со связанным списком

1. Вставить в начале
2. Вставить в конце
3. Вставить между связанным списком
4. Удалить
5. Печать связанного списка

# Class For Single Node Which Stores Data and the next Node
class Node:
    def __init__(self ,data=None, next=None):
        self.data = data
        self.next = next

Объяснение кода

• Здесь мы создали узел класса, который будет иметь параметры, переданные методу __init__, то есть data и next.
• self.data сохранит данные, а self.next сохранит указатель на следующий узел в связанном списке.

# Class That Implements LL
class LinkedList:
    def __init__(self):
        self.head=None
        
        
        
#   Printing Whole LL
    def print_ll(self):
        if self.head is None:
            print('Linked list is empty')
            return
        temp = self.head
        ll_str = ''
        while temp:
            ll_str += str(temp.data)+' --> ' if temp.next else str(temp.data)
            temp=temp.next
        print(ll_str)
        
        
        
#   For Getting Length of LL
    def get_length(self):
        if self.head is None:
            print("The Length is 0")
            return 0
        temp=self.head
        count = 0
        while temp:
            temp=temp.next
            count += 1
        return count
#   For Inserting Values At the begining of the LL
    def insert_at_begining(self,data):
        node = Node(data,self.head)
        self.head = node
        
        
        
#   For Inserting Values at the end of LL    
    def insert_at_end(self,data):
        if self.head is None:
            self.insert_at_begining(data)
            return
        temp = self.head
        
        while temp.next:
            temp=temp.next
        temp.next = Node(data,None)
        
        
                
#   For Inserting Value at given Index(starting from 0)
    def insert_at(self,index,data):
        if index<0  or index > self.get_length():
            raise Exception("Invalid Index")
        
        if self.head is None or index == 0:
            self.insert_at_begining(data)
            return
        temp = self.head
        count = 0
        while temp:
            
            if count == index - 1:
                nxt_node = temp.next
                temp.next = Node(data,nxt_node)
                break
            temp=temp.next
            count += 1
        
    
#     For Removing Values at given indext(Starting from 0)
    def remove_at(self,index):
        if index<0  or index > self.get_length():
            raise Exception("Invalid Index")
        
        if index == 0:
            self.head = self.head.next
            return
        temp = self.head
        count = 0
        while temp: 
            if count == index - 1:
                temp.next = temp.next.next
                break
            temp = temp.next
            count += 1

Объяснение кода

• Теперь в классе связанного списка мы напишем все методы, которые будут выполнять все операции со связанным списком.
• Сначала в методе __init__ мы инициализируем только одну переменную с именем self.head значением None (здесь self.head представляет собой заголовок связанного списка или начало связанного списка).
• Теперь мы поговорим о первом методе insert_at_begining, который имеет один параметр data. Этот метод добавит узел в начало связанного списка. Этот метод создаст переменную с именем node, которая создаст экземпляр Node с данными, равными данным параметра и next = self.head, но как self.head = None мы инициализируем self.head этой переменной узла, так что голова будет указывать на первый узел, или новый узел будет считаться головным узлом. .
• Теперь мы поговорим о insert_at_end, который также имеет один параметр с именем data, и этот метод будет проверять, является ли заголовок None , что означает, что LL пуст, поэтому метод будет добавлять новый узел в начале. И если LL не пуст, метод будет проходить через LL, перейдет к последнему узлу LL и добавит туда новый узел.
• Теперь третья операция вставки - вставка в любую позицию. Это будет сделано методом insert_at, который имеет два параметра data и index (начиная с 0). Сначала этот метод проверит, недействителен ли индекс. после этого он будет проходить через LL и остановится на узле, который имеет index =index-1, и после этого мы добавим к новому узлу между двумя узлами, изменив следующее значение этих узлов.

• get_length будет проходить через LL и длину печати в конце цикла, используя переменную count, которая почти такая же, как стек или очередь.
• print_ll также будет делать то же самое, что и для стека или очереди, поэтому этот метод не требует пояснений.
• Теперь последний и самый важный метод - это remove_at, у которого есть один параметр index. Этот метод удалит узел по данному индексу. Этот метод проверяет два условия: во-первых, правильно ли index, а во-вторых, если заданный index равен 0 (это означает, что вы хотите удалить голову). В противном случае этот метод будет выполнять цикл через LL и останавливаться на узле, который имеет index = index-1, а на узле он изменит значение следующей переменной на temp.next.next (это означает, что теперь он будет указывать на узел, который находится рядом с удаленным узлом) .

Заключение

Итак, в этой статье мы рассмотрели основы структур данных и вкладышей Структуры данных.

Во второй части мы рассмотрим нелинейные структуры данных, такие как деревья, хеш-карты, графики.

Надеюсь, вам понравилось читать и учиться.