Comprehensive Data Structures and Algorithms in C

Posted on Jan 11, 2025 in Computer Engineering in Computer Engineering

1. Binary Search

Binary Search Using Recursion

#include <stdio.h>
int binser(int [], int low, int high, int key); // declaration
int main() {
    int n;
    printf("Enter array size: ");
    scanf("%d", &n);
    int arr[n];
    printf("Enter array in sorted order:\n");
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    int key;
    printf("Enter element to search: ");
    scanf("%d", &key);
    int found = binser(arr, 0, n - 1, key);
    if(found == -1) {
        printf("\nElement not found");
    } else {
        printf("Element present at %d", found);
    }
    return 0;
}
int binser(int arr[], int low, int high, int key) { // definition
    if(low <= high) {
        int mid = (low + high) / 2;
        int pivot = arr[mid];
        if(key == pivot) {
            return mid;
        } else if(key > pivot) {
            return binser(arr, mid + 1, high, key);
        } else {
            return binser(arr, low, mid - 1, key);
        }
    }
    return -1;
}

2. Binary Tree – Array

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

void insert(int tree[], int size, int element) {
    int pos = 0;
    while (pos < size) {
        if (tree[pos]) {
            if (tree[pos] < element)
                pos = 2 * pos + 2;  // right
            else if (tree[pos] && tree[pos] > element)
                pos = 2 * pos + 1;  // left
        } else {
            tree[pos] = element;
            return;
        }
    }
}

void print(int tree[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", tree[i]);
    printf("\n");
}

int main() {
    int tree[100] = {0};
    int tsize = 100;
    // print first 20 elements
    print(tree, 20);
    insert(tree, tsize, 2);
    insert(tree, tsize, 3);
    insert(tree, tsize, 5);
    insert(tree, tsize, 1);
    insert(tree, tsize, 4);
    print(tree, 20);
    return 0;
}

3. Binary Tree – Linked List

#include <stdio.h>
#include <stdlib.h>
struct node {
    int key;
    struct node *left, *right;
};
// Create a node
struct node *newNode(int item) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// Inorder Traversal
void inorder(struct node *root) {
    if (root != NULL) {
        // Traverse left
        inorder(root->left);
        // Traverse root
        printf("%d -> ", root->key);
        // Traverse right
        inorder(root->right);
    }
}
void preorder(struct node *root) {
    if (root != NULL) {
        printf("%d -> ", root->key);
        preorder(root->left);
        preorder(root->right);
    }
}
void postorder(struct node *root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d -> ", root->key);
    }
}

// Insert a node
struct node *insert(struct node *node, int key) {
    // Return a new node if the tree is empty
    if (node == NULL) return newNode(key);
    // Traverse to the right place and insert the node
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);
    return node;
}

// Driver code
int main() {
    int ch, val;
    struct node *root = NULL;
    do {
        printf("\n1. Insert\n2. Display Inorder\n3. Preorder\n4. Postorder\n5. Exit\n");
        printf("\nEnter choice: ");
        scanf("%d", &ch);
        switch(ch) {
            case 1:
                printf("\nEnter value to insert: ");
                scanf("%d", &val);
                root = insert(root, val);
                printf("Root data - %d", root->key);
                break;
            case 2:
                printf("Inorder traversal: ");
                inorder(root);
                break;
            case 3:
                printf("Preorder traversal: ");
                preorder(root);
                break;
            case 4:
                printf("Postorder traversal: ");
                postorder(root);
                break;
            case 5:
                exit(0);
        }
    } while(ch <= 5);
}

4. Circular Linked List

#include <stdio.h>
#include <stdlib.h>
struct node {
    int data;
    struct node *next;
} *head, *tail, *cur; // node declaration

// Function declaration
void insertHead(int);
void insertTail(int);
void display();
void deleteHead();
void deleteTail();

