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

#define MAX_LENGTH 500

/* РЕАЛИЗАЦИЯ СТЕКА НА ОСНОВЕ СПИСКА */

// Node of the list <=> element of stack
typedef struct Node {
    char data;  // in this case we save char symb
    struct Node *next;
}Node;

// Stack struct, saving top element
typedef struct Stack {
    struct Node* topElem;
}Stack;

// Initialization
void initStack(Stack* stack) {
    stack->topElem = (Node*)malloc(1 * sizeof(Node));
    stack->topElem = NULL;
}

// Checking for empty
int isEmpty(Stack* stack) {
    return stack->topElem == NULL;
}

/*
To push an element into the stack, we create a new node,
and point the stack pointer to the new node.
*/
void push(Stack* stack, char data) {
    Node* tmp = (Node*)malloc(1 * sizeof(Node));
    if(!tmp) {
        printf("Can't push!\n");
        return;
    }
    tmp->data = data;
    tmp->next = stack->topElem; // making last top element next for new top element
    stack->topElem = tmp;  // making new top element
}

/*
To pop an element from the stack,
we need to get the data of the element,
point the stack pointer to the next element and remove it
*/
char pop(Stack* stack) {
    Node* tmp = stack->topElem;
    char del_data = stack->topElem->data;
    stack->topElem = stack->topElem->next;
    free(tmp);
    return del_data;
}

// Getting value of top element
char top(struct Stack* stack) {
    return stack->topElem->data;
}

/*
To display the stack content,
we traverse the stack elements from the first element to NULL
*/
void display(Stack* stack) {
    Node* current;
    current = stack->topElem;
    if(current) {
        printf("Stack: ");
        do {
            printf("%c ", current->data);
            current = current->next;
        } while (current);
        printf("\n");
    }else {
        printf("The Stack is empty!\n");
    }
}

// Get quantity of elements in stack
int count(Stack* stack) {
    int quant = 0;
    Node* current;
    current = stack->topElem;
    if(current) {
        do {
            quant++;
            current = current->next;
        } while (current);
    }else {
        printf("The Stack is empty!\n");
    }
    return quant;
}

int main() {
    clock_t begin = clock();

    Stack* stack = (Stack*)malloc(1 * sizeof(Stack));
    initStack(stack);

    clock_t end = clock();
    // CLOCKS_PER_SEC is the number of clocks per second, so dividing by CLOCKS_PER_SEC yields a time in seconds
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    printf("Время на инициализацию списка: %fl секунд\n", time_spent);

    begin = clock();

    for (int i = 0; i < 1000000; i++) {
        push(stack, i);
    }

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("Время на добавление в список 1000000 элементов: %lf секунд\n", time_spent);

    begin = clock();

    for (int i = 0; i < 1000000; i++) {
        pop(stack);
    }

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("Время на удаление из списка 1000000 элементов: %lf секунд\n", time_spent);

    return 0;
}