/* 
* Code example for CP264 Data Structures II
* linked list stack
* HBF 
*/
#include <stdio.h>
#include <malloc.h>

typedef struct node {
  int data;
  struct node *next;
} snode;

void push(snode **topp, int);
void pop(snode **topp);    // pop and free the top element
int peek(snode *top);      // get the data of the top element
snode *pop1(snode **topp); // pop and return the top element (not free) 
void pop2(snode **topp, snode**); // pop and pass out the pointer of old top element (not free)
void display_stack(snode *top); // display from top to the bottom. 

int main() {
  snode *top = NULL;
  printf("push:\n");
  push(&top, 1);
  push(&top, 2);
  push(&top, 3);
  push(&top, 4);  
  printf("display:\n");
  display_stack(top);
  printf("\npeek:%d\n", peek(top));
  printf("pop\n");
  pop(&top);
  printf("display:\n");
  display_stack(top);
  
  snode *snp = pop1(&top);
  printf("pop1 %d\n", snp->data);
  free(snp);
  printf("display:\n");
  display_stack(top);
  
  pop2(&top, &snp);
  printf("pop2 %d\n", snp->data);
  free(snp);
  printf("display:\n");
  display_stack(top);
  
  return 0;
}

void push(snode **topp, int val) {
  snode *ptr = (snode*) malloc(sizeof(snode));
  ptr->data = val;
  if (*topp == NULL) {
    ptr->next = NULL;
    *topp = ptr;
  } else {
    ptr->next = *topp;
    *topp = ptr;
  }
}

void pop(snode **topp) {
  if (*topp == NULL)
    printf("\nUNDERFLOW");
  else {
    snode *temp = *topp;
    *topp = temp->next;
    free(temp);
  }
}

snode *pop1(snode **topp) {
  if (*topp == NULL)
    return NULL;
  else {
    snode *np = *topp;
    *topp = np->next;
    return np;
  }
}

void pop2(snode **topp, snode **npp) {
  if (*topp == NULL)
    *npp = NULL;
  else {
    snode *np = *topp;
    *topp = np->next;
    *npp = np;
  }
}

int peek(snode *top) {
  if (top == NULL) {
    printf("\nEMPTY");
    return -1;
  }  
  else
    return top->data;
}

void display_stack(snode *top) {
  snode *p = top;
  if ( p == NULL)
    printf("\nEMPTY");
  else {
    while (p != NULL) {
      printf("%d\n", p->data);
      p = p->next;
    }
  }
}

/*
push:
display:
4
3
2
1

peek:4
pop
display:
3
2
1
pop1 3
display:
2
1
pop2 2
display:
1
*/