#include <stdio.h>
#include <stdlib.h>

/* Stack implementerad som länkad lista */

/* Typdeklarationer */

struct Node
{
  int data;
  struct Node *next;
};

typedef struct Node Node;

typedef struct
{
  Node *top;
}Stack;

/* prototyper */

Stack* createStack(void);
void push(Stack *s, int data);
int pop(Stack *s);
int empty(Stack *s);
int top(Stack* s);
int size(Stack* s);


/* Skapa en stack, returnera en pekare till den */
Stack* createStack(void)
{
  Stack *s = malloc(sizeof(Stack));
  s->top = NULL;

  return s;
}

/* Lägg ett element på stacken */
void push(Stack *s, int d)
{
  Node *temp;

  temp = malloc(sizeof(Node));	/* skapa en ny nod */
  temp->next = s->top;           /* länka in den överst */
  temp->data = d;

  s->top = temp;
}

/* Returnera true om stacken är tom */
int empty(Stack *s)
{
  return (s->top == NULL);
}

/* returnera, och ta bort, översta värdet på stacken.
	Om den är tom, returnera 0 */
int pop(Stack *s)
{
  int temp; 
  Node *p = s->top;
  if (empty(s)) return 0; 		/* vad göra ? */
  
  temp = s->top->data;        /* kom ihåg datat */
  s->top = s->top->next;      /* länka ur noden */
  free(p);                    /* och ta bort den */
  
  return temp;
}

/* returnera översta värdet på stacken */
int top(Stack *s)
{
  return s->top->data;
}


/* returnera antal element på stacken, iterativ funktion */
int size(Stack *s)
{
  int n = 0;
  Node *p = s->top; 
  
  while (p != NULL)
  {
    p = p->next;
    n++;
  }
  return n;
}


/* Returnera antal element på stacken, rekursiv funktion */
int rsize(Node *n)
{
  if (n == NULL) return 0;          /* basfall, vi har nått botten */
  return rsize(n->next) + 1;        /* storleken på resten av stacken */
}

int size2(Stack *s)
{
  return rsize(s->top);
}

int main(void)
{
  Stack *stack;

  stack = createStack();
  push(stack, 4);
  push(stack, 5);
  push(stack, 6);
  /* observera utskriften här ! Varför blir det så ? */
  printf("size = %d, data = %d, size = %d\n", size(stack), pop(stack), size(stack));
  printf("size = %d\n", size(stack));
  printf("rsize = %d\n", size2(stack));
  printf("%d, size = %d\n", pop(stack), size(stack));
  printf("%d, size = %d\n", pop(stack), size(stack));
  printf("%d, size = %d\n", pop(stack), size(stack));
  printf("%d, rsize = %d\n", pop(stack), size2(stack));

  return 0;
}