Demonstrate Linked List Implementation of Stack in C++?

Software Development
1

A stack is represented using nodes of a linked list. Each node consists of two parts:

data - The data part of each node contains the assigned value
next (storing address of next node) - next points to the node containing the next item in the stack
top - refers to the topmost node in the stack.

Both the push() and pop() operations are carried out at the front/top of the linked list and hence takes O(1) time.

A stack can also be implemented using arrays but here we are going for the Linked List approach since arrays are of limited size and size of stack has to be predetermined whereas in a linked list implementation nodes can be added according to the user’s requirements.

PSUEDO CODE: -

void push(int value) {
   struct Node *newNode;
   newNode = (struct Node *)malloc(sizeof(struct Node));
   newNode->data = value; // assign value to the node
   if (top == NULL) {
       newNode->next = NULL;
   } else {
       newNode->next = top; // Make the node as top
   }
   top = newNode; // top always points to the newly created node
   printf("Node is Inserted\n\n");
}
 

int pop() {
   if (top == NULL) {
       printf("\nStack Underflow\n");
   } else {
       struct Node *temp = top;
       int temp_data = top->data;
       top = top->next;
       free(temp);
       return temp_data;
   }
}

 
void display() {
   // Display the elements of the stack
   if (top == NULL) {
       printf("\nStack Underflow\n");
   } else {
       printf("The stack is \n");
       struct Node *temp = top;
       while (temp->next != NULL) {
           printf("%d--->", temp->data);
           temp = temp->next;
       }
       printf("%d--->NULL\n\n", temp->data);
   }