Implementazione dello stack in C

Possiamo implementare la struttura dei dati attraverso la lingua C. Esistono diversi tipi di struttura dei dati disponibili per archiviare e accedere ai dati in modo efficiente. Stack è uno di questi.

Uno stack è una versione modificata di array. Possiamo aggiungere o rimuovere un elemento all'estremità dello stack. Questa fine è al Superiore dello stack.

Stack è un modo specializzato per gestire, archiviare, inserire, eliminare, accedere ai dati. È astratto nella natura.

Array e stack

1. C'è un po 'di differenza tra l'array e lo stack in termini di accessibilità. Possiamo accedere a qualsiasi elemento dall'array in qualsiasi condizione, ma nel caso dello stack, possiamo inserire o eliminare l'elemento da un'estremità uno per uno. Questa fine si chiama top. In termini di accessibilità, l'array è più veloce dello stack.
2. Stack ha due funzioni principali chiamate push and pop.
3. La funzione push viene utilizzata per inserire in uno stack e la funzione pop viene utilizzata per rimuovere un elemento dallo stack.

Rappresentazione

Possiamo accedere solo all'ultimo elemento inserito in stack. Questa è la parte superiore dello stack. Possiamo inserire o rimuovere dall'alto.

Questo è noto come l'ultimo in Fast Out (LIFO) e The Fast in Last Out (FILO).

Implementazione

Lo stack può essere implementato come segue:

-> Array -> Array dinamico -> Elenco collegamenti

Operazione

-> Push -> pop

Algoritmo Push: Push (Stack, Top, Maxstk, Articolo)

1. [Lo stack è pieno]

Se top == maxstk

Mostra messaggio: Traboccare e tornare

2. Imposta top = top + 1
3. Imposta Stack [Top] = Item
4. Ritorno

Algoritmo Pop: Pop (stack, top, oggetto)

1. [Elemento rimosso dallo stack]

Se top == -1

Mostra il messaggio: Underflow and Return

2. Imposta elemento = stack [top]
3. Top: top -1
4. Ritorno

Stack usando l'array

Struct Arraystack

int top;
capacità non firmata;
int *array;

Qui, definiamo un tipo di dati definito dall'utente chiamato ArrayStack. Ha tre membri di dati denominati Top, Capacity e un puntatore chiamato *Array.

Notazione polacca

La notazione polacca sta scrivendo gli operatori di un'espressione prima o dopo il loro operand.

Modi di scrivere:

Infisso 2. Prefisso 3. Postfix

Infisso

Gli operatori sono mantenuti tra i due operandi.

Esempio: A + B

Prefisso

Gli operatori sono conservati prima dei loro operandi.

Esempio: + A B

Postfix

Gli operatori sono tenuti dopo i loro operandi.

Esempio: A B +

Convertire

1.

Infisso:
(A + b) * c
Prefisso:
* + A b c
Postfix:
A B + C *

2.

Infisso:
A + (B * C)
Prefisso:
+ A * b c
Postfix:
A B C * +

3.

Infix :( a + b) / (c - d)
Prefisso:/ + a b - c d
Postfix: A B + C D - /

Tutta questa conversione può essere eseguita usando lo stack. Ora, vogliamo mostrare come creare uno stack e come vengono inseriti l'elemento o i dati. Gli elementi possono essere rimossi dallo stack attraverso la programmazione.

Esempio di programmazione

#includere
#includere
INT ITM;
struct arraystack // definisce un tipo di dati;

int top;
capacità int;
int *array;
;
struct arraystack *createstack (int cap) // crea uno stack;

Struct ArrayStack *stack;
stack = malloc (sizeof (struct arraystack));
stack-> top = - 1;
stack-> capacità = cap;
stack-> array = malloc (sizeof (int) * stack-> capacità);
restituire (stack);

Int full (struct arraystack *stack) // Il controllo dello stack è pieno o no.

if (stack-> top == stack-> capacità-1)
restituzione (1);
altro
restituzione (0);

int vuoto (Struct ArrayStack *Stack) // Controllare lo stack è vuoto o no.

if (stack-> top == -1)
restituzione (1);
altro
restituzione (0);

void push (struct arraystack *stack, int oggetto) // inserisci elementi nello stack;

Se ( !completo (stack))

stack-> top ++;
stack-> array [stack-> top] = articolo;


int pop (struct arraystack *stack) // Rimuovi gli elementi dallo stack;

Se ( !vuoto (stack))

Item = stack-> array [stack-> top];
stack-> top--;
restituire (articolo);

restituzione (-1);

int main ()

INT Choice;
Struct ArrayStack *stack;
stack = createstack (4);
mentre (1)

printf ("\ n 1 . spingere " ) ;
printf ("\ n 2 . pop ");
printf ("\ n 3 . uscita \ n ");
printf ("Inserisci la tua scelta \ n");
scanf ("%d", e scelta);
Switch (scelta)

caso 1:
printf ("immettere un numero \ n");
scanf (" %d", & articolo);
push (stack, oggetto);
rottura ;
Caso 2:
Item = pop (stack);
if (item == - 1)
printf ("stack è vuoto");
altro
printf ("Valore popped è %d", articolo);
rottura ;
Caso 3:
uscita (0);


restituzione 0;

Produzione:

Spiegazione

Come abbiamo detto in precedenza, definiamo un tipo di dati definito dall'utente chiamato ArrayStack. Ha tre membri di dati denominati Top, Capacity e un array di punta. Quindi, definiamo una funzione denominata createstack in cui passiamo un valore che viene creato il blocco totale di array. La funzione Malloc () crea questo array e restituisce l'indirizzo allo stack variabile che è il tipo ArrayStack. L'array stack-> contiene l'indirizzo dell'array creato dalla funzione Malloc ().

Successivamente, definiamo un'altra funzione denominata full () per verificare se lo stack è pieno o no.

Crea un'altra funzione denominata per verificare se lo stack è vuoto.

Quindi, definiamo un'altra funzione denominata push () in cui inseriamo gli elementi uno per uno nello stack da un'estremità chiamata TOP. Per inserire l'elemento nello stack, controlliamo prima se lo stack è pieno.

Quindi, definiamo un'altra funzione denominata pop () in cui eliminiamo gli elementi uno per uno dallo stack da un'estremità chiamata top. Per rimuovere l'elemento nello stack, controlliamo prima se lo stack è vuoto.

Quindi, all'interno della funzione principale (), scriviamo la custodia Switch per offrire all'utente un'opzione di menu per selezionare la sua scelta se l'elemento viene inserito o eliminato nello stack.

Conclusione

Dalla discussione sullo stack, siamo giunti a raggiungere questa conclusione che lo stack è una struttura di dati ben definita che viene utilizzata per gestire i dati in modo strutturale. Il nostro stack della vita quotidiana è implementato in vari campi per archiviare, inserire o eliminare elementi.