Izpratne par steka ieviešanu Python

Datu struktūrām ir galvenā loma programmēšanas pasaulē. Tie palīdz mums sakārtot mūsu datus tā, lai tos varētu efektīvi izmantot. Stacks ir viena no vienkāršākajām datu struktūrām.

Uzzināsim par steku un tā ieviešanu Python.

Kas ir kaudze?

Reālajā dzīvē kaudze ir līdzīga grāmatu, krēslu utt. kaudzei. Un tas atbilst LIFO principam. Tā ir vienkāršākā datu struktūra. Apskatīsim scenāriju ar reālās pasaules piemēru.

Pieņemsim, ka mums ir kaudze grāmatu šādi.

Ja mēs vēlamies trešo grāmatu no augšas, mums ir jānoņem pirmās divas grāmatas no augšas, lai izņemtu trešo grāmatu. Šeit augšējā grāmata nonāk kaudzē pēdējā un pirmajā vietā no kaudzes. Datu struktūras kaudze programmēšanā ievēro to pašu principu Last-in/First-out (LIFO).

Darbības Stackā

Kaudzē galvenokārt ir divas darbības

1. push (dati)

Pievieno vai nospiež datus kaudzē.

2. pop()

Noņem vai paceļ augšējo elementu no kaudzes.

Skatiet tālāk redzamos push un pop darbību ilustrācijas.

Mēs uzrakstīsim dažas palīgfunkcijas, kas palīdzēs iegūt vairāk informācijas par steku.

Apskatīsim viņus.

palūrēt ()

Atgriež augšējo elementu no kaudzes.

ir tukšs()

Atgriež neatkarīgi no tā, vai kaudze ir tukša vai nav.

Pietiekami daudz steka datu struktūras konceptuālo aspektu. Bez liekām pūlēm ķersimies pie ieviešanas.

Es pieņemu, ka jūsu datorā ir instalēts python, ja nē, varat arī izmēģināt tiešsaistes kompilatoru.

Stack ieviešana

Ieviešanas steka ir vienkāršākā, salīdzinot ar citām datu struktūras implementācijām. Mēs Python varam ieviest steku vairākos veidos.

Apskatīsim tos visus pa vienam.

#1. Saraksts

Mēs ieviesīsim steku, izmantojot sarakstu klasē. Apskatīsim steka ieviešanu soli pa solim.

1. darbība. Uzrakstiet klasi ar nosaukumu Stack.

class Stack:
	pass

2. darbība: mums ir jāuztur dati sarakstā. Klasē Stack pievienosim tukšu sarakstu ar nosaukuma elementiem.

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

3. darbība. Lai elementus ievietotu kaudzē, mums ir nepieciešama metode. Uzrakstīsim push metodi, kas izmanto datus kā argumentu, un pievienosim to elementu sarakstam.

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

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

4. darbība. Līdzīgi uzrakstīsim pop metodi, kas izceļ augšējo elementu no kaudzes. Mēs varam izmantot saraksta datu tipa pop metodi.

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

Mēs esam pabeiguši steka ieviešanu ar nepieciešamajām darbībām. Tagad pievienosim palīgfunkcijas, lai iegūtu vairāk informācijas par steku.

5. darbība. Mēs varam iegūt augstāko elementu no kaudzes, izmantojot negatīvo indeksu. Koda elements [-1] atgriež pēdējo no saraksta. Mūsu gadījumā tas ir kaudzes augšējais elements.

class Stack:
	## ...

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

6. darbība: ja elementu saraksta garums ir 0, tad kaudze ir tukša. Uzrakstīsim metodi, kas atgriež neatkarīgi no tā, vai elements ir tukšs vai nav.

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

Mēs esam pabeiguši steka ieviešanu, izmantojot saraksta datu tipu.

Ak! pagaidiet, mēs to tikko ieviesām. Bet es neredzēju, kā to izmantot. Kā tad to lietot?

Nāciet, redzēsim, kā to īstenot. Mums ir jāizveido objekts, lai klasei Stack to izmantotu. Tas nav nekas īpašs. Vispirms darīsim to.

class Stack: 
    ## ...

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

Mēs esam izveidojuši steka objektu un esam gatavi to izmantot. Izpildiet tālāk norādītās darbības, lai pārbaudītu steka darbības.

• Pārbaudiet, vai kaudze ir tukša, izmantojot metodi is_empty. Tam vajadzētu atgriezties True.
• Iespiediet skaitļus 1, 2, 3, 4, 5 kaudzē, izmantojot push metodi.
• Metodei is_empty ir jāatgriež False. Pārbaudi.
• Drukājiet augšējo elementu, izmantojot skatīšanās metodi.
• Izvelciet elementu no kaudzes, izmantojot pop metodi.
• Pārbaudiet skatīšanās elementu. Tam jāatgriež elements 4.
• Tagad izlieciet visus elementus no kaudzes.
• Metodei is_empty ir jāatgriež vērtība True. Pārbaudi.

Mūsu steka ieviešana ir pabeigta, ja tā iztur visas iepriekš minētās darbības. Mēģiniet uzrakstīt kodu iepriekšminētajām darbībām.

Vai jūs uzrakstījāt kodu? Nē, neuztraucieties, pārbaudiet tālāk norādīto kodu.

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

