Массив, Стек, Очередь, Связанный список
Предпосылка
Вы должны иметь базовые знания языка программирования 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. Массивы
Массивы - один из самых распространенных и наиболее часто используемых DS. В Array есть выделенный блок памяти, в котором последовательно хранятся элементы одних и тех же типов данных. Вы можете сохранить фиксированное количество элементов в этом блоке памяти.
Существует концепция ИНДЕКС, с помощью которой вы можете элементы. Обычно в каждом языке программирования индекс начинается с 0. Таким образом, вы можете получить доступ к любому элементу. из массива с помощью индекса (для EX, если вы хотите получить доступ к элементу массива, вы можете получить его как имя_массива [0]).
Массив - это самый простой и базовый тип DS, с помощью которого вы можете реализовать множество DS, таких как Stack, Queue или Linked Lists.
Основные операции, которые можно выполнять с массивом
- Траверс - распечатать все элементы массива.
- Вставить - вставить элемент в массив.
- Удалить - удалить элемент из массива.
- Обновить - обновить элемент в массиве.
Реализация массивов с использованием 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.
Одно из основных и известных применений стека - это операция отмены в любом программном обеспечении. В котором последнее состояние этого программного обеспечения помещается в верхнюю часть стека, и когда мы отменим, это состояние будет сначала выскакивать из стека и отображаться для нас.
Основные операции, которые вы можете выполнять со стеком
- Печать - распечатать все элементы стопки.
- Нажать - вставить элемент в стопку.
- Pop - удалить элемент из стопки.
- 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 работает точно так же, как и реальная очередь. В реальной жизни очередь, первый человек, который запускает очередь, будет первым, кто выйдет из очереди.
Это разные типы очередей
- Простая очередь (это простая очередь, которая следует за FIFO.)
- Приоритетная очередь (в этом типе очереди каждый элемент связан с определенным приоритетом, а затем обрабатывается в соответствии с их приоритетом.)
- Очередь с двойным завершением (в этой очереди будет два конца очереди, и вы можете вставлять или удалять элементы с любой стороны концов, чтобы эта очередь не следовала за операцией FIFO.)
- Циклическая очередь (в Циклической очереди последний элемент очереди указывает на первый элемент очереди.)
Количество основных операций, выполняемых в очереди -
- Enque - вставка элементов в очередь.
- Deque - удаление элементов из очереди.
- Печать - печать всей очереди.
Как и стек, вы можете реализовать очередь, используя списки, а также модуль коллекций. Но здесь мы реализуем очередь только с помощью модуля коллекций.
# 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
как двояковую очередь с помощью модуля коллекций. - Теперь в
enque
method он будет принимать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 узла хранится адрес или указатель следующего узла.
Таким образом, в связанном списке все узлы содержат адрес или указатель на следующий узел связанного списка. Таким образом, нам не нужно выделять конкретный блок памяти для хранения данных, мы можем добавить новый узел без какого-либо конкретного выделения памяти перед созданием связанного списка.
Это различные типы связанных списков
- Простой связанный список (это простой связанный список).
- Двусвязный список (в этом типе связанного списка, который имеет указатель, один - это предыдущий указатель, а один - следующий указатель, предыдущий указатель хранит ссылку на предыдущий узел, а следующий указатель сохраняет ссылку на следующий узел.)
- Круговой связанный список (в этом связанном списке последний узел содержит указатель первого узла.)
Основные операции со связанным списком
- Вставить в начале
- Вставить в конце
- Вставить между связанным списком
- Удалить
- Печать связанного списка
# 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
(это означает, что теперь он будет указывать на узел, который находится рядом с удаленным узлом) .
Заключение
Итак, в этой статье мы рассмотрели основы структур данных и вкладышей Структуры данных.
Во второй части мы рассмотрим нелинейные структуры данных, такие как деревья, хеш-карты, графики.
Надеюсь, вам понравилось читать и учиться.