#include <stdio.h>
#include <stdlib.h>
// Define a structure for a linked list node
struct Node {
int data;
struct Node* next;
};
// Function to push an element onto the stack
void push(struct Node** top, int value) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("Heap overflow\n");
return;
}
newNode->data = value; // Set the data
newNode->next = *top; // Link the new node to the current top
*top = newNode; // Update the top to the new node
printf("Pushed %d onto the stack.\n", value);
}
// Function to check if the stack is empty
int isEmpty(struct Node* top) {
return top == NULL;
}
// Function to pop an element from the stack
int pop(struct Node** top) {
if (isEmpty(*top)) {
printf("Stack underflow\n");
return -1;
}
struct Node* temp = *top; // Temporarily hold the top node
*top = (*top)->next; // Update the top to the next node
int poppedValue = temp->data; // Retrieve the popped value
free(temp); // Free the memory of the old top node
printf("Popped %d from the stack.\n", poppedValue);
return poppedValue;
}
// Function to peek the top element of the stack
int peek(struct Node* top) {
if (!isEmpty(top)) {
return top->data;
} else {
printf("Stack is empty\n");
return -1;
}
}
// Function to display all elements in the stack
void display(struct Node* top) {
if (isEmpty(top)) {
printf("Stack is empty\n");
} else {
printf("Stack elements: ");
struct Node* temp = top;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
}
int main() {
struct Node* stack = NULL; // Initialize an empty stack
// Push elements onto the stack
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
// Display stack elements
display(stack);
// Peek at the top element
printf("Top element is %d\n", peek(stack));
// Pop elements from the stack
pop(&stack);
pop(&stack);
// Display stack elements again
display(stack);
// Pop the last element
pop(&stack);
// Try to pop from an empty stack
pop(&stack);
return 0;
}
Explanation:
- Structure Definition (
struct Node):- The
Nodestructure represents each element in the stack. - Each node stores an integer (
data) and a pointer to the next node (next).
- The
- Push Function (
push):- This function inserts a new element at the top of the stack.
- It creates a new node, sets its
datawith the given value, and points it to the currenttopnode. - Then, it updates the
toppointer to the new node, making it the new top of the stack.
- Pop Function (
pop):- This function removes the element from the top of the stack.
- It first checks if the stack is empty to avoid underflow.
- If not empty, it updates the
topto point to the next node and frees the old top node’s memory. - It returns the value of the popped node.
- Peek Function (
peek):- This function returns the value of the top element without removing it.
- It checks if the stack is empty before attempting to access the
top‘s data.
- Display Function (
display):- This function prints all the elements in the stack from top to bottom.
- It traverses from the top node to the bottom, printing each
data.
- Main Function (
main):- The stack is initialized as
NULL, representing an empty stack. - A few values are pushed onto the stack, displayed, and some are popped off to show how the stack shrinks.
- The program also attempts to pop from an empty stack to demonstrate the underflow handling.
- The stack is initialized as
Pushed 10 onto the stack.
Pushed 20 onto the stack.
Pushed 30 onto the stack.
Stack elements: 30 20 10
Top element is 30
Popped 30 from the stack.
Popped 20 from the stack.
Stack elements: 10
Popped 10 from the stack.
Stack is empty
Stack underflow
Explanation of the Output:
- Three elements (10, 20, and 30) are pushed onto the stack.
- When displayed, the stack shows elements as
30 20 10, where30is at the top. - After popping, the top element
30is removed, followed by20. - The display then shows
10as the only element. - Popping again removes
10, leaving the stack empty. - Attempting another pop results in a “Stack underflow” message since the stack is empty.
This program effectively demonstrates the basic operations of a stack using a linked list, providing flexibility in terms of dynamic memory usage and avoiding the fixed size limitation of arrays.
