Stack Implementation Using C
A stack can be implemented in C using two methods:
- Array-Based Implementation
- Linked List-Based Implementation
1. Array-Based Stack Implementation
In this approach:
- A fixed-size array is used to store stack elements.
- A variable top keeps track of the last element added to the stack.
C Code
c
Copy code
#include <stdio.h>
#define MAX 5 // Maximum size of the stack
typedef struct {
int arr[MAX];
int top;
} Stack;
// Function to initialize the stack
void initStack(Stack *s) {
s->top = -1;
}
// Function to check if the stack is full
int isFull(Stack *s) {
return s->top == MAX – 1;
}
// Function to check if the stack is empty
int isEmpty(Stack *s) {
return s->top == -1;
}
// Push operation
void push(Stack *s, int value) {
if (isFull(s)) {
printf(“Stack Overflow\n”);
} else {
s->arr[++(s->top)] = value;
printf(“Pushed: %d\n”, value);
}
}
// Pop operation
int pop(Stack *s) {
if (isEmpty(s)) {
printf(“Stack Underflow\n”);
return -1;
} else {
return s->arr[(s->top)–];
}
}
// Peek operation
int peek(Stack *s) {
if (isEmpty(s)) {
printf(“Stack is empty\n”);
return -1;
} else {
return s->arr[s->top];
}
}
int main() {
Stack s;
initStack(&s);
push(&s, 10);
push(&s, 20);
printf(“Top element: %d\n”, peek(&s));
printf(“Popped: %d\n”, pop(&s));
printf(“Top element after pop: %d\n”, peek(&s));
return 0;
}
2. Linked List-Based Stack Implementation
In this approach:
- Each stack element is stored as a node in a linked list.
- The top pointer points to the last inserted node.
C Code
c
Copy code
#include <stdio.h>
#include <stdlib.h>
// Define a node structure
typedef struct Node {
int data;
struct Node *next;
} Node;
// Push operation
void push(Node **top, int value) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf(“Stack Overflow\n”);
return;
}
newNode->data = value;
newNode->next = *top;
*top = newNode;
printf(“Pushed: %d\n”, value);
}
// Pop operation
int pop(Node **top) {
if (*top == NULL) {
printf(“Stack Underflow\n”);
return -1;
}
Node *temp = *top;
int value = temp->data;
*top = temp->next;
free(temp);
return value;
}
// Peek operation
int peek(Node *top) {
if (top == NULL) {
printf(“Stack is empty\n”);
return -1;
}
return top->data;
}
// Check if the stack is empty
int isEmpty(Node *top) {
return top == NULL;
}
int main() {
Node *top = NULL;
push(&top, 10);
push(&top, 20);
printf(“Top element: %d\n”, peek(top));
printf(“Popped: %d\n”, pop(&top));
printf(“Top element after pop: %d\n”, peek(top));
return 0;
}
Comparison of C Implementations
| Aspect | Array-Based Stack | Linked List-Based Stack |
| Memory Usage | Fixed, can waste space. | Dynamic, efficient usage. |
| Size Limit | Limited by array size. | Limited by system memory. |
| Implementation | Simple and faster. | Requires dynamic memory management. |
Choose the implementation based on the problem requirements and resource constraints.