// Function definition
void insertHead(int val) {
    cur = (struct node*)malloc(sizeof(struct node));
    cur->data = val;
    cur->next = NULL;
    if(head == NULL) {
        head = tail = cur;
        head->next = head;
    } else {
        cur->next = head;
        head = cur;
        tail->next = head;
    }
}
void insertTail(int val) {
    cur = (struct node*)malloc(sizeof(struct node));
    cur->data = val;
    cur->next = NULL;
    if(head == NULL) {
        head = tail = cur;
        head->next = head;
    } else {
        tail->next = cur;
        tail = cur;
        tail->next = head;
    }
}
void display() {
    struct node *p = head;
    if(head == NULL)
        printf("\nList is empty");
    else {
        while(p->next != head) {
            printf("%d\t", p->data);
            p = p->next;
        }
        printf("%d\t", p->data);
    }
}
void deleteHead() {
    if(head == NULL)
        printf("List is empty");
    else if(head == tail)
        head = tail = NULL;
    else {
        head = head->next;
        tail->next = head;
    }
}
void deleteTail() {
    struct node *p = head, *k;
    if(head == NULL)
        printf("List is empty");
    else if(head == tail)
        head = tail = NULL;
    else {
        while(p->next != head) {
            k = p;
            p = p->next;
        }
        tail = k;
        tail->next = head;
    }
}
int main() {
    head = tail = NULL;
    int ch, val;
    do {
        printf("\n1. Insert Head\n2. Insert Tail\n3. Display\n4. Delete Head\n5. Delete Tail\n6. Exit\n");
        printf("\nEnter choice: ");
        scanf("%d", &ch);
        switch(ch) {
            case 1:
                printf("\nEnter value to insert: ");
                scanf("%d", &val);
                insertHead(val);
                break;
            case 2:
                printf("\nEnter value to insert: ");
                scanf("%d", &val);
                insertTail(val);
                break;
            case 3:
                display();
                break;
            case 4:
                deleteHead();
                break;
            case 5:
                deleteTail();
                break;
            case 6:
                exit(0);
            default:
                printf("\nInvalid choice");
        }
    } while(ch <= 6);
    return 0;
}

5. Doubly Linked List

#include <stdio.h>
#include <stdlib.h>
struct node {
    int data;
    struct node *next, *prev;
} *head, *tail, *cur;
void insertHead(int);
void insertTail(int);
void deleteHead();
void deleteTail();
void display();

void insertHead(int val) {
    cur = (struct node*)malloc(sizeof(struct node));
    cur->data = val;
    cur->next = NULL;
    if(head == NULL)
        head = tail = cur;
    else {
        cur->next = head;
        head->prev = cur;
        head = cur;
    }
}
void insertTail(int val) {
    cur = (struct node*)malloc(sizeof(struct node));
    cur->data = val;
    cur->next = NULL;
    if(head == NULL)
        head = tail = cur;
    else {
        tail->next = cur;
        cur->prev = tail;
        tail = cur;
    }
}
void display() {
    struct node *p = head;
    if(head == NULL)
        printf("\nList is empty");
    else {
        printf("\nMoving forward:");
        while(p != NULL) {
            printf("%d\t", p->data);
            p = p->next;
        }
        p = tail;
        printf("\nMoving Backward:");
        while(p != NULL) {
            printf("%d\t", p->data);
            p = p->prev;
        }
    }
}
void deleteHead() {
    if(head == NULL)
        printf("List is empty");
    else if(head == tail)
        head = tail = NULL;
    else {
        head = head->next;
        head->prev = NULL;
    }
}
void deleteTail() {
    if(head == NULL)
        printf("List is empty");
    else if(head == tail)
        head = tail = NULL;
    else {
        tail = tail->prev;
        tail->next = NULL;
    }
}
int main() {
    head = tail = NULL;
    int ch, val;
    do {
        printf("\n1. Insert Head\n2. Insert Tail\n3. Delete Head\n4. Delete Tail\n5. Display\n6. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &ch);
        switch(ch) {
            case 1:
                printf("Enter value to insert: ");
                scanf("%d", &val);
                insertHead(val);
                break;
            case 2:
                printf("Enter value to insert: ");
                scanf("%d", &val);
                insertTail(val);
                break;
            case 3:
                deleteHead();
                break;
            case 4:
                deleteTail();
                break;
            case 5:
                display();
                break;
            case 6:
                exit(0);
            default:
                printf("Invalid choice");
        }
    } while(ch <= 6);
    return 0;
}

6. Postfix Evaluation

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int stack[20];
int top = -1;
void push(int);
int pop();
void display();
void push(int val) {
    if(top == 19)
        printf("Overflow\n");
    else {
        top++;
        stack[top] = val;
    }
}
int pop() {
    if(top == -1)
        printf("Empty\n");
    else {
        int c = stack[top];
        top--;
        return c;
    }
}
void display() {
    if (top == -1)
        printf("List is empty\n");
    else {
        for (int i = 0; i <= top; i++) {
            printf("%d ", stack[i]);
        }
        printf("\n");
    }
}
int main() {
    int ch;
    char str[20];
    int val, res;
    printf("Enter Postfix expression: ");
    scanf("%s", str);
    for (int i = 0; str[i] != '\0'; i++) {
        if(isdigit(str[i]))
            push(str[i] - '0');
        else {
            int op1 = pop();
            int op2 = pop();
            if(str[i] == '+')
                res = op2 + op1;
            else if(str[i] == '-')
                res = op2 - op1;
            else if(str[i] == '*')
                res = op2 * op1;
            else if(str[i] == '/')
                res = op2 / op1;
            else if(str[i] == '%')
                res = op2 % op1;
            push(res);
        }
    }
    printf("The result is %d", pop());
}

7. Graph – Linked List

#include <stdio.h>
#include <stdlib.h>
struct node {
    int vertex;
    struct node* next;
};
struct node* createNode(int);
struct Graph {
    int numVertices;
    struct node** adjLists;
};
// Create a node
struct node* createNode(int v) {
    struct node* newNode = malloc(sizeof(struct node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}
// Create a graph
struct Graph* createAGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(struct node*));
    for (int i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;
    return graph;
}
// Add edge
void addEdge(struct Graph* graph, int s, int d) {
    // Add edge from s to d
    struct node* newNode = createNode(d);
    newNode->next = graph->adjLists[s];
    graph->adjLists[s] = newNode;
    // Add edge from d to s
    newNode = createNode(s);
    newNode->next = graph->adjLists[d];
    graph->adjLists[d] = newNode;
}
// Print the graph
void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->numVertices; v++) {
        struct node* temp = graph->adjLists[v];
        printf("\nVertex %d: ", v);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}
int main() {
    struct Graph* graph = createAGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 0, 3);
    addEdge(graph, 1, 2);
    printGraph(graph);
    return 0;
}

8. Graph – Array

#include <stdio.h>
void print(int mat[3][3], int n) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("%d  ", mat[i][j]);
        }
        printf("\n");
    }
}
void add(int mat[3][3], int i, int j) {
    mat[i][j] = 1;
    mat[j][i] = 1;
}
int main() {
    int n;
    printf("Enter number of nodes: ");
    scanf("%d", &n);
    int mat[3][3];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            mat[i][j] = 0;
        }
    }
    print(mat, n);
    add(mat, 0, 1);
    add(mat, 0, 2);
    add(mat, 1, 2);
    printf("Adjacency matrix:\n");
    print(mat, n);
}

9. Infix to Postfix

#include <stdio.h>
#include <string.h>
#include <ctype.h>
char stack[20];
int top = -1;
void push(char);
int precedence(char);
char pop();
void display();
void push(char val) {
    if(top == 19)
        printf("Overflow\n");
    else {
        top++;
        stack[top] = val;
    }
}
int precedence(char a) {
    if(a == '+' || a == '-')
        return 0;
    else if(a == '*' || a == '%' || a == '/')
        return 1;
}
char pop() {
    if(top == -1)
        printf("Empty\n");
    else {
        char c = stack[top];
        top--;
        return c;
    }
}
void display() {
    if (top == -1)
        printf("List is empty\n");
    else {
        for (int i = 0; i <= top; i++) {
            printf("%c", stack[i]);
        }
        printf("\n");
    }
}
int main() {
    int ch;
    char str[20];
    printf("Expression: ");
    scanf("%s", str);
    for (int i = 0; str[i] != '\0'; i++) {
        if(isalpha(str[i]))
            printf("%c", str[i]);
        else if(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '%' || str[i] == '/') {
            if(top == -1)
                push(str[i]);
            else {
                int op1 = precedence(stack[top]);
                int op2 = precedence(str[i]);
                if(op1 >= op2) {
                    char c = pop();
                    printf("%c", c);
                    push(str[i]);
                } else
                    push(str[i]);
            }
        }
    }
    while (top != -1) {
        char a = pop();
        printf("%c", a);
    }
}

10. Priority Queue – Ascending

#include <stdio.h>
#include <stdlib.h>
void sort();
void enqueue();
void dequeue();
void display();
int queue[5];
int Rear = -1;
int Front = -1;
int main() {
    int ch;
    do {
        printf("1. Enqueue Operation\n");
        printf("2. Dequeue Operation\n");
        printf("3. Display the Queue\n");
        printf("4. Exit\n");
        printf("Enter your choice of operations: ");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                enqueue();
                sort();
                break;
            case 2:
                dequeue();
                break;
            case 3:
                display();
                break;
            case 4:
                exit(0);
            default:
                printf("Incorrect choice\n");
        }
    } while(ch <= 4);
}
void sort() {
    int temp;
    for(int i = 0; i <= Rear; i++) {
        for(int j = i + 1; j <= Rear; j++) {
            if(queue[i] > queue[j]) {
                temp = queue[i];
                queue[i] = queue[j];
                queue[j] = temp;
            }
        }
    }
}
void enqueue() {
    int val;
    if (Rear == 4)
        printf("Overflow\n");
    else {
        if (Front == -1)
            Front = 0;
        printf("Element to be inserted in the Queue: ");
        scanf("%d", &val);
        Rear = Rear + 1;
        queue[Rear] = val;
    }
}
void dequeue() {
    if (Front == -1 || Front > Rear) {
        printf("Underflow\n");
        return;
    } else {
        printf("Element deleted from the Queue: %d\n", queue[Front]);
        Front = Front + 1;
    }
}
void display() {
    if (Front == -1)
        printf("Empty Queue\n");
    else {
        printf("Queue: \n");
        for (int i = Front; i <= Rear; i++)
            printf("%d ", queue[i]);
        printf("\n");
    }
}

11. Priority Queue – Descending

#include <stdio.h>
#include <stdlib.h>
void sort();
void enqueue();
void dequeue();
void display();
int queue[5];
int Rear = -1;
int Front = -1;
int main() {
    int ch;
    do {
        printf("1. Enqueue Operation\n");
        printf("2. Dequeue Operation\n");
        printf("3. Display the Queue\n");
        printf("4. Exit\n");
        printf("Enter your choice of operations: ");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                enqueue();
                sort();
                break;
            case 2:
                dequeue();
                break;
            case 3:
                display();
                break;
            case 4:
                exit(0);
            default:
                printf("Incorrect choice\n");
        }
    } while(ch <= 4);
}
void sort() {
    int temp;
    for(int i = 0; i <= Rear; i++) {
        for(int j = i + 1; j <= Rear; j++) {
            if(queue[i] < queue[j]) {
                temp = queue[i];
                queue[i] = queue[j];
                queue[j] = temp;
            }
        }
    }
}
void enqueue() {
    int val;
    if (Rear == 4)
        printf("Overflow\n");
    else {
        if (Front == -1)
            Front = 0;
        printf("Element to be inserted in the Queue: ");
        scanf("%d", &val);
        Rear = Rear + 1;
        queue[Rear] = val;
    }
}
void dequeue() {
    if (Front == -1 || Front > Rear) {
        printf("Underflow\n");
        return;
    } else {
        printf("Element deleted from the Queue: %d\n", queue[Front]);
        Front = Front + 1;
    }
}
void display() {
    if (Front == -1)
        printf("Empty Queue\n");
    else {
        printf("Queue: \n");
        for (int i = Front; i <= Rear; i++)
            printf("%d ", queue[i]);
        printf("\n");
    }
}

12. Queue – Linked List

#include <stdio.h>
#include <stdlib.h>
struct node {
    int data;
    struct node *next;
} *front, *rear, *cur;
void enqueue(int);
void dequeue();
void display();
void enqueue(int val) {
    cur = (struct node*)malloc(sizeof(struct node));
    cur->data = val;
    cur->next = NULL;
    if(front == NULL)
        front = rear = cur;
    else {
        rear->next = cur;
        rear = cur;
    }
}
void dequeue() {
    if(front == NULL)
        printf("The list is empty\n");
    else
        front = front->next;
}
void display() {
    struct node *p = front;
    if(front == NULL)
        printf("The list is empty\n");
    else {
        printf("THE DATA ARE:\n");
        while(p != NULL) {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}
int main() {
    front = rear = NULL;
    int a;
    do {
        printf("[1]: Enqueue\n[2]: Dequeue\n[3]: Display\n[4]: Exit\n");
        scanf("%d", &a);
        switch(a) {
            case 1: {
                int val;
                printf("ENTER VALUE\n");
                scanf("%d", &val);
                enqueue(val);
                break;
            }
            case 2: {
                dequeue();
                break;
            }
            case 3: {
                display();
                break;
            }
            case 4: {
                exit(0);
            }
            default: {
                printf("Invalid\n");
            }
        }
    } while(a <= 4);
}

13. Queue – Array

#include <stdio.h>
#include <stdlib.h>
void enqueue();
void dequeue();
void display();
int queue[5];
int Rear = -1;
int Front = -1;
int main() {
    int ch;
    do {
        printf("1. Enqueue Operation\n");
        printf("2. Dequeue Operation\n");
        printf("3. Display the Queue\n");
        printf("4. Exit\n");
        printf("Enter your choice of operations: ");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                enqueue();
                break;
            case 2:
                dequeue();
                break;
            case 3:
                display();
                break;
            case 4:
                exit(0);
            default:
                printf("Incorrect choice\n");
        }
    } while(ch <= 4);
}
void enqueue() {
    int val;
    if (Rear == 4)
        printf("Overflow\n");
    else {
        if (Front == -1)
            Front = 0;
        printf("Element to be inserted in the Queue: ");
        scanf("%d", &val);
        Rear = Rear + 1;
        queue[Rear] = val;
    }
}
void dequeue() {
    if (Front == -1 || Front > Rear) {
        printf("Underflow\n");
        return;
    } else {
        printf("Element deleted from the Queue: %d\n", queue[Front]);
        Front = Front + 1;
    }
}
void display() {
    if (Front == -1)
        printf("Empty Queue\n");
    else {
        printf("Queue: \n");
        for (int i = Front; i <= Rear; i++)
            printf("%d ", queue[i]);
        printf("\n");
    }
}

14. Singly Linked List

#include <stdio.h>
#include <stdlib.h>
struct node {
    int data;
    struct node *next;
} *head, *tail, *cur;
void insertHead(int);
void insertTail(int);
void display();
void deleteHead();
void deleteTail();
void deleteTail() {
    if(head == NULL)
        printf("\nCannot delete....List is empty");
    else if(head == tail)
        head = tail = NULL;
    else {
        struct node *p = head, *k;
        while(p->next != NULL) {
            k = p;
            p = p->next;
        }
        k->next = NULL;
        tail = k;
    }
}
void deleteHead() {
    if(head == NULL)
        printf("\nCannot delete....List is empty");
    else
        head = head->next;
}
void insertHead(int val) {
    cur = (struct node*)malloc(sizeof(struct node));
    cur->data = val;
    cur->next = NULL;
    if(head == NULL)
        head = tail = cur;
    else {
        cur->next = head;
        head = cur;
    }
}
void insertTail(int val) {
    cur = (struct node*)malloc(sizeof(struct node));
    cur->data = val;
    cur->next = NULL;
    if(head == NULL)
        head = tail = cur;
    else {
        tail->next = cur;
        tail = cur;
    }
}
void display() {
    if(head == NULL)
        printf("List is empty");
    else {
        struct node *p = head;
        while(p != NULL) {
            printf("%d\t", p->data);
            p = p->next;
        }
    }
}
int main() {
    int ch;
    head = tail = NULL;
    int val;
    do {
        printf("\n1. Insert Head\n2. Insert Tail\n3. Display\n4. Delete Head\n5. Delete Tail\n6. Exit\n");
        printf("\nEnter choice: ");
        scanf("%d", &ch);
        switch(ch) {
            case 1:
                printf("\nEnter value to insert: ");
                scanf("%d", &val);
                insertHead(val);
                break;
            case 2:
                printf("\nEnter value to insert: ");
                scanf("%d", &val);
                insertTail(val);
                break;
            case 3:
                display();
                break;
            case 4:
                deleteHead();
                break;
            case 5:
                deleteTail();
                break;
            case 6:
                exit(0);
            default:
                printf("Invalid choice");
        }
    } while(ch <= 6);
    return 0;
}

15. Stack – Palindrome

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char stack[20];
int top = -1;
void push(char);
char pop();
void display();
void push(char val) {
    if(top == 19)
        printf("Overflow\n");
    else {
        top++;
        stack[top] = val;
    }
}
char pop() {
    if(top == -1)
        printf("");
    else {
        char c = stack[top];
        top--;
        return c;
    }
}
void display() {
    if (top == -1)
        printf("List is empty\n");
    else {
        for (int i = 0; i <= top; i++) {
            printf("%c", stack[i]);
        }
        printf("\n");
    }
}
int main() {
    int ch;
    char str[20];
    printf("String: ");
    scanf("%s", str);
    for(int i = 0; str[i] != '\0'; i++)
        push(str[i]);
    display();
    int flag = 0;
    for(int i = 0; i <= strlen(str) / 2; i++) {
        char c = pop();
        if(c != str[i]) {
            flag++;
            printf("Not palindrome\n");
            return 0;
        }
    }
    if(flag == 0)
        printf("Palindrome\n");
    return 0;
}

16. Stack – Array

#include <stdio.h>
#include <stdlib.h>
int stack[5];
int top = -1;
void push(int);
void pop();
void peek();
void display();
void push(int val) {
    if(top == 4)
        printf("Overflow\n");
    else {
        top++;
        stack[top] = val;
    }
}
void pop() {
    if(top == -1)
        printf("The list is empty");
    else
        top--;
}
void peek() {
    if(top == -1)
        printf("The list is empty");
    else
        printf("Top = %d\n", stack[top]);
}
void display() {
    if(top == -1)
        printf("The list is empty");
    else {
        printf("THE DATA ARE:\n");
        for(int i = 0; i <= top; i++)
            printf("%d ", stack[i]);
    }
    printf("\n");
}
int main() {
    int ch;
    do {
        printf("[1]: Push\n[2]: Pop\n[3]: Peek\n[4]: Display\n[5]: Exit\n");
        scanf("%d", &ch);
        switch(ch) {
            case 1: {
                int val;
                printf("ENTER VALUE\n");
                scanf("%d", &val);
                push(val);
                break;
            }
            case 2: {
                pop();
                break;
            }
            case 3: {
                peek();
                break;
            }
            case 4: {
                display();
                break;
            }
            case 5: {
                exit(0);
            }
            default: {
                printf("Invalid");
            }
        }
    } while(ch <= 5);
}

17. Stack – Linked List

#include <stdio.h>
#include <stdlib.h>
struct node {
    int data;
    struct node *next;
} *top, *cur;
void push(int);
void pop();
void peek();
void display();
void push(int val) {
    cur = (struct node*)malloc(sizeof(struct node));
    cur->data = val;
    cur->next = NULL;
    if(top == NULL)
        top = cur;
    else {
        cur->next = top;
        top = cur;
    }
}
void pop() {
    if(top == NULL)
        printf("The list is empty");
    else
        top = top->next;
}
void peek() {
    if(top == NULL)
        printf("The list is empty");
    else
        printf("Top = %d\n", top->data);
}
void display() {
    struct node *p = top;
    if(top == NULL)
        printf("The list is empty");
    else {
        printf("THE DATA ARE:\n");
        while(p != NULL) {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}
int main() {
    top = NULL;
    int a;
    do {
        printf("[1]: Push\n[2]: Pop\n[3]: Peek\n[4]: Display\n[5]: Exit\n");
        scanf("%d", &a);
        switch(a) {
            case 1: {
                int val;
                printf("ENTER VALUE\n");
                scanf("%d", &val);
                push(val);
                break;
            }
            case 2: {
                pop();
                break;
            }
            case 3: {
                peek();
                break;
            }
            case 4: {
                display();
                break;
            }
            case 5: {
                exit(0);
            }
            default: {
                printf("Invalid");
            }
        }
    } while(a <= 5);
}