Structuri de date – Stiva (LIFO – Last In First Out)

O stivă (în engleză stack) este o structură de tip LIFO (Last In First Out = ultimul intrat primul ieşit) şi este un caz particular al listei liniare în care toate inserările (depunerile -în engleză push) şi ştergerile (sau extragerile -în engleză pop) (în general orice acces) sunt făcute la unul din capetele listei, numit vârful stivei. Acest nod poate fi citit, poate fi şters sau în faţa lui se poate insera un nou nod care devine cap de stivă.

Implementarea unei structuri de date de tip stivă utilizând un tablou unidimensional se poate face astfel:

#include "stdio.h"
#include "stdlib.h"
#define STCKSIZE 50
//prototipul funcţiei de depunere în stivă
void push(int i);
//prototipul funcţiei de extragere din stivă
int pop(void);
//variabile globale; în tabloul stack simulăm stiva
int *pi, *tos, stack[STCKSIZE];

void main(void)
{
  int value;
  pi=stack;
  tos=pi;
  do
  {
    printf(" Introduceţi un nr pozitiv pentru depunere, -1 pt ieşire si o pt o extragere:");
    scanf("%d",&value);
    if(value)
      push(value);
    else
      printf("Am extras elementul: 96d\n",pop());
    }
    while (value !=-i);
}

void push(int i)
{
  p1++;
  if(p1==(tos+STCKSIZE))
  {
    printf("Stiva plina!");
    exit(i);
  }
  //depunem în stivă elementul 1
  *p1=i;
}

int pop(void)
{
  if(pi==tos)
{
    printf("Stiva vida! \n");
    exit(1);
}
  pi--;
  //returnăm elementul curent (înainte de decrementarea pointerului pl)
  return(*(p+i));
}

Implementarea unei stive utilizând o structură dinamică (listă simplu înlănţuită folosind pointeri):

#include "stdio.h"
#include "stdlib.h"

struct stack
{
  int info;
  stack* urm;
};

typedef stack* nod;
//v conţine vârful stivei (adresa ultimului nod introdus),
//respectiv o dacă stiva este vidă
nod v;
int n;

//funcţia de adăugare in stivă
void push(int n)
{
  //c pointer ce conţine adresa noului nod introdus
  nod c;
  if(!v)
  {
    v=(nod)malloc(sizeof(stack));
    v->info=n;
    v->urm=o;
  }
  else
  {
    c=(nod)malloc(sizeof(stack));
    c->info=n;
    //legăm noul vârf al stivei de următorul element (fostul vârf)
    c->urm=v;
    //v va indica în continuare noul vârf al stivei
    v=c;
  }
}

//funcţia de extragere a unui element din stivă
void pop(void)
{
  //c va reţine adresa nodului extras
  nod c;
  if(!v)
    printf("Stiva este vida\n");
  else
  {
  c=v;
  printf("Am extras elementul: %d\n",c->info);
  //noul vârf al stivei
  v=v->urm;
  free(c);
  }
}

//funcţia de afişare a stivei
void traversare(void)
{
  //pointerul c este iniţializat cu adresa vârfului stivei
  nod c=v;
  printf( "Traversam stiva:");
  if (!c)
    printf("Stiva este goala !\n");
    //atât timp cât c este diferit de o deci nu am ajuns la ultimul element al stivei
    while (c)
      {
      printf("%d ",c->info);
      //continuăm cu următorul element al stivei
      c=c->urm;
      }
  printf(“\n\n”);
}

void main(void)
{
  do
  {
    printf("Introduceti elementul (-1 pentru extragere element, 0 pentru ieşire):");
    scanf("%d",&n);
    if(n)
      if (n!=(-1))
      {
        push(n);
        traversare();
      }
    else
      {
        pop();
        traversare();
      }
  } while (n); //ieşim când n=0
}

Leave a Reply

Your email address will not be published. Required fields are marked *

6 + three =

Time limit is exhausted. Please reload CAPTCHA.