/*
 * example: backtracking/reverse the order of linear data structure by stack 
 * HBF
*/
#include <stdio.h>
#define MAX 10

void push(int stack[], int *top, int val);
void pop(int stack[], int *top);
int  peek(int stack[], int top);

int main() {
  int stack[MAX], top = -1;
  int a[10]={1,2,3,4,5}, n=5, i;
  int b[10];
  
  printf("array:\n");
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }

  printf("\ntraversal and remember:\n");
  for (i = 0; i < n; i++) {
    push(stack, &top, a[i]);
  }

  printf("backtracking:\n");
  for(i=0; i < n; i++) {
    b[i] = peek(stack, top);
    printf("%d ", b[i]);
    pop(stack, &top);
  }
  
  printf("\narray in reverse order:\n");
  for (i = 0; i < n; i++) {
    printf("%d ", b[i]);
  }

  return 0;
}

void push(int stack[], int *top, int val) {
  if (*top == MAX-1) {
    printf("\n STACK OVERFLOW");
  } else {
    *top = *top + 1;
    stack[*top] = val;
  }
}

void pop(int stack[], int *top) {
  if (*top == -1) {
    printf("\n STACK UNDERFLOW");
  } else {
    *top = *top - 1;
  }
}

int peek(int stack[], int top) {
  if (top == -1) {
    printf("\n STACK IS EMPTY");
    return -1;
  } else
    return (stack[top]);
}

/*
array:
1 2 3 4 5
traversal and remember:
backtracking:
5 4 3 2 1
array in reverse order:
5 4 3 2 1
*/