Urā! mēs esam pabeiguši steka ieviešanu no nulles, izmantojot saraksta datu tipu. Ja izpildīsit iepriekš minēto kodu, jūs redzēsit izvadi, kā minēts tālāk.

True
False
5
4
True

Mēs varam tieši izmantot saraksta datu tipu kā steku. Iepriekš minētā steka ieviešana palīdz izprast steka ieviešanu arī citās programmēšanas valodās.

Varat arī apskatīt šos ar sarakstu saistītos rakstus.

Apskatīsim iebūvēto deque no kolekcijām iebūvēto moduli, kas var darboties kā kaudze.

#2. deque no kolekcijām

Tā tiek īstenota kā divgalu rinda. Tā kā tas atbalsta elementu pievienošanu un noņemšanu no abiem galiem. Tāpēc mēs varam to izmantot kā kaudzi. Mēs varam likt tai ievērot steka LIFO principu.

Tas tiek ieviests, izmantojot citas datu struktūras, ko sauc par divkārši saistītu sarakstu. Tātad elementu ievietošanas un dzēšanas veiktspēja ir konsekventa. Piekļuve elementiem no vidējā saistītā saraksta aizņēma O (n) laiku. Mēs varam to izmantot kā kaudzi, jo nav nepieciešams piekļūt vidējiem elementiem no kaudzes.

Pirms steka ieviešanas apskatīsim metodes, kas tiek izmantotas steka ieviešanai, izmantojot rindu.

• append(data) – izmanto, lai nospiestu datus stekā
• pop() – izmanto, lai noņemtu augšējo elementu no kaudzes

Nav alternatīvu metožu peek un is_empty. Skatīšanās metodes vietā varam izdrukāt visu kaudzi. Tālāk mēs varam izmantot len ​​metodi, lai pārbaudītu, vai kaudze ir tukša.

Ieviesīsim steku, izmantojot deque no kolekciju moduļa.

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)

Tieši tā. Mēs esam iemācījušies, kā ieviest steku, izmantojot deque no kolekciju iebūvētā moduļa. Ja izpildīsit iepriekš minēto programmu, jūs saņemsit izvadi, kā minēts tālāk.

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

Līdz šim mēs esam redzējuši divus veidus, kā ieviest steku. Vai ir kādi citi veidi, kā ieviest steku? Jā! Apskatīsim pēdējo veidu, kā ieviest steku šajā apmācībā.

#3. LifoQueue

Pats nosaukums LifoQueue saka, ka tas seko LIFO principam. Tāpēc mēs to varam bez šaubām izmantot kā kaudzi. Tas ir no iebūvētā moduļa rindas. LifoQueue nodrošina dažas ērtas metodes, kas ir noderīgas steka ieviešanā. Apskatīsim viņus

• put(data) – pievieno vai nospiež datus rindā
• get() – noņem vai izliek no rindas augšējo elementu
• tukšs() – atgriež neatkarīgi no tā, vai kaudze ir tukša vai nav
• qsize() – atgriež rindas garumu

Ieviesīsim steku, izmantojot LifoQueue no rindas moduļa.

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

Ja izpildīsit iepriekš minēto programmu, to nemainot, jūs iegūsit tālāk minēto izvadi.

True
False
5
4
3
Size 2
2
1
True

Stack pielietojums

Tagad jums ir pietiekami daudz zināšanu par skursteņiem, lai tos izmantotu programmēšanas problēmās. Apskatīsim problēmu un atrisināsim to, izmantojot steku.

Dotajā izteiksmē uzrakstiet programmu, lai pārbaudītu, vai iekavas, iekavas, cirtainie iekavas ir pareizi vai nē.

Apskatīsim dažus piemērus.

Ievade: „[{}]([])”

Izvade: līdzsvarota

Ievade: “{[}]([])”

Izvade: nav līdzsvarota

Mēs varam izmantot steku, lai atrisinātu iepriekš minēto problēmu. Apskatīsim darbības, lai atrisinātu problēmu.

• Izveidojiet kaudzi, lai saglabātu rakstzīmes.
• Ja izteiksmes garums ir nepāra, tad izteiksme ir Nav līdzsvarota
• Atkārtojiet, izmantojot doto izteiksmi.
  • Ja pašreizējā rakstzīme ir sākuma iekava no ( vai { vai [, then push it to stack.
  • Else if the current character is a closing bracket ) or } or ]pēc tam izlec no kaudzes.
  • Ja uznirstošā rakstzīme atbilst sākuma iekavai, turpiniet, pretējā gadījumā iekavas nav līdzsvarotas.
• Pēc iterācijas, ja kaudze ir tukša, vienādojums ir līdzsvarots, pretējā gadījumā vienādojums nav līdzsvarots.

Mēs varam izmantot iestatīto datu tipu iekavu atbilstības pārbaudei.

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

Mēs varam izmantot steku, lai atrisinātu daudz vairāk problēmu. Iepriekš minētā problēma ir viena no tām. Mēģiniet izmantot kaudzes koncepciju visur, kur, jūsuprāt, tas jums ir vispiemērotākais.

Secinājums

Jā! Jūs esat pabeidzis apmācību. Es ceru, ka jums patika apmācība tikpat ļoti kā man tās veidošanas laikā. Tas ir viss apmācībai.

Laimīgu kodēšanu 🙂 👨‍💻