Какво представляват структурите на стек данни в Python?

Структурите на данни представляват колекция от стойности на данни, връзките между тях и функциите или операциите, които могат да бъдат приложени към данните. Сега има много налични структури от данни. Но днес фокусът ни ще бъде върху структурите на стека данни. Ще обсъждам следните теми:

• Защо структури от данни?
• Видове структури от данни
• Какво представлява структурата на стека?
• Създаване на структура на данните за стека
• Натиснете елементи в стека
• Поп елементи от стека
• Приложения на структурата от данни на стека

Защо структури от данни?

За да отговорите на това, ще трябва да мислите на голямо ниво. Помислете как Google Maps ви показва най-добрия маршрут само за части от секундите, как ви връща резултата от търсенето за микросекунди. Той не се занимава само със 100 уебсайта, той се занимава с повече от милиард сайтове и въпреки това показва резултатите ви толкова бързо.

Е, въпреки че използваният алгоритъм играе решаваща роля, структурата на данните или използваният контейнер е основата на този алгоритъм. Във всяко приложение организирането и съхраняването на данни по начин или в структура, която е най-подходяща за тяхното използване, е от ключово значение за ефективен достъп и обработка на данни.

Видове структури от данни

Има някои стандартни структури от данни, които могат да се използват за ефективна работа с данни. Можем дори да ги персонализираме или да създадем изцяло нови, за да отговарят на нашето приложение.

Какво представлява структурата на стека?

Помислете за някои реални примери:

• Пратка в товар
• Чинии на поднос
• Купчина монети
• Чекмеджета
• Шунтиране на влакове в железопътен двор

Всички тези примери следват a Last-In-First-Out стратегия. Помислете за плочи на тава. Когато искате да вземете чиния, вие сте принудени да вземете чиния отгоре, докато когато плочите се държат на тавата, те трябва да бъдат в обратен ред. По-горе примери, които следват Last-In-First-Out (LIFO) принцип са известни като Стек .

Освен допълнителните операции, мога да кажа, че основните операции, които са възможни в стека, са:

1. Натиснете или поставете елемент в горната част на стека
2. Поп или премахнете елемент от горната част на стека

Създаване на структура на данните за стека

class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1

• max_size е максималният брой елементи, които се очакват в стека.
• Елементите на стека се съхраняват в списъка на python.
• Top показва най-горния индекс на стека, който първоначално се приема -1 за отбелязване на празен стек.

Първоначалното състояние на стека може да се види на фигурата, където max_size = 5

Натиснете елемента в стека

Сега, ако искате да въведете или натиснете елемент в стека, трябва да го запомните

• Най-отгоре ще сочи индекса, към който ще бъде вмъкнат елементът.
• И че нито един елемент няма да бъде вмъкнат, когато стекът е пълен, т.е.когато max_size = top.

И така, какъв трябва да бъде алгоритъмът ??

# връща максималния размер на стека def get_max_size (self): return self .__ max_size # връща bool стойност независимо дали стекът е пълен или не, True ако е пълен и False в противен случай def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes елемент в горната част на стека def push (self, data): if (self.is_full ()): print ('стекът вече е пълен') else: self .__ top = self .__ top + int (1 ) self .__ елементи [self .__ top] = данни # Можете да използвате __str __ () по-долу, за да отпечатате елементите на DS обекта, докато отстранявате грешки def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg ​​= 'Stack data (Top to Bottom):' + msg return msg

Сега, когато изпълните следното:

сливане сортиране c ++ код

stack1 = стек (4)

# Натиснете всички необходими елементи.

stack1.push („A“)

stack1.push („B“)

stack1.push („C“)

stack1.push („E“)

печат (stack1.is_full ())

печат (стек1)

Изход:

стекът вече е пълен
Вярно
Данни за стека (отгоре надолу): D C B A

какво прави форматът в python

Поп елементи от стека

Сега, когато сте вмъкнали елементите в стека, искате да ги извадите, така че трябва да се погрижите за следното:

• Стекът не е празен, т.е.горе! = -1
• Когато изтриете данните, горната част трябва да сочи към предишния връх на стека.

И така, какъв ще бъде алгоритъмът ??

#returns bool стойност дали стекът е празен или не, True ако е празен и False в противен случай def is_empty (self): return self .__ top == - 1 #returns изскачаща стойност def pop (self): if (self.is_empty ()): print ('нищо за изскачане, вече празно') else: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 връща a #display всички елементи на стека отгоре надолу def display (self): за i в обхват (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()

Сега, като се има предвид създадения по-рано стек, опитайте се да пуснете елементи

печат (stack1.pop ())

печат (stack1.pop ())

печат (стек1)

печат (stack1.pop ())

печат (stack1.pop ())

печат (stack1.pop ())

Изход:

д

° С

Данни за стека (отгоре надолу): B A

Б.

ДА СЕ

нищо за пукане, вече празно

Приложения на структурата от данни на стека

• Пример 1:

Стек се използва за внедряване на алгоритъм за съвпадение на скоби за оценка на аритметичен израз, а също и при изпълнението на извиквания на методи.

Отговорът на който е 5.

• Пример 2:

Клипборд в Windows използва два стека за изпълнение на операции за отмяна-повторение (ctrl + z, ctrl + y). Бихте работили върху редактори на думи на Windows като MS-Word, Notepad и др. Ето един текст, написан в MS-Word. Наблюдавайте как текстът се променя при щракване на Ctrl-Z и Ctrl-Y.

Ето код, който симулира операция за отмяна-повторение. Прегледайте кода и наблюдавайте как стекът се използва в тази реализация.

#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): print ('Стека е пълен !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('стекът е празен! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' стекът е празен ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Можете да използвате __str __ () за отпечатване на елементите на DS обект при отстраняване на грешки def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg ​​=' Данни на стека (От горе до долу): '+ msg връщане на ms g # Функция за внедряване на операция за премахване или backspace def remove (): глобален клипборд, undo_stack data = клипборд [лен (клипборд) -1] клипборд # функция за изпълнение на операция за отмяна def undo (): глобален клипборд, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Няма данни за отмяна') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', clipboard) # функция за изпълнение на операция redo, def redo (): глобален клипборд, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Няма данни да се преработи ') else: data = redo_stack.pop () if (данните не са в клипборда): print (' Няма данни за повторно ') redo_stack.push (data) else: clipboard.remove (data) undo_stack.push ( данни) print ('Redo:', clipboard) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (clipboard)) redo_stack = Stack (len (клипборд)) remove () undo () redo ()

Изход:

Премахване: [„A“, „B“, „C“, „D“, „E“]

програма от серия на Фибоначи в Java

Отмяна: [„A“, „B“, „C“, „D“, „E“, „F“]

Повторно: [„A“, „B“, „C“, „D“, „E“]

С това стигнахме до края на тази структура на данните за стека в статията на Python. Ако успешно сте разбрали и стартирали кодовете сами, вече не сте начинаещ в структурата на данните за стекове.

Имате въпрос към нас? Моля, споменете го в раздела за коментари на тази статия и ние ще се свържем с вас възможно най-скоро.

За да получите задълбочени познания за Python заедно с различните му приложения, можете да се регистрирате за живо с 24/7 поддръжка и доживотен достъп.