Write a program that uses a linked list to implement a stack.

Source Code

Brief explanation is provided after the source code.

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

typedef struct stackNode *LINK;
struct stackNode {
    int item;
    LINK next;
};

LINK head;
LINK newNode(int item, LINK h) {
    LINK nnode = malloc(sizeof(*nnode));
    nnode -> item = item;
    nnode -> next = h;
}

void stackInit(){
    head = NULL;
}

int stackEmpty() {
    return head == NULL;
}

void stackPush(int item) {
    head = newNode(item, head);
    printf("%d added to stack, ", item);
}

int stackPop(void) {
    int item = head -> item;
    LINK t = head -> next;
    free(head);
    head = t;
    return item;
}

void stackDisplay(void) {
    LINK t = head;
    while ( t != NULL) {
        printf("%d ", t -> item);
        t = t -> next;
    }
    printf("\n");
}

int main(int argc, char ** argv) {
    int i, item;
    stackInit();
    /* add 10 random numbers to stack */
    for (i = 0; i < 10; i++) {
        stackPush(rand() % 1000);
    }
    printf("\n");
    printf("Initial Contents: ");
    stackDisplay();
    /* pop 5 items off the stacks */
    for (i = 0; i < 5; i++) {
        if(!stackEmpty()) {
           item = stackPop();
           printf("%d popped from stack, ", item);
        }
    }
    printf("\n");
    printf("Contents after poping off 5 items: ");
    stackDisplay();

    return 0;
}

When you compile and execute the above program it produces the following result on Linux:

383 added to stack, 886 added to stack, 777 added to stack, 915 added to stack, 793 added to stack, 335 added to stack, 386 added to stack, 492 added to stack, 649 added to stack, 421 added to stack, 
Initial Contents: 421 649 492 386 335 793 915 777 886 383 
421 popped from stack, 649 popped from stack, 492 popped from stack, 386 popped from stack, 335 popped from stack, 
Contents after poping off 5 items: 793 915 777 886 383 

Brief Explanation

  • A stack is a last-in, first-out (LIFO) data structure.
  • Since a linked list is used in this implementation, we can store as many items as we want until memory becomes an issue.
  • All new items are added to the start of the list.
  • All deletions are done at the start of the list.
  • The program starts by initializing a stack.
  • The program iteratively push ten items to the stack using the function stackPush.
  • The function stackDisplay is used to display the items in the stack.
  • The program then iteratively pop out five items from the stack using the function stackPop.

Add comment


Security code
Refresh