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

	#define EMPTY 'E'

	typedef struct node {
		char c;
		struct node *next;
	} node;

	typedef struct stack {
		struct node *top;
	} stack;

	// Function Prototypes
	stack *createStack();
	node *createNode(char c);
	int isEmpty(stack *s);
	int push(stack *s, char c);
	char pop(stack *s);
	char peek(stack *s);
	void clearStack(stack *s);
	void printStack(stack *s);
	void printChar(char c);
	void printOptions();

	// Initializes new stack
	stack *createStack() {
		stack *s = (stack *)malloc(sizeof(stack));
		s->top = NULL;
		return s;
	}

	// Initializes new node
	node *createNode(char c) {
		node *n = (node *)malloc(sizeof(node));
		n->c = c;
		n->next = NULL;
		return n;
	}

	// Returns 1 if stack is NULL or empty, otherwise returns 0
	int isEmpty(stack *s) { return (!s || !(s->top)); }

	// Creates new node with provided character and appends to top of stack
	// Returns 0 if stack was NULL, otherwise returns 1
	int push(stack *s, char c) {
		if (!s)
			return 0;

		node *n = createNode(c);

		n->next = s->top; // NOTE: If s->top is NULL, still works
		s->top = n;
		return 1;
	}

	// Returns/ removes top character from stack
	// If stack is NULL or empty, returns EMPTY
	char pop(stack *s) {
		if (!s || !(s->top))
			return EMPTY;

		char c = s->top->c;
		node *tmp = s->top;
		s->top = s->top->next;
		free(tmp);

		return c;
	}

	// Returns - WITHOUT removing - top character from stack
	// If stack is NULL or empty, returns EMPTY
	char peek(stack *s) { return (isEmpty(s)) ? EMPTY : s->top->c; }

	// Empty all elements in stack
	void clearStack(stack *s) {
		while (!isEmpty(s))
			pop(s);
	}

	// Prints stack to screen
	void printStack(stack *s) {
		if (isEmpty(s)) {
			printf("Stack is empty\n");
			return;
		}
		printf("(top)\n");
		node *walker = s->top;
		while (walker) {
			printf("%c\n", walker->c);
			walker = walker->next;
		}
		printf("(bottom)\n");
	}

	// Print character
	void printChar(char c) {
		if (c == EMPTY)
			printf("EMPTY\n");
		else
			printf("%c\n", c);
	}

	// Print options menu
	void printOptions() {
		printf("1) Push\n");
		printf("2) Pop\n");
		printf("3) Peek\n");
		printf("4) Print Stack\n");
		printf("5) Clear Stack\n");
		printf("6) Quit\n");
		printf("\n:");
	}

	int main(void) {
		stack *s = createStack();

		int choice = 0;
		char c;

		while (choice != 6) {
			printOptions();
			scanf("%d", &choice);

			switch (choice) {

			case 1: // Push
				printf("Type a lowercase letter to add to stack:\n");
				scanf(" %c", &c);
				if (push(s, c))
					printf("%c added to stack\n", c);
				else
					printf("Failed to add %c to stack\n", c);
				break;

			case 2: // Pop
				c = pop(s);
				printf("Popped: ");
				printChar(c);
				break;

			case 3: // Peek
				c = peek(s);
				printf("Peeked: ");
				printChar(c);
				break;

			case 4: // Print Stack
				printStack(s);
				break;

			case 5: // Clear Stack
				clearStack(s);
				printf("Stack is now empty\n");
				break;

			default:
				break;
			}
			printf("\n");
		}

		// Free Memory
		clearStack(s);
		free(s);

		return 0;
	}