A krūva yra linijinė duomenų struktūra, kuri saugo elementus a Paskutinis atvykimas / pirmasis išėjimas (LIFO) arba „First-In/Last-Out“ (FILO) būdu. Į krūvą naujas elementas pridedamas viename gale, o elementas pašalinamas tik iš to galo. Įterpimo ir ištrynimo operacijos dažnai vadinamos push ir pop.

Su kaminu susijusios funkcijos yra šios:

• tuščia() – Grąžina, ar krūva tuščia – Laiko sudėtingumas: O(1)
• dydis () – Grąžina krūvos dydį – Laiko sudėtingumas: O(1)
• top() / peek() – Grąžina nuorodą į aukščiausią krūvos elementą – Laiko sudėtingumas: O(1)
• stumti (a) – Įterpia elementą „a“ krūvos viršuje – Laiko sudėtingumas: O(1)
• pop () – Ištrina aukščiausią krūvos elementą – Laiko sudėtingumas: O(1)

Įgyvendinimas:

Yra įvairių būdų, kaip dėklas gali būti įdiegtas Python. Šiame straipsnyje aprašomas dėklo įgyvendinimas naudojant duomenų struktūras ir modulius iš Python bibliotekos.
Stack Python gali būti įdiegtas šiais būdais:

• sąrašą
• Kolekcijos.deque
• eilė.LifoQueue

Diegimas naudojant sąrašą:

Python integruotas duomenų struktūros sąrašas gali būti naudojamas kaip krūva. Vietoj push(), append() naudojamas elementams pridėti prie krūvos viršaus, o pop() pašalina elementą LIFO tvarka.
Deja, sąrašas turi keletą trūkumų. Didžiausia problema yra ta, kad augant gali kilti greičio problemų. Sąrašo elementai saugomi vienas šalia kito atmintyje. Jei krūva išauga didesnė už atminties bloką, kuriame šiuo metu ji yra, Python turi atlikti tam tikrą atminties paskirstymą. Dėl to kai kurie append() skambučiai gali užtrukti daug ilgiau nei kiti.

# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

Diegimas naudojant collections.deque:

Python steką galima įdiegti naudojant deque klasę iš rinkinių modulio. Deque yra teikiama pirmenybė sąrašui tais atvejais, kai reikia greitesnių pridėjimo ir iššokimo operacijų abiejuose konteinerio galuose, nes deque suteikia O(1) laiko sudėtingumą pridėjimo ir iššokimo operacijoms, palyginti su sąrašu, kuriame pateikiama O(n) laiko sudėtingumas.

Deque naudojami tie patys metodai, kaip matyti sąraše, append () ir pop ().

# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

Diegimas naudojant eilės modulį

Eilės modulis taip pat turi LIFO eilę, kuri iš esmės yra stack. Duomenys įterpiami į eilę naudojant funkciją put() ir get() išima duomenis iš eilės.

Šiame modulyje yra įvairių funkcijų:

• maksimalus dydis – Eilėje leidžiamų prekių skaičius.
• tuščia() – Grąžinkite True, jei eilė tuščia, kitu atveju – False.
• pilnas () – Grąžinkite True, jei tokių yra maksimalus dydis prekių eilėje. Jei eilė buvo inicijuota su maxsize=0 (numatytasis), full() niekada nepateikia True.
• gauti () – Pašalinti ir grąžinti prekę iš eilės. Jei eilė tuščia, palaukite, kol prekė atsiras.
• get_nowait() – Grąžinkite prekę, jei ji iš karto pasiekiama, kitu atveju pakelkite eilęEmpty.
• įdėti (prekė) – Įdėkite prekę į eilę. Jei eilė pilna, prieš įtraukdami prekę palaukite, kol atsiras laisva vieta.
• įdėti_dabar (prekė) – Įdėkite prekę į eilę neužblokuodami. Jei iš karto nėra laisvos vietos, pakelkite „QueueFull“.
• qsize() – Grąžinti eilėje esančių elementų skaičių.

# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>

0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

Diegimas naudojant atskirai susietą sąrašą:

Susietame sąraše yra du metodai addHead(item) ir removeHead(), kurie veikia pastoviu laiku. Šie du metodai yra tinkami kamino įgyvendinimui.

• getSize () – Gaukite krūvoje esančių elementų skaičių.
• Yra tuščias() – Grąžinti „True“, jei krūva tuščia, „False“, kitaip.
• žvilgtelėti () – Grąžinti viršutinį daiktą krūvoje. Jei krūva tuščia, pakelkite išimtį.
• stumti (vertė) – Įstumkite vertę į krūvos galvutę.
• pop () – Pašalinkite ir grąžinkite vertę kamino galvoje. Jei krūva tuščia, pakelkite išimtį.

Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:

# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # Gauti dabartinį krūvos dydį def getSize(self): return self.size # Patikrinkite, ar krūva tuščia def isEmpty(self): return self.size = = 0 # Gaukite viršutinį krūvos elementą def peek(self): # Sanitarinis patikrinimas, ar mes # žiūrime į tuščią krūvą. if self.isEmpty(): return None return self.head.next.value # Įstumkite reikšmę į krūvą. def push(self, value): node = Mazgas(value) node.next = self.head.next # Padarykite naują mazgą nukreiptą į dabartinę galvą self.head.next = mazgas #!!! # Atnaujinkite galvutę į naują mazgą self.size += 1 # Pašalinkite reikšmę iš kamino ir grąžinkite. def pop(self): if self.isEmpty(): pakelti Išimtis('Iš tuščios krūvos') remove = self.head.next self.head.next = pašalinti.next #!!! pakeistas self.size -= 1 grąžina remove.value # Tvarkyklės kodas, jei __name__ == '__main__': stack = Stack() for i diapazone (1, 11): stack.push(i) print(f' Stack: {stack}') _ diapazone (1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # kintamojo pavadinimas pakeistas print(f'Stack: { stack}')>

Išvestis

Stack: 10->9->8->7->6->5->4->3->2->1 Pop: 10 Pop: 9 Pop: 8 Pop: 7 Pop: 6 Stack: 5->4->3->2->1>

Stack privalumai:

• Stackai yra paprastos duomenų struktūros su tiksliai apibrėžtu operacijų rinkiniu, todėl jas lengva suprasti ir naudoti.
• Stacks yra efektyvus elementų pridėjimui ir pašalinimui, nes šių operacijų laiko sudėtingumas yra O(1).
• Norėdami pakeisti elementų tvarką, naudojame kamino duomenų struktūrą.
• Stackai gali būti naudojami anuliavimo / perdarymo funkcijoms įgyvendinti programose.

Stack trūkumai:

• Dydžio apribojimas „Stack“ yra trūkumas ir, jei jie yra pilni, nebegalite pridėti daugiau elementų į krūvą.
• Stackai nesuteikia greitos prieigos prie kitų elementų, išskyrus viršutinį elementą.
• Stacks nepalaiko veiksmingos paieškos, nes elementus reikia kelti po vieną, kol surasite ieškomą elementą.