A kaudze ir lineāra datu struktūra, kas saglabā vienumus a Last-in/First-Out (LIFO) vai First-In/Last-Out (FILO) veidā. Kaudzē jauns elements tiek pievienots vienā galā un elements tiek noņemts tikai no šī gala. Ievietošanas un dzēšanas darbības bieži sauc par push un pop.

Ar steku saistītās funkcijas ir:

• tukšs () – Atgriež, vai kaudze ir tukša – Laika sarežģītība: O(1)
• Izmērs() – Atgriež kaudzes izmēru – Laika sarežģītība: O(1)
• top () / palūrēt () – Atgriež atsauci uz steka augšējo elementu – Laika sarežģītība: O(1)
• push (a) – Ievieto elementu “a” kaudzes augšpusē – Laika sarežģītība: O(1)
• pop () – Dzēš steka augšējo elementu – Laika sarežģītība: O(1)

Īstenošana:

Ir dažādi veidi, kā steku var ieviest Python. Šis raksts aptver steka ieviešanu, izmantojot Python bibliotēkas datu struktūras un moduļus.
Stack programmā Python var ieviest, izmantojot šādus veidus:

• sarakstu
• Kolekcijas.deque
• rinda.LifoQueue

Ieviešana, izmantojot sarakstu:

Python iebūvēto datu struktūru sarakstu var izmantot kā kaudzi. Push() vietā tiek izmantots append(), lai pievienotu elementus kaudzes augšpusē, savukārt pop() noņem elementu LIFO secībā.
Diemžēl sarakstā ir daži trūkumi. Lielākā problēma ir tā, ka augot tam var rasties ātruma problēmas. Sarakstā esošie vienumi atmiņā tiek glabāti blakus viens otram, ja steka kļūst lielāka par atmiņas bloku, kurā tā pašlaik ir, Python ir jāveic daži atmiņas sadalījumi. Tas var novest pie tā, ka daži append() zvani var aizņemt daudz ilgāku laiku nekā citi.

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

Ieviešana, izmantojot collections.deque:

Python steku var ieviest, izmantojot deque klasi no kolekciju moduļa. Deque ir priekšroka salīdzinājumā ar sarakstu gadījumos, kad mums ir nepieciešamas ātrākas pievienošanas un pop operācijas no abiem konteinera galiem, jo ​​deque nodrošina O(1) laika sarežģītību pievienošanas un pop operācijām, salīdzinot ar sarakstu, kas nodrošina O(n) laika sarežģītība.

Deque tiek izmantotas tās pašas metodes, kas redzamas sarakstā, append () un 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([])>

Īstenošana, izmantojot rindas moduli

Rindas modulim ir arī LIFO rinda, kas būtībā ir kaudze. Dati tiek ievietoti rindā, izmantojot funkciju put() un get() izņem datus no rindas.

Šajā modulī ir pieejamas dažādas funkcijas:

• maksimālais izmērs – rindā atļauto vienumu skaits.
• tukšs () – Atgrieziet True, ja rinda ir tukša, vai False pretējā gadījumā.
• pilns () – Atgrieziet True, ja tādi ir maksimālais izmērs vienumi rindā. Ja rinda tika inicializēta ar maxsize=0 (noklusējums), tad full() nekad neatgriež True.
• gūt() – Noņemiet un atgrieziet preci no rindas. Ja rinda ir tukša, pagaidiet, līdz prece ir pieejama.
• get_nowait() – Atgrieziet preci, ja tāda ir uzreiz pieejama, pretējā gadījumā paaugstiniet QueueEmpty.
• likt (prece) – Ievietojiet preci rindā. Ja rinda ir pilna, pirms preces pievienošanas uzgaidiet, līdz ir pieejama brīva vieta.
• put_nowait(prece) – Ievietojiet vienumu rindā bez bloķēšanas. Ja uzreiz nav pieejams neviens brīvs slots, paaugstiniet QueueFull.
• qsize() – Atgriezt rindā esošo vienumu skaitu.

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

Ieviešana, izmantojot atsevišķi saistītu sarakstu:

Saistītajā sarakstā ir divas metodes addHead(item) un removeHead(), kas darbojas nemainīgā laikā. Šīs divas metodes ir piemērotas kaudzes ieviešanai.

• getSize() - Iegūstiet kaudzē esošo vienumu skaitu.
• ir tukšs() – Atgrieziet True, ja kaudze ir tukša, vai False pretējā gadījumā.
• palūrēt () – Atgriezt kaudzītes augšējo vienumu. Ja kaudze ir tukša, paaugstiniet izņēmumu.
• push (vērtība) – Iespiediet vērtību kaudzes galvā.
• pop () – Noņemiet un atgrieziet vērtību kaudzes galvā. Ja kaudze ir tukša, paaugstiniet izņēmumu.

Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.

# 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] # Iegūstiet pašreizējo steka izmēru def getSize(self): return self.size # Pārbaudiet, vai steks ir tukšs def isEmpty(self): return self.size = = 0 # Iegūstiet steka def peek(self) augšējo vienumu: # Sanitārā pārbaude, lai redzētu, vai # mēs apskatām tukšu kaudzīti. if self.isEmpty(): return None return self.head.next.value # Nospiediet vērtību kaudzē. def push(self, value): node = Node(value) node.next = self.head.next # Padarīt, ka jaunais mezgls norāda uz pašreizējo galvu self.head.next = mezgls #!!! # Atjauniniet galvu, lai tā būtu jaunais mezgls self.size += 1 # Noņemiet vērtību no steka un atgriezieties. def pop(self): if self.isEmpty(): paaugstina Izņēmums('Izlec no tukšas kaudzes') remove = self.head.next self.head.next = remove.next #!!! mainīts self.size -= 1 atgriež remove.value # Draivera kods, ja __name__ == '__main__': kaudze = Stack() for i diapazonā (1, 11): stack.push(i) print(f' Stack: {steck}') _ diapazonā (1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # mainīgā nosaukums mainīts print(f'Steck: { kaudze}')>

Izvade

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 priekšrocības:

• Stacki ir vienkāršas datu struktūras ar precīzi definētu darbību kopu, kas padara tās viegli saprotamas un lietojamas.
• Stacki ir efektīvi elementu pievienošanai un noņemšanai, jo šo darbību laika sarežģītība ir O(1).
• Lai mainītu elementu secību, mēs izmantojam steka datu struktūru.
• Stackus var izmantot, lai lietojumprogrammās ieviestu atsaukšanas/atkārtošanas funkcijas.

Stack trūkumi:

• Lieluma ierobežojums steksā ir trūkums, un, ja tie ir pilni, jūs nevarat pievienot vairāk elementu kaudzītei.
• Stacks nenodrošina ātru piekļuvi citiem elementiem, izņemot augšējo elementu.
• Stacks neatbalsta efektīvu meklēšanu, jo elementi ir jāpopē pa vienam, līdz atrodat meklēto elementu.