Lo stack ha solo un'estremità aperta per spingere e scoppiare gli elementi di dati dall'altra. Queue ha entrambe le estremità aperte per l'accodamento e la rimozione degli elementi di dati.
Stack e coda sono le strutture dati utilizzate per la memorizzazione di elementi di dati e sono in realtà basate su alcuni equivalenti reali. Ad esempio, lo stack è una pila di CD in cui è possibile estrarre e inserire CD nella parte superiore della pila di CD. Allo stesso modo, la coda è una coda per i biglietti del teatro in cui la persona che si trova al primo posto, cioè davanti alla coda, verrà servita per prima e la nuova persona in arrivo apparirà nel retro della coda (coda della coda).
Grafico comparativo
| Base per il confronto | Pila | Coda |
|---|---|---|
| Principio di funzionamento | LIFO (Last in First Out) | FIFO (First in First Out) |
| Struttura | La stessa fine è usata per inserire ed eliminare elementi. | Un'estremità viene utilizzata per l'inserimento, ovvero la parte posteriore e un'altra estremità vengono utilizzate per la cancellazione di elementi, ad esempio il front end. |
| Numero di puntatori utilizzati | Uno | Due (in caso di coda semplice) |
| Operazioni eseguite | Spingi e fai pop | Accodare e desettare |
| Esame di condizioni vuote | Superiore == -1 | Anteriore == -1 || Anteriore == Posteriore + 1 |
| Esame della piena condizione | Superiore == Max - 1 | Posteriore == Max - 1 |
| varianti | Non ha varianti. | Ha varianti come coda circolare, coda di priorità, coda doppiamente terminata. |
| Implementazione | Più semplice | Comparativamente complesso |
Definizione di Stack
Una pila è una struttura di dati lineare non primitiva. È una lista ordinata in cui viene aggiunto il nuovo elemento e l'elemento esistente viene eliminato da una sola estremità, chiamato come la cima dello stack (TOS). Dato che tutta la cancellazione e l'inserimento in uno stack sono fatti dalla cima della pila, l'ultimo elemento aggiunto sarà il primo a essere rimosso dalla pila. Questo è il motivo per cui lo stack è chiamato tipo Last-in-First-out (LIFO).
Si noti che l'elemento a cui si accede spesso nello stack è l'elemento più in alto, mentre l'ultimo elemento disponibile si trova nella parte inferiore della pila.
Esempio
Alcuni di voi potrebbero mangiare biscotti (o poppins). Se si presume, viene strappato solo un lato della copertina e i biscotti vengono estratti uno alla volta. Questo è ciò che viene chiamato scoppiettante, e allo stesso modo, se vuoi conservare alcuni biscotti per un po 'di tempo dopo, li rimetterai nel pacchetto attraverso la stessa estremità strappata che si chiama spingendo.
Definizione di coda
Una coda è una struttura di dati lineare che rientra nella categoria del tipo non primitivo. È una raccolta di tipi di elementi simili. L'aggiunta di nuovi elementi avviene ad un'estremità chiamata retro-fine. Allo stesso modo, la cancellazione degli elementi esistenti avviene all'altra estremità chiamata Front-end, ed è logicamente un tipo di elenco First in first out (FIFO).
Esempio
Nella nostra vita quotidiana ci imbattiamo in molte situazioni in cui dobbiamo aspettare il servizio desiderato, dobbiamo quindi entrare in attesa per il nostro turno per ottenere assistenza. Questa coda di attesa può essere pensata come una coda.
Differenze chiave tra pila e coda
- Lo stack segue il meccanismo LIFO d'altra parte Queue segue il meccanismo FIFO per aggiungere e rimuovere elementi.
- In una pila, lo stesso fine viene usato per inserire ed eliminare gli elementi. Al contrario, nella coda si usano due estremità diverse per inserire ed eliminare gli elementi.
- Dato che Stack ha un solo estremo aperto è la ragione per usare solo un puntatore per riferirsi alla cima dello stack. Ma la coda usa due puntatori per fare riferimento alla parte anteriore e posteriore della coda.
- Stack esegue due operazioni note come push e pop mentre in Queue è noto come accodamento e rimozione.
- L'implementazione dello stack è più facile mentre l'implementazione della coda è complicata.
- La coda ha varianti come coda circolare, coda di priorità, coda doppiamente terminata, ecc. Al contrario, lo stack non ha varianti.
Implementazione dello stack
Lo stack può essere applicato in due modi:
- L'implementazione statica utilizza matrici per creare uno stack. L'implementazione statica è una tecnica semplice ma non flessibile, in quanto la dichiarazione della dimensione dello stack deve essere fatta durante la progettazione del programma, dopo di che non è possibile variare le dimensioni. Inoltre, l'implementazione statica non è molto efficiente per quanto riguarda l'utilizzo della memoria. Poiché una matrice (per l'implementazione dello stack) viene dichiarata prima dell'inizio dell'operazione (in fase di progettazione del programma). Ora se il numero di elementi da ordinare è molto meno nello stack, la memoria allocata staticamente sarà sprecata. D'altra parte, se vi è più numero di elementi da memorizzare nello stack, non possiamo essere in grado di modificare la dimensione della matrice per aumentare la sua capacità, in modo che possa accogliere nuovi elementi.
- L'implementazione dinamica viene anche chiamata rappresentazione elenco collegato e utilizza i puntatori per implementare il tipo di stack della struttura dati.
Implementazione della coda
La coda può essere implementata in due modi:
- Implementazione statica : se una coda viene implementata utilizzando gli array, il numero esatto di elementi che si desidera archiviare nella coda deve essere garantito in precedenza, poiché la dimensione dell'array deve essere dichiarata in fase di progettazione o prima dell'inizio dell'elaborazione. In questo caso, l'inizio dell'array diventerà il fronte della coda e l'ultima posizione dell'array agirà da retro della coda. La seguente relazione fornisce gli elementi interi presenti nella coda quando implementati usando gli array:
anteriore - posteriore + 1
Se "posteriore <frontale" allora non ci sarà nessun elemento in coda o in coda sarà sempre vuoto. - Implementazione dinamica : implementazione di code usando i puntatori, lo svantaggio principale è che un nodo in una rappresentazione collegata consuma più spazio di memoria di un elemento corrispondente nella rappresentazione dell'array. Poiché ci sono almeno due campi in ogni nodo uno per il campo dati e altro per memorizzare l'indirizzo del nodo successivo mentre nella rappresentazione collegata esiste solo il campo dati. Il merito di utilizzare la rappresentazione collegata diventa evidente quando è necessario inserire o eliminare un elemento nel mezzo di un gruppo di altri elementi.
Operazioni su Stack
Le operazioni di base che possono essere gestite nello stack sono le seguenti:
- PUSH : quando un nuovo elemento viene aggiunto all'inizio dello stack è noto come operazione PUSH. La spinta di un elemento nello stack richiama l'aggiunta dell'elemento, in quanto il nuovo elemento verrà inserito nella parte superiore. Dopo ogni operazione di spinta, la cima viene aumentata di uno. Se l'array è pieno e non è possibile aggiungere nuovi elementi, si chiama STACK-FULL condition o STACK OVERFLOW. FUNZIONAMENTO PUSH - funzione in C:
Considerando lo stack è dichiarato comeint stack [5], top = -1;void push(){int item;if (top < 4){printf ("Enter the number") ;scan ("%d", & item) ;top = top + 1;stack [top] = item;}else{printf (" Stack is full");}} - POP : quando un elemento viene eliminato dalla cima dello stack, è noto come operazione POP. Lo stack viene diminuito di uno, dopo ogni operazione pop. Se non ci sono elementi lasciati nello stack e viene eseguito il pop, questo si tradurrà in STACK UNDERFLOW condizione che significa che lo stack è vuoto. FUNZIONAMENTO POP - funzioni in C:
Considerando lo stack è dichiarato comeint stack [5], top = -1;void pop(){int item;if (top >= 4){item = stack [top];top = top - 1;printf ("Number deleted is = %d", item) ;}else{printf (" Stack is empty");}}
Operazioni su una coda
Le operazioni di base che possono essere eseguite in coda sono:
- Accodamento : per inserire un elemento in una coda. Funzione di esecuzione di un comando in C:
La coda è dichiarata comeint queue [5], Front = -1 and rear = -1;void add (){int item;if ( rear < 4){printf ("Enter the number") ;scan ("%d", & item) ;if (front == -1){front =0 ;rear =0 ;}else{rear = rear + 1;}queue [rear] = item ;}else{printf ("Queue is full") ;}} - Dequeue : per eliminare un elemento dalla coda. Funzione di esecuzione di un comando in C:
La coda è dichiarata comeint queue [5], Front = -1 and rear = -1;void delete (){int item;if ( front ! = -1){item = queue [ front ] ;if (front == rear){front =-1 ;rear =-1 ;}else{front = front + 1;printf ("Number deleted is = %d", item) ;}}else{printf ("Queue is empty") ;}}
Applicazioni di Stack
- Analisi in un compilatore.
- Macchina virtuale Java.
- Annulla in un word processor.
- Pulsante Indietro in un browser Web.
- Linguaggio PostScript per stampanti.
- Implementazione delle chiamate di funzione in un compilatore.
Applicazioni di coda
- Buffer di dati
- Trasferimento dati asincrono (file IO, pipe, socket).
- Assegnazione di richieste su una risorsa condivisa (stampante, processore).
- Analisi del traffico
- Determina il numero di cassieri da avere in un supermercato.
Conclusione
Stack e Queue sono strutture di dati lineari che differiscono in certi modi, come meccanismo di lavoro, struttura, implementazione, varianti, ma entrambi sono usati per memorizzare gli elementi nella lista ed eseguire operazioni sulla lista come aggiunta e cancellazione degli elementi. Sebbene ci siano alcune limitazioni della coda semplice che viene recuperata utilizzando altri tipi di coda.
