A kup je linearna podatkovna struktura, ki shranjuje elemente v a Zadnji vstop/prvi ven (LIFO) ali način First In/Last Out (FILO). V skladu je nov element dodan na enem koncu in element je odstranjen samo s tega konca. Operaciji vstavljanja in brisanja se pogosto imenujeta push in pop.

Funkcije, povezane s skladom, so:

• prazno() – Vrne, ali je sklad prazen – Časovna kompleksnost: O(1)
• velikost () – Vrne velikost sklada – Časovna kompleksnost: O(1)
• top() / peek() – Vrne sklic na najvišji element sklada – Časovna kompleksnost: O(1)
• potisni(a) – Vstavi element ‘a’ na vrh sklada – Časovna kompleksnost: O(1)
• pop() – Izbriše najvišji element sklada – Časovna kompleksnost: O(1)

Izvedba:

V Pythonu je sklad mogoče implementirati na različne načine. Ta članek pokriva implementacijo sklada z uporabo podatkovnih struktur in modulov iz knjižnice Python.
Stack v Pythonu je mogoče implementirati na naslednje načine:

• seznam
• Zbirke.deque
• čakalna vrsta.LifoQueue

Izvedba z uporabo seznama:

Pythonov vgrajen seznam struktur podatkov se lahko uporablja kot sklad. Namesto push() se append() uporablja za dodajanje elementov na vrh sklada, medtem ko pop() odstrani element v vrstnem redu LIFO.
Na žalost ima seznam nekaj pomanjkljivosti. Največja težava je, da lahko med rastjo naleti na težave s hitrostjo. Elementi na seznamu so shranjeni drug poleg drugega v pomnilniku; če sklad postane večji od bloka pomnilnika, ki ga trenutno vsebuje, potem mora Python narediti nekaj dodelitev pomnilnika. To lahko povzroči, da nekateri klici append() trajajo veliko dlje kot drugi.

# 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: []>

Izvedba z uporabo collections.deque:

Sklad Python je mogoče implementirati z uporabo razreda deque iz modula zbirk. Deque ima prednost pred seznamom v primerih, ko potrebujemo hitrejše operacije dodajanja in izpiranja z obeh koncev vsebnika, saj deque zagotavlja časovno kompleksnost O(1) za operacije dodajanja in izpiranja v primerjavi s seznamom, ki zagotavlja O(n) časovna kompleksnost.

Uporabljeni sta enaki metodi na deque, kot je prikazano na seznamu, append() in 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([])>

Izvedba z modulom čakalne vrste

Modul Queue ima tudi čakalno vrsto LIFO, ki je v bistvu sklad. Podatki se vstavijo v čakalno vrsto s funkcijo put(), get() pa vzame podatke iz čakalne vrste.

V tem modulu so na voljo različne funkcije:

• maxsize – Število elementov, dovoljenih v čakalni vrsti.
• prazno() – Vrni True, če je čakalna vrsta prazna, v nasprotnem primeru False.
• poln() – Vrni True, če obstajajo maxsize elementov v čakalni vrsti. Če je bila čakalna vrsta inicializirana z maxsize=0 (privzeto), potem full() nikoli ne vrne True.
• dobiti () – Odstranite in vrnite element iz čakalne vrste. Če je čakalna vrsta prazna, počakajte, da je element na voljo.
• get_nowait() – Vrni element, če je takoj na voljo, sicer dvigni QueueEmpty.
• postaviti (predmet) – Postavite predmet v čakalno vrsto. Če je čakalna vrsta polna, počakajte, da bo na voljo prosto mesto, preden dodate element.
• put_nowait(element) – Postavite element v čakalno vrsto brez blokiranja. Če ni takoj na voljo nobene proste reže, dvignite QueueFull.
• qsize() – Vrni število elementov v čakalni vrsti.

# 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>

Izvedba z enojno povezanim seznamom:

Povezani seznam ima dve metodi addHead(item) in removeHead(), ki se izvajata v konstantnem času. Ti dve metodi sta primerni za izvedbo sklada.

• getSize() – Pridobite število elementov v kupu.
• je prazno() – Vrni True, če je sklad prazen, drugače pa False.
• pokukati() – Vrnite zgornji element v kupu. Če je sklad prazen, dvignite izjemo.
• potisni (vrednost) – Potisnite vrednost v glavo sklada.
• pop() – Odstranite in vrnite vrednost v glavi sklada. Če je sklad prazen, dvignite izjemo.

Spodaj je izvedba zgornjega pristopa:

# 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] # Pridobi trenutno velikost sklada def getSize(self): return self.size # Preveri, če je sklad prazen def isEmpty(self): return self.size = = 0 # Pridobite zgornji element sklada def peek(self): # Sanitarni pregled, da vidimo, ali # kukamo v prazen sklad. if self.isEmpty(): return None return self.head.next.value # Potisnite vrednost v sklad. def push(self, value): vozlišče = vozlišče(vrednost) node.next = self.head.next # Naj bo novo vozlišče kazalo na trenutno glavo self.head.next = vozlišče #!!! # Posodobite glavo, da bo novo vozlišče self.size += 1 # Odstranite vrednost iz sklada in se vrnite. def pop(self): if self.isEmpty(): raise Exception('Izstrelitev iz praznega sklada') remove = self.head.next self.head.next = remove.next #!!! spremenjena self.size -= 1 return remove.value # Koda gonilnika if __name__ == '__main__': stack = Stack() for i in range(1, 11): stack.push(i) print(f' Stack: {stack}') for _ in range(1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # spremenjeno ime spremenljivke print(f'Stack: { sklad}')>

Izhod

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>>

Prednosti Stacka:

• Skladi so preproste podatkovne strukture z natančno definiranim naborom operacij, zaradi česar jih je enostavno razumeti in uporabljati.
• Skladi so učinkoviti za dodajanje in odstranjevanje elementov, saj imajo te operacije časovno zahtevnost O(1).
• Da obrnemo vrstni red elementov, uporabimo podatkovno strukturo sklada.
• Skladi se lahko uporabljajo za izvajanje funkcij razveljavitve/ponovitve v aplikacijah.

Slabosti Stacka:

• Omejitev velikosti v Stacku je pomanjkljivost in če so polni, v sklad ne morete dodati več elementov.
• Skladi ne omogočajo hitrega dostopa do elementov, razen do zgornjega elementa.
• Skladi ne podpirajo učinkovitega iskanja, saj morate elemente izpostavljati enega za drugim, dokler ne najdete elementa, ki ga iščete.