STIVA-implementata ca lista simplu inlantuita

stack-linked-list.c

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

/*
Laborator 3. STIVA (LIFO) implementata cu lista simplu inlantuita



Last In First out



farfurie3
farfurie2
farfurie1

FIFO este pentru coada First In First Out

 (4)(5)(7) ......>>> header
/ \
|||
Tail
*/

typedef struct _STACK_NODE {

        int key;
        struct _STACK_NODE *next;

} STACK_NODE;


typedef struct {

	  STACK_NODE *first; //varful stivei

} STACK;


/* INIT */

static STACK_NODE *stack_create_node(int value) {

	   STACK_NODE *node = NULL;

	   node = (STACK_NODE*)malloc(sizeof(STACK_NODE));

	   if(node == NULL) {
        
        fprintf(stderr, "%s\n", "Err: malloc failed!");   

	   	exit(EXIT_FAILURE);
	   }

	   memset(node, 0,  sizeof(STACK_NODE)); //next = NULL

	   node->key = value;

	   return node;
}

//pointer catre stack
void stack_init(STACK *s) {

	s->first = NULL; //stiva vida
}

bool stack_is_empty(const STACK *s) {

     return s->first == NULL;   
}

/*
SCOATE elementul din varful stivei si ii returneaza key O(1)
underflow: stiva goala -->afiseaza eroare -1 

D (varful stivel) | STACK_NODE *node = D //daca fac FREE
C
B
A

*/

int pop(STACK *s) {

      if(s->first == NULL) {
      	fprintf(stderr, "Err: underflow - stiva este goala!\n");
      	return -1;
      }

      //declaram un pointer catre stack_node
      STACK_NODE *node = s->first;//luam adresa varfului stivei in pointerul node catre Stack_NODE

      int key = node->key;

      s->first = node->next; //link pentru a deveni varful stivei

      free( node );//eliberez spatiul din HEAP pentru varful stivei

      node = NULL;

      return key;
}

/* returneaza varful stivei FARA sa-l stearga (top) */
/*

node5(key) top , varful stivei | s->first se refera la varful stivei
node4(key)
node3(key)
node2(key)
node1(key)
*/

int top(const STACK *s) {

	if(s->first == NULL) {
		fprintf(stderr, "Err: stiva este goala!"); 
		return -1;
	}  
	return s->first->key;//returnam key din varful stivei.
}

/* ELiberare spatiu din HEAP pentru stiva */
/*

//item3 (varful stivei) adica s->first 


item2 varful stivei



item1  varful stivei

s->first = NULL
*/

void stack_clear(STACK *s) {

	while( s->first != NULL ) pop( s );
}

/*________________AFISARE ________________*/

void stack_print(const STACK *s) {

      if(s->first == NULL) {
      	printf("STIVA ESTE GOALA! {}\n");
      	return;
      }

      printf("VARF -> ");

      for(STACK_NODE *c = s->first; c != NULL; c = c->next) {

      	 printf("%d", c->key);

      	 if(c->next) printf(" -> ");
      }

      printf(" -> NULL\n");
}


/*--------------Operatii fundamentale-----------------*/

//....Node2->Node1 -->(NULL)
//adauga un element in varful stivei (insert_first) O(1) 
void push(STACK *s, int key) {

	STACK_NODE *node = stack_create_node( key );

	node->next = s->first;

	s->first = node;
}

int main(int argc, char const *argv[])
{

	 STACK s;

	 stack_init( &s );

     printf("STIVA initiala!\n");
	 stack_print(&s);

	 push(&s, 4);
	 push(&s, 17);
	 push(&s, 2);
	 push(&s, 7);
	 push(&s, 5);

	 printf("\n Dupa push (4, 17, 2, 7, 5): \n");
	 stack_print(&s);

	 printf("\nTOP = %d\n", top(&s)); //5 , nu STERGE
	 stack_print(&s);

	 printf("\npop() = %d\n", pop(&s)); /* 5 */
	 printf("\npop() = %d\n", pop(&s)); /* 7 */

	 push(&s, 14);
	 printf("\nLIFO: Dupa push(14):\n");
	 stack_print(&s);

	 //GOLIRE STIVA
	 stack_clear(&s);
	 printf("\nDupa golire: \n");
	 stack_print(&s);

	 printf("\nTEST underflow:\n");
	 pop(&s);
	
	return 0;
}