Разумевање имплементације стека у Питхон-у

Структуре података играју кључну улогу у свету програмирања. Они нам помажу да организујемо своје податке на начин који се може ефикасно користити. Стек је једна од најједноставнијих структура података.

Хајде да научимо више о стеку и његовој имплементацији у Питхон-у.

Шта је стек?

Гомила је слична гомили књига, столица итд., у стварном животу. И следи принцип Ласт-ин/Фирст-оут ​​(ЛИФО). То је најједноставнија структура података. Хајде да видимо сценарио са примером из стварног света.

Рецимо да имамо гомилу књига на следећи начин.

Када желимо трећу књигу одозго, морамо уклонити прве две књиге са врха да бисмо извадили трећу књигу. Овде, највиша књига иде последња на гомилу и долази прва од гомиле. Стог структуре података прати исти принцип Ласт-ин/Фирст-оут ​​(ЛИФО) у програмирању.

Операције у стеку

У стеку су углавном две операције

1. пусх (подаци)

Додаје или гура податке у стек.

2. поп()

Уклања или искаче највиши елемент из снопа.

Погледајте доње илустрације пусх и поп операција.

Написаћемо неке помоћне функције које ће нам помоћи да добијемо више информација о стеку.

Хајде да их видимо.

завирити ()

Враћа највиши елемент из стека.

Празно()

Враћа да ли је стек празан или не.

Доста концептуалних аспеката структуре података стека. Пређимо на имплементацију без даљег одлагања.

Претпостављам да имате инсталиран Питхон на рачунару, ако не, можете испробати и онлајн компајлер.

Имплементација стека

Имплементација стека је најлакша у поређењу са другим имплементацијама структуре података. У Питхон-у можемо имплементирати стек на више начина.

Хајде да их видимо све један по један.

#1. Листа

Ми ћемо имплементирати стек користећи листу у класи. Хајде да видимо корак по корак имплементацију стека.

Корак 1: Напишите класу под називом Стацк.

class Stack:
	pass

Корак 2: Морамо да одржавамо податке на листи. Хајде да додамо празну листу у класу Стацк са елементима имена.

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

Корак 3: Да бисмо гурнули елементе у стек, потребан нам је метод. Хајде да напишемо пусх метод који узима податке као аргумент и додаје их листи елемената.

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

	def push(self, data):
		self.elements.append(data)
		return data

Корак 4: Слично, хајде да напишемо поп метод који искаче највиши елемент из стека. Можемо користити метод поп типа података листе.

class Stack:
	## ...
	def pop(self):
		return self.elements.pop()

Завршили смо имплементацију стека са потребним операцијама. Сада, додајмо помоћне функције да бисмо добили више информација о стеку.

  Поправите шифру грешке НВИДИА ОпенГЛ драјвера 8

Корак 5: Можемо добити највиши елемент из стека користећи негативни индекс. Елемент кода <спан дата-токен-индек=”2″ дата-реацтроот=””>[-1] враћа последњу листу. То је највиши елемент стека у нашем случају.

class Stack:
	## ...

	def peek(self):
		return self.elements[-1]

Корак 6: Ако је дужина листе елемената 0, онда је стек празан. Хајде да напишемо методу која враћа да ли је елемент празан или не.

class Stack:
	## ...
	def is_empty(self):
		return len(self.elements) == 0

Завршили смо имплементацију стека користећи тип података листе.

Ох! чекајте да смо га управо имплементирали. Али, нисам видео како да га користим. Како га онда користити?

Хајде да видимо како да то применимо. Морамо да креирамо објекат за класу Стацк да бисмо га користили. То није велика ствар. Хајде да то урадимо прво.

class Stack: 
    ## ...

if __name__ == '__main__':
    stack = Stack()

Направили смо стек објекат и спремни смо да га користимо. Хајде да пратимо доле наведене кораке да тестирамо операције стека.

  • Проверите да ли је стек празан или не помоћу методе ис_емпти. Требало би да врати Труе.
  • Гурните бројеве 1, 2, 3, 4, 5 у гомилу користећи метод гурања.
  • Метод ис_емпти треба да врати Фалсе. Провери.
  • Одштампајте највиши елемент користећи метод завиривања.
  • Избаците елемент из стека помоћу методе поп.
  • Проверите елемент завиривања. Требало би да врати елемент 4.
  • Сада извуците све елементе из стека.
  • Метод ис_емпти треба да врати Труе. Провери.

Наша имплементација стека је завршена ако прође све горе наведене кораке. Покушајте да напишете код за горе наведене кораке.

Јеси ли ти написао код? Не, не брините, проверите код испод.

class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
    
    def pop(self): 
        return self.elements.pop() 
        
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

if __name__ == '__main__':
    stack = Stack()
    
    ## checking is_empty method -> true
    print(stack.is_empty())

    ## pushing the elements
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)

    ## again checking is_empty method -> false
    print(stack.is_empty())

    ## printing the topmost element of the stack -> 5
    print(stack.peek())

    ## popping the topmost element -> 5
    stack.pop()

    ## checking the topmost element using peek method -> 4
    print(stack.peek())

    ## popping all the elements
    stack.pop()
    stack.pop() 
    stack.pop() 
    stack.pop() 

    ## checking the is_empty method for the last time -> true
    print(stack.is_empty())

Ура! завршили смо имплементацију стека од нуле користећи тип података листе. Видећете излаз као што је наведено у наставку ако покренете горњи код.

True
False
5
4
True

Можемо директно користити тип података листе као стек. Горња имплементација стека помаже вам да разумете имплементацију стека и у другим програмским језицима.

  Како направити прилагођену тему боја за Фирефок

Такође можете погледати ове чланке везане за листу.

Хајде да видимо уграђени декуе из уграђеног модула колекција који може да делује као стек.

#2. дека из збирки

Реализован је као двострани ред. Пошто подржава додавање и уклањање елемената са оба краја. Стога га можемо користити као стек. Можемо га натерати да прати ЛИФО принцип стека.

Имплементира се коришћењем других структура података које се називају двоструко повезана листа. Дакле, перформансе уметања и брисања елемената су доследне. Приступ елементима са средње повезане листе трајао је О(н) времена. Можемо га користити као стек јер нема потребе за приступом средњим елементима из стека.

Пре имплементације стека, да видимо методе које се користе за имплементацију стека помоћу реда.

  • аппенд(дата) – користи се за гурање података у стек
  • поп() – користи се за уклањање највишег елемента из стека

Не постоје алтернативне методе за пеек и ис_емпти. Можемо да одштампамо цео сноп уместо методе завиривања. Затим можемо користити метод лен да проверимо да ли је стек празан или не.

Хајде да имплементирамо стек користећи декуе из модула колекције.

from collections import deque

## creating deque object
stack = deque()

## checking whether stack is empty or not -> true
print(len(stack) == 0)

## pushing the elements
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

## again checking whether stack is empty or not -> false
print(len(stack) == 0)

## printing the stack
print(stack)

## popping the topmost element -> 5
stack.pop()

## printing the stack
print(stack)

## popping all the elements
stack.pop()
stack.pop() 
stack.pop() 
stack.pop() 

## checking the whether stack is empty or not for the last time -> true
print(len(stack) == 0)

То је то. Научили смо како да имплементирамо стек користећи декуе из уграђеног модула колекција. Добићете излаз као што је наведено у наставку ако извршите горњи програм.

True
False
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4])
True

До сада смо видели два начина за имплементацију стека. Постоје ли други начини за имплементацију стека? Да! Хајде да видимо коначни начин имплементације стека у овом водичу.

#3. ЛифоКуеуе

Сам назив ЛифоКуеуе говори да следи ЛИФО принцип. Стога га без икакве сумње можемо користити као стек. То је из редоследа уграђеног модула. ЛифоКуеуе пружа неке згодне методе које су корисне у имплементацији стека. Хајде да их видимо

  • пут(подаци) – додаје или гура податке у ред
  • гет() – уклања или искаче највиши елемент из реда
  • емпти() – враћа да ли је стек празан или не
  • ксизе() – враћа дужину реда

Хајде да имплементирамо стек користећи ЛифоКуеуе из модула куеуе.

from queue import LifoQueue

## creating LifoQueue object
stack = LifoQueue()

## checking whether stack is empty or not -> true
print(stack.empty())

## pushing the elements
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)

## again checking whether stack is empty or not -> false
print(stack.empty())

## popping all the elements
print(stack.get())
print(stack.get())
print(stack.get())

## checking the stack size
print("Size", stack.qsize())

print(stack.get())
print(stack.get())

## checking the whether stack is empty or not for the last time -> true
print(stack.empty())

Добићете доле наведени излаз ако извршите горњи програм без промене.

True
False
5
4
3
Size 2
2
1
True

Примена Стацк-а

Сада имате довољно знања о стековима да га примените у програмским проблемима. Хајде да видимо проблем и решимо га помоћу стека.

  Утишајте свој аларм покретом руке [Android]

Дати израз, напишите програм да проверите да ли су заграде, заграде, витичасте заграде правилно избалансиране или не.

Хајде да видимо неке примере.

Улазни: „[{}]([])”

Излаз: Балансиран

Улазни: „{[}]([])”

Излаз: Није избалансиран

Можемо користити стек да решимо горњи проблем. Хајде да видимо кораке за решавање проблема.

  • Направите стек за чување знакова.
  • Ако је дужина израза непарна, онда је израз Није уравнотежен
  • Пређите кроз дати израз.
    • Ако је тренутни знак почетна заграда из ( или { или [, then push it to stack.
    • Else if the current character is a closing bracket ) or } or ]а затим искочи из гомиле.
    • Ако се искакани знак поклапа са почетном заградом, онда наставите, иначе заграде нису избалансиране.
  • Након итерације, ако је стек празан онда је једначина уравнотежена, иначе једначина није уравнотежена.

Можемо да користимо сет података за проверу подударања заграда.

## stack
class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
        
    def pop(self): 
        return self.elements.pop() 
    
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

def balance_check(expression):
    ## checking the length of the expression
    if len(expression) % 2 != 0:
        ## not balanced if the length is odd
        return False
    
    ## for checking
    opening_brackets = set('([{') 
    pairs = set([ ('(',')'), ('[',']'), ('{','}') ]) 
    
    ## stack initialization
    stack = Stack()
    
    ## iterating through the given expression
    for bracket in expression:

        ## checking whether the current bracket is opened or not        
        if bracket in opening_brackets:
            ## adding to the stack 
            stack.push(bracket)
        else:
            ## popping out the last bracket from the stack
            popped_bracket = stack.pop()
        
            ## checking whether popped and current bracket pair
            if (popped_bracket, bracket) not in pairs:
                return False
    
    return stack.is_empty()

if __name__ == '__main__':
    if balance_check('[{}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")
    
    if balance_check('{[}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")

Можемо користити стек да решимо много више проблема. Горњи проблем је један од њих. Покушајте да примените концепт стека где год мислите да вам најбоље одговара.

Закључак

Иах! Завршили сте туторијал. Надам се да сте уживали у туторијалу колико и ја док сам га правио. То је то за туторијал.

Срећно кодирање 🙂 👨‍💻