#include <stdio.h>
#include <stdlib.h>
#include <time.h>  // use time() to get current time

#define SIZE 100

typedef struct {
    int data[SIZE];
    int top;
} Stack;

void init_stack(Stack *s) {
    s->top = -1;
}

// Stack functions
int full(Stack *s) {
    return s->top == SIZE - 1;
}

int empty(Stack *s) {
    return s->top == -1;
}

void push(Stack *s, int val) {
    if(!full(s))
        s->data[++(s->top)] = val;
    else {
        printf("Stack is full!");
        exit(1);
    }
}

int pop(Stack *s) {
    if(!empty(s))
        return s->data[(s->top)--];
    printf("Stack is empty!");
    exit(2);
}

// Questions
void random_number_generator(Stack* s, int range, int offset, int len) {
    srand(time(NULL));          // use srand(time(NULL)) to set seed of random number generator as current time
    int i;
    for(i = 0; i < len; i++)
        push(s, rand() % range + offset);  // generate random number
}

void print_stack(Stack* ele_s, int ElementsInOneLine) {
    Stack temp_popped;
    init_stack(&temp_popped);
    int ElementsInCurrentLine = 0;
    
    while(!empty(ele_s)) {
        int popped_value = pop(ele_s);
        printf("%d ", popped_value);  // remove '\n' if output is too long
        push(&temp_popped, popped_value);
        if(++ElementsInCurrentLine >= ElementsInOneLine) {
            printf("\n");
            ElementsInCurrentLine = 0;
        }
    }
    while(!empty(&temp_popped)) {
        int popped_value = pop(&temp_popped);
        push(ele_s, popped_value);
    }
    printf("\n");
}

void restore(Stack *ele_s, Stack *temp_s) {
    while(!empty(temp_s)) {
        push(ele_s, pop(temp_s));
    }
}

void reverseStack(Stack *s) {
    // base case
    if(empty(s))
        return;
    // store front(first element) of queue, and remove front
    int top = pop(s);
 
    // asking recursion to reverse the leftover queue
    reverseStack(s);
 
    // placing first element at its correct position
    push(s, top);
}

int getElement(Stack *s, int fromTop, int n) {    // 1 is fromTop, 0 is fromBottom
    Stack temp_popped;
    init_stack(&temp_popped);
    int i, popped_value;
    
    if(fromTop == 1) {
        for(i = 0; i < n; i++) {
            popped_value = pop(s);
            push(&temp_popped, popped_value);
        }
        restore(s, &temp_popped);
    } else {
        Stack reversed_ele_s;
        Stack popped_reverse;
        init_stack(&reversed_ele_s);
        init_stack(&popped_reverse);

        // reverse ele_s and get value from the top n-th element
        while(!empty(s)) {
            push(&reversed_ele_s, pop(s));
        }
        for(i = 0; i < n; i++) {
            popped_value = pop(&reversed_ele_s);
            push(&temp_popped, popped_value);
        }

        // reverse temp_popped and restore (beacuse ele_s was reversed)
        while(!empty(&temp_popped)) {
            push(&popped_reverse, pop(&temp_popped));
        }
        restore(s, &popped_reverse);
        restore(s, &reversed_ele_s);
    }
    return popped_value;
}


int main() {
    Stack s;
    init_stack(&s);

    // p1
    random_number_generator(&s, 100, 1, 6);  // Use rand()%100+1 to get 6 random numbers
    print_stack(&s, 6);    // 6 numbers in one line

    // p2 element out of size
    // int x = getElement(&s, 1, 11);
    // printf("%d \n", x);

    // p3
    random_number_generator(&s, 100, 1, 21);  // Use rand()%100+1 to get 21 random numbers
    print_stack(&s, 7);    // 7 numbers in one line
    printf("\n");

    // p4
    int y = getElement(&s, 1, 11);
    printf("%d \n\n", y);

    // p5
    int z = getElement(&s, 0, 2);
    printf("%d \n\n", z);

    // p6
    int w = getElement(&s, 0, 3);
    printf("%d \n\n", w);

    // p7
    print_stack(&s, 7);    // 7 numbers in one line
    
    return 0;
}