A pino on lineaarinen tietorakenne, joka tallentaa kohteita a Last-in/First-Out (LIFO) tai First-In/Last-Out (FILO) -tavalla. Pinossa uusi elementti lisätään toiseen päähän ja elementti poistetaan vain siitä päästä. Lisää- ja poistotoimintoja kutsutaan usein push- ja pop-toiminnoiksi.

Pinoon liittyvät toiminnot ovat:

• tyhjä() – Palauttaa, onko pino tyhjä – Aika monimutkaisuus: O(1)
• koko() – Palauttaa pinon koon – Aika monimutkaisuus: O(1)
• top() / kurkista() – Palauttaa viittauksen pinon ylimpään elementtiin – Aika monimutkaisuus: O(1)
• työnnä (a) – Lisää elementin ”a” pinon yläosaan – Aika monimutkaisuus: O(1)
• pop() – Poistaa pinon ylimmän elementin – Aika monimutkaisuus: O(1)

Toteutus:

Pythonissa pino voidaan toteuttaa useilla eri tavoilla. Tämä artikkeli kattaa pinon toteutuksen Python-kirjaston tietorakenteilla ja moduuleilla.
Pino Pythonissa voidaan toteuttaa seuraavilla tavoilla:

• lista
• Collections.deque
• jono.LifoQueue

Toteutus listalla:

Pythonin sisäänrakennettua tietorakennelistaa voidaan käyttää pinona. Kommentin push() sijaan append()-funktiota käytetään lisäämään elementtejä pinon yläosaan, kun taas pop() poistaa elementin LIFO-järjestyksessä.
Valitettavasti luettelossa on muutamia puutteita. Suurin ongelma on, että se voi joutua nopeusongelmiin kasvaessaan. Listan kohteet tallennetaan vierekkäin muistiin, jos pino kasvaa suuremmiksi kuin sillä hetkellä oleva muistilohko, Pythonin on tehtävä joitakin muistivarauksia. Tämä voi johtaa siihen, että jotkut append()-kutsut voivat kestää paljon kauemmin kuin toiset.

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

Käyttöönotto collections.dequen avulla:

Python-pino voidaan toteuttaa käyttämällä deque-luokkaa kokoelmamoduulista. Deque on suositeltavampi kuin luettelo tapauksissa, joissa tarvitsemme nopeampia liite- ja pop-operaatioita säilön molemmista päistä, koska deque tarjoaa O(1)-ajan monimutkaisuuden liittämis- ja pop-operaatioille verrattuna luetteloon, joka tarjoaa O(n) aika monimutkaisuus.

Dequessa käytetään samoja menetelmiä kuin listassa, append() ja 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([])>

Toteutus jonomoduulilla

Jonomoduulissa on myös LIFO-jono, joka on periaatteessa pino. Data lisätään jonoon put()-funktiolla ja get() ottaa tiedot pois jonosta.

Tässä moduulissa on saatavilla useita toimintoja:

• suurin koko – Jonossa sallittujen kohteiden määrä.
• tyhjä() – Palauta True, jos jono on tyhjä, False muussa tapauksessa.
• koko() – Palauta True, jos sellaisia ​​on suurin koko kohteita jonossa. Jos jono alustettiin arvolla maxsize=0 (oletus), full() ei koskaan palauta arvoa True.
• saada() – Poista ja palauta kohde jonosta. Jos jono on tyhjä, odota, kunnes tuote on saatavilla.
• get_nowait() – Palauta tuote, jos sellainen on heti saatavilla, muuten nosta QueueEmpty.
• laittaa (tuote) – Aseta tuote jonoon. Jos jono on täynnä, odota, kunnes vapaa paikka on käytettävissä, ennen kuin lisäät tuotteen.
• put_nowait(tuote) – Aseta kohde jonoon ilman estämistä. Jos vapaata paikkaa ei ole heti saatavilla, nosta QueueFull.
• qsize() – Palauta jonossa olevien kohteiden määrä.

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

Toteutus yksitellen linkitetyn luettelon avulla:

Linkitetyssä luettelossa on kaksi menetelmää addHead(item) ja removeHead(), jotka suoritetaan vakioajassa. Nämä kaksi menetelmää sopivat pinon toteuttamiseen.

• getSize() – Selvitä pinossa olevien kohteiden määrä.
• on tyhjä() – Palauta True, jos pino on tyhjä, False muussa tapauksessa.
• kurkistaa() – Palauta pinon ylin esine. Jos pino on tyhjä, nosta poikkeus.
• push(arvo) – Työnnä arvo pinon päähän.
• pop() – Poista ja palauta arvo pinon päässä. Jos pino on tyhjä, nosta poikkeus.

Alla on yllä olevan lähestymistavan toteutus:

# 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] # Hae pinon nykyinen koko def getSize(self): return self.size # Tarkista onko pino tyhjä def isEmpty(self): return self.size = = 0 # Hae pinon ylin kohde def peek(self): # Terveystarkista nähdäksemme, # kurkistammeko tyhjää pinoa. if self.isEmpty(): return None return self.head.next.value # Työnnä arvo pinoon. def push(self, value): solmu = Solmu(arvo) solmu.seuraava = self.head.next # Aseta uusi solmu osoittamaan nykyiseen päähän self.head.next = solmu #!!! # Päivitä pää uudeksi solmuksi self.size += 1 # Poista arvo pinosta ja palauta. def pop(self): if self.isEmpty(): nosta Poikkeus('Popping tyhjästä pinosta') remove = self.head.next self.head.next = poista.seuraava #!!! muutettu self.size -= 1 palauttaa remove.value # Ohjainkoodi if __name__ == '__main__': pino = Pino() i:lle alueella(1, 11): pino.push(i) print(f' Pino: {pino}') kohteelle _ alueella(1, 6): top_value = pino.pop() print(f'Pop: {top_value}') # muuttujan nimi muutettu print(f'Pino: { pino}')>

Lähtö

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

Stackin edut:

• Pinot ovat yksinkertaisia ​​tietorakenteita, joissa on hyvin määritelty toimintosarja, mikä tekee niistä helppoja ymmärtää ja käyttää.
• Pinot ovat tehokkaita elementtien lisäämiseen ja poistamiseen, koska näiden toimintojen aikamonimutkaisuus on O(1).
• Kääntääksemme elementtien järjestystä käytämme pinotietorakennetta.
• Pinoja voidaan käyttää kumoa/uudelleen-toimintojen toteuttamiseen sovelluksissa.

Stackin haitat:

• Pinon koon rajoitus on haitta, ja jos ne ovat täynnä, pinoon ei voi lisätä enempää elementtejä.
• Pinot eivät tarjoa nopeaa pääsyä muihin elementteihin kuin yläelementtiin.
• Pinot eivät tue tehokasta hakua, sillä elementtejä on pompattava yksitellen, kunnes löydät etsimäsi elementin.