Struttura dei dati e algoritmi - Stack

Uno stack è un tipo di dati astratto (ADT), comunemente utilizzato nella maggior parte dei linguaggi di programmazione. Si chiama pila poiché si comporta come una pila del mondo reale, ad esempio: un mazzo di carte o una pila di piatti, ecc.

Uno stack del mondo reale consente operazioni solo a un'estremità. Ad esempio, possiamo posizionare o rimuovere una carta o un piatto solo dalla parte superiore della pila. Allo stesso modo, Stack ADT consente tutte le operazioni sui dati solo a un'estremità. In qualsiasi momento, possiamo accedere solo all'elemento superiore di uno stack.

Questa caratteristica rende la struttura dati LIFO. LIFO sta per Last-in-first-out. Qui si accede per primo all'elemento che è stato posizionato (inserito o aggiunto) per ultimo. Nella terminologia dello stack, viene chiamata l'operazione di inserimentoPUSH viene chiamata l'operazione di operazione e rimozione POP operazione.

Rappresentazione in pila

Il diagramma seguente illustra uno stack e le sue operazioni:

Uno stack può essere implementato mediante Array, Structure, Pointer e Linked List. Lo stack può essere di dimensioni fisse o può avere un senso di ridimensionamento dinamico. Qui, implementeremo lo stack utilizzando gli array, il che lo rende un'implementazione dello stack di dimensioni fisse.

Operazioni di base

Le operazioni sullo stack possono comportare l'inizializzazione dello stack, il suo utilizzo e quindi la de-inizializzazione. Oltre a questi elementi di base, uno stack viene utilizzato per le seguenti due operazioni principali:

• push() - Spingere (immagazzinare) un elemento sullo stack.

• pop() - Rimozione (accesso) di un elemento dalla pila.

Quando i dati vengono inseriti nello stack.

Per utilizzare uno stack in modo efficiente, dobbiamo controllare anche lo stato dello stack. Per lo stesso scopo, la seguente funzionalità viene aggiunta agli stack:

• peek() - ottenere l'elemento dati superiore dello stack, senza rimuoverlo.

• isFull() - controlla se lo stack è pieno.

• isEmpty() - controlla se lo stack è vuoto.

In ogni momento, manteniamo un puntatore agli ultimi dati PUSH nello stack. Poiché questo puntatore rappresenta sempre la parte superiore dello stack, da qui denominatotop. Iltop il puntatore fornisce il valore superiore dello stack senza rimuoverlo effettivamente.

Per prima cosa dovremmo conoscere le procedure per supportare le funzioni dello stack -

sbirciare()

Algoritmo della funzione peek () -

begin procedure peek
   return stack[top]
end procedure

Implementazione della funzione peek () nel linguaggio di programmazione C -

Example

int peek() {
   return stack[top];
}

è pieno()

Algoritmo della funzione isfull () -

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

Implementazione della funzione isfull () nel linguaggio di programmazione C -

Example

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

è vuoto()

Algoritmo della funzione isempty () -

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif
   
end procedure

L'implementazione della funzione isempty () nel linguaggio di programmazione C è leggermente diversa. Inizializziamo top a -1, poiché l'indice nell'array inizia da 0. Quindi controlliamo se il top è sotto zero o -1 per determinare se lo stack è vuoto. Ecco il codice -

Example

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

Operazione push

Il processo di inserimento di un nuovo elemento di dati nello stack è noto come operazione push. L'operazione push prevede una serie di passaggi:

• Step 1 - Controlla se la pila è piena.

• Step 2 - Se lo stack è pieno, produce un errore ed esce.

• Step 3 - Se la pila non è piena, aumenta top per indicare il prossimo spazio vuoto.

• Step 4 - Aggiunge un elemento di dati alla posizione dello stack, dove punta in alto.

• Step 5 - Restituisce il successo.

Se l'elenco collegato viene utilizzato per implementare lo stack, nel passaggio 3 è necessario allocare lo spazio in modo dinamico.

Algoritmo per l'operazione PUSH

Un semplice algoritmo per l'operazione Push può essere derivato come segue:

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data

end procedure

L'implementazione di questo algoritmo in C è molto semplice. Vedere il codice seguente -

Example

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

Operazione Pop

L'accesso al contenuto mentre lo si rimuove dallo stack è noto come operazione Pop. In un'implementazione di matrice dell'operazione pop (), l'elemento data non viene effettivamente rimosso, invecetopviene decrementato in una posizione inferiore nella pila per puntare al valore successivo. Ma nell'implementazione dell'elenco collegato, pop () rimuove effettivamente l'elemento dati e rilascia lo spazio di memoria.

Un'operazione Pop può comportare i seguenti passaggi:

• Step 1 - Controlla se la pila è vuota.

• Step 2 - Se lo stack è vuoto, produce un errore ed esce.

• Step 3 - Se lo stack non è vuoto, accede all'elemento di dati in cui top sta indicando.

• Step 4 - Diminuisce il valore di top di 1.

• Step 5 - Restituisce il successo.

Algoritmo per l'operazione Pop

Un semplice algoritmo per l'operazione Pop può essere derivato come segue:

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

L'implementazione di questo algoritmo in C è la seguente:

Example

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

Per un programma stack completo in linguaggio di programmazione C, fare clic qui .