Le strutture dati sono una raccolta di valori di dati, le relazioni tra di essi e le funzioni o operazioni che possono essere applicate ai dati. Ora sono disponibili molte strutture dati. Ma oggi il nostro focus sarà su Stack Data Structures. Discuterò i seguenti argomenti:
- Perché le strutture dati?
- Tipi di strutture dati
- Cos'è la struttura dei dati dello stack?
- Creazione della struttura dei dati dello stack
- Spingi gli elementi nello stack
- Elementi pop da Stack
- Applicazioni della struttura dei dati dello stack
Perché le strutture dati?
Per rispondere a questa domanda dovrai pensare ad un grande livello. Pensa a come le mappe di Google ti mostrano il percorso migliore in una frazione di secondi, come restituisce i risultati della ricerca in microsecondi. Non tratta solo 100 siti web, tratta più di un miliardo di siti e mostra ancora risultati così rapidi.
Ebbene, sebbene l'algoritmo utilizzato svolga un ruolo cruciale, la struttura dei dati o il contenitore utilizzato è il fondamento di tale algoritmo. In qualsiasi applicazione, organizzare e archiviare i dati in un modo o in una struttura più adatti al loro utilizzo è la chiave per un accesso e un trattamento dei dati efficienti.
Tipi di strutture dati
Esistono alcune strutture dati standard che possono essere utilizzate per lavorare in modo efficiente con i dati. Possiamo persino personalizzarli o costruirne di nuovi per adattarli alla nostra applicazione.
Cos'è la struttura dei dati dello stack?
Considera alcuni esempi di vita reale:
- Spedizione in carico
- Piatti su un vassoio
- Pila di monete
- Pila di cassetti
- Manovra di treni in uno scalo ferroviario
Tutti questi esempi seguono a Ultimo ad entrare, primo ad uscire strategia. Considera i piatti su un vassoio, quando vuoi prendere un piatto sei costretto a prendere un piatto dall'alto mentre quando i piatti erano tenuti sul vassoio devono essere in ordine inverso. Sopra gli esempi che seguono il Last-In-First-Out (LIFO) principio sono noti come Pila .
A parte le operazioni complementari, posso dire che le principali Operazioni possibili sullo stack sono:
- Spingere o inserire un elemento in cima alla pila
- Fai scoppiare o rimuovi un elemento dalla cima della pila
Creazione della struttura dei dati dello stack
class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elementi = [Nessuno] * self .__ max_size self .__ top = -1
- max_size è il numero massimo di elementi previsti nello stack.
- Gli elementi dello stack vengono memorizzati nell'elenco Python.
- Top indica l'indice più in alto dello stack che viene inizialmente preso -1 per contrassegnare lo stack vuoto.
Lo stato iniziale dello Stack può essere visto nella figura dove max_size = 5
Spingi l'elemento nello stack
Ora, se vuoi inserire o spingere un elemento nello stack, devi ricordarlo
- La parte superiore punterà l'indice a cui verrà inserito l'elemento.
- E che nessun elemento verrà inserito quando lo stack è pieno, cioè quando max_size = top.
Quindi quale dovrebbe essere l'algoritmo ??
# restituisce la dimensione massima dello stack def get_max_size (self): return self .__ max_size # restituisce il valore bool sia che lo stack sia pieno o meno, True se pieno e False altrimenti def is_full (self): return self.get_max_size () - 1 == self .__ top # spinge l'elemento in cima allo stack def push (self, data): if (self.is_full ()): print ('lo stack è già pieno') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data # Puoi usare il seguente __str __ () per stampare gli elementi dell'oggetto DS durante il debug def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg = 'Stack data (Top to Bottom):' + msg return msgOra, quando esegui quanto segue:
programma di pianificazione round robin in c
stack1 = Stack (4)
#Push tutti gli elementi richiesti.
stack1.push ('A')
stack1.push ('B')
stack1.push ('C')
stack1.push ('E')
print (stack1.is_full ())
stampa (pila1)
Produzione:
lo stack è già pieno
Vero
Stack di dati (dall'alto verso il basso): D C B A
configurazione di php su Windows
Elementi pop da Stack
Ora, dopo aver inserito gli elementi nella pila, vuoi farli scoppiare, quindi devi occuparti di quanto segue:
- Lo stack non è vuoto, ovvero in alto! = -1
- Quando si eliminano i dati, la parte superiore deve puntare alla parte superiore precedente dello stack.
Allora, quale sarà l'algoritmo ??
#returns bool value se lo stack è vuoto o meno, True se vuoto e False altrimenti def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): print ('niente da aprire, già vuoto') else: a = self .__ elementi [self .__ top] self .__ top = self .__ top-1 restituisce un # mostra tutti gli elementi dello stack dall'alto verso il basso def display (self): for i in range (self .__ top, -1, -1): print (self .__ elementi [i], end = '') print ()Ora, considerando lo stack creato in precedenza, prova a inserire gli elementi
print (stack1.pop ())
print (stack1.pop ())
stampa (pila1)
print (stack1.pop ())
print (stack1.pop ())
print (stack1.pop ())
Produzione:
D
C
Stack di dati (dall'alto verso il basso): B A
B
PER
niente da scoppiare, già vuoto
Applicazioni della struttura dei dati dello stack
- Esempio 1:
Uno stack viene utilizzato per implementare l'algoritmo di corrispondenza delle parentesi per la valutazione delle espressioni aritmetiche e anche nell'implementazione delle chiamate ai metodi.
La risposta è 5.
- Esempio 2:
Appunti in Windows usa due stack per implementare le operazioni di annullamento-ripetizione (ctrl + z, ctrl + y). Avresti lavorato su editor di parole di Windows come MS-Word, Blocco note, ecc. Ecco un testo scritto in MS-Word. Osserva come il testo è cambiato facendo clic su Ctrl-Z e Ctrl-Y.
Ecco un codice che simula l'operazione di annullamento-ripetizione. Esamina il codice e osserva come viene utilizzato lo stack in questa implementazione.
#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elementi = [Nessuno] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): print ('Lo stack è pieno !!') else: self .__ top + = 1 self .__ elementi [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Lo stack è vuoto! ! ') else: data = self .__ elementi [self .__ top] self .__ top- = 1 restituisce i dati def display (self): if (self.is_empty ()): print (' Lo stack è vuoto ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size #Puoi usare il seguente __str __ () per stampare gli elementi del Oggetto DS durante il debug def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elementi [index])) index- = 1 msg = ' '.join (msg) msg =' Stack data (Top to Bottom): '+ msg return ms g #funzione per implementare l'operazione di rimozione o backspace def remove (): global clipboard, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Remove:', clipboard) #funzione per implementare l'operazione di annullamento def undo (): global clipboard, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Non ci sono dati da annullare') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', clipboard) #funzione per implementare l'operazione redo def redo (): global clipboard, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Non ci sono dati to redo ') else: data = redo_stack.pop () if (data not in clipboard): print (' Non ci sono dati da rifare ') redo_stack.push (data) else: clipboard.remove (data) undo_stack.push ( data) print ('Redo:', clipboard) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (clipboard)) redo_stack = Stack (len (appunti)) remove () undo () redo ()Produzione:
Rimuovi: ['A', 'B', 'C', 'D', 'E']
accoppiamento stretto vs accoppiamento lento
Annulla: ['A', 'B', 'C', 'D', 'E', 'F']
Ripeti: ['A', 'B', 'C', 'D', 'E']
Con questo, arriviamo alla fine di questo articolo Stack Data Structure in Python. Se hai compreso e eseguito con successo i codici da solo, non sei più un principiante di Stacks Data Structure.
Hai domande per noi? Si prega di menzionarlo nella sezione commenti di questo articolo e ti risponderemo il prima possibile.
Per ottenere una conoscenza approfondita di Python e delle sue varie applicazioni, puoi iscriverti a live con supporto 24 ore su 24, 7 giorni su 7 e accesso a vita.