C Program to Implement Stack Using Linked List

Introduction

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. In a stack implemented using a linked list, each node contains data and a pointer to the next node. The top of the stack is represented by the head of the linked list, and stack operations such as push, pop, and peek can be performed by manipulating the linked list.

Example:

• Push Operation: Adding elements [10, 20, 30] to the stack results in 30 being at the top.
• Pop Operation: Removing the top element (30) from the stack leaves 20 at the top.

Problem Statement

Create a C program that:

• Implements a stack using a linked list.
• Performs stack operations such as push, pop, and peek.
• Displays the stack contents after each operation.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions and dynamic memory allocation.
2. Define the Node Structure: Create a structure for the node containing an integer data part and a pointer to the next node.
3. Implement the Stack Operations:

• Push: Add an element to the top of the stack.
• Pop: Remove and return the top element from the stack.
• Peek/Top: Return the top element without removing it.
• IsEmpty: Check if the stack is empty.

4. Create a Main Function: In the main() function, allow the user to perform stack operations interactively.

C Program to Implement Stack Using Linked List

#include <stdio.h> #include <stdlib.h> // Step 2: Define the Node Structure struct Node { int data; struct Node* next; }; // Function to check if the stack is empty int isEmpty(struct Node* top) { return top == NULL; } // Function to push an element onto the stack void push(struct Node** top_ref, int value) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); if (new_node == NULL) { printf("Stack overflow! Cannot push %d onto the stack.\n", value); return; } new_node->data = value; new_node->next = *top_ref; *top_ref = new_node; printf("%d pushed onto the stack.\n", value); } // Function to pop an element from the stack int pop(struct Node** top_ref) { if (isEmpty(*top_ref)) { printf("Stack underflow! Cannot pop from an empty stack.\n"); return -1; // Return -1 to indicate stack underflow } struct Node* temp = *top_ref; int popped_value = temp->data; *top_ref = temp->next; free(temp); return popped_value; } // Function to peek the top element of the stack int peek(struct Node* top) { if (isEmpty(top)) { printf("Stack is empty! Cannot peek.\n"); return -1; // Return -1 to indicate an empty stack } return top->data; } // Function to display the stack elements void display(struct Node* top) { if (isEmpty(top)) { printf("Stack is empty!\n"); return; } printf("Stack elements: "); while (top != NULL) { printf("%d -> ", top->data); top = top->next; } printf("NULL\n"); } int main() { struct Node* stack = NULL; int choice, value; while (1) { // Step 4: Provide a Menu for Stack Operations printf("\nStack Operations Menu:\n"); printf("1. Push\n"); printf("2. Pop\n"); printf("3. Peek\n"); printf("4. Display\n"); printf("5. Exit\n"); printf("Enter your choice: "); scanf("%d", &choice); switch (choice) { case 1: printf("Enter value to push onto the stack: "); scanf("%d", &value); push(&stack, value); break; case 2: value = pop(&stack); if (value != -1) { printf("Popped value: %d\n", value); } break; case 3: value = peek(stack); if (value != -1) { printf("Top value: %d\n", value); } break; case 4: display(stack); break; case 5: exit(0); default: printf("Invalid choice! Please enter a valid option.\n"); } } return 0; // Return 0 to indicate successful execution } 

Explanation

Step 2: Define the Node Structure

• The Node structure contains two members: an integer data to store the node’s data and a pointer next to point to the next node in the stack.

Function to Check if the Stack is Empty

• The isEmpty function returns 1 if the stack is empty (top is NULL), and 0 otherwise.

Function to Push an Element onto the Stack

• The push function adds a new element to the top of the stack. A new node is created, and its next pointer is set to the current top of the stack. The top pointer is then updated to this new node.

Function to Pop an Element from the Stack

• The pop function removes and returns the top element from the stack if the stack is not empty. The top pointer is updated to the next node, and the removed node is freed from memory.

Function to Peek the Top Element of the Stack

• The peek function returns the top element of the stack without removing it. It is useful for viewing the element at the top of the stack.

Function to Display the Stack Elements

• The display function prints all the elements in the stack from top to bottom.

Main Function

• The main function provides a menu-driven interface allowing the user to perform various stack operations interactively.

Output Example

Example Output:

Stack Operations Menu: 1. Push 2. Pop 3. Peek 4. Display 5. Exit Enter your choice: 1 Enter value to push onto the stack: 10 10 pushed onto the stack. Stack Operations Menu: 1. Push 2. Pop 3. Peek 4. Display 5. Exit Enter your choice: 1 Enter value to push onto the stack: 20 20 pushed onto the stack. Stack Operations Menu: 1. Push 2. Pop 3. Peek 4. Display 5. Exit Enter your choice: 4 Stack elements: 20 -> 10 -> NULL Stack Operations Menu: 1. Push 2. Pop 3. Peek 4. Display 5. Exit Enter your choice: 2 Popped value: 20 

Conclusion

This C program demonstrates how to implement a stack using a linked list. It includes basic stack operations such as push, pop, peek, and display, making it a useful example for beginners learning about data structures in C programming.