Stack Implementation and Operations
Stack is a linear data structure following LIFO (Last In, First Out) principle. Common operations
include push (add element), pop (remove top), peek (view top), isEmpty, and isFull.
#include <stdio.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int data) {
if (top >= MAX - 1) {
printf("Stack Overflow\n");
return;
}
stack[++top] = data;
}
int pop() {
if (top < 0) {
printf("Stack Underflow\n");
return -1;
}
return stack[top--];
}
int peek() {
if (top < 0) {
printf("Stack Empty\n");
return -1;
}
return stack[top];
}
int isEmpty() {
return top < 0;
}
Sample Input/Output:
Input:
push 10
push 20
peek
pop
isEmpty
Output:
20 (peek)
20 (popped)
0 (not empty, after first pop)
Time Complexity: Push, Pop, Peek: O(1); Space: O(n). [1]
Tower of Hanoi Using Stack
Problem Statement: Move n disks from source peg (A) to target peg (C) using auxiliary peg (B).
Rules: Move one disk at a time; never place larger disk on smaller one.
Iterative stack-based solution simulates pegs as three stacks, performing 2^n - 1 moves by
calculating disk positions per move.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct Stack {
unsigned capacity;
int top;
int *array;
};
struct Stack* createStack(unsigned capacity) {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
return stack;
}
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
int isFull(struct Stack* stack) {
return stack->top == stack->capacity - 1;
}
void push(struct Stack* stack, int item) {
if (!isFull(stack))
stack->array[++stack->top] = item;
}
int pop(struct Stack* stack) {
if (!isEmpty(stack))
return stack->array[stack->top--];
return INT_MIN;
}
int top(struct Stack* stack) {
return stack->top == -1 ? INT_MIN : stack->array[stack->top];
}
void moveDisksBetweenTwoPoles(struct Stack* src, struct Stack* dest, char s, char d) {
int pole1TopDisk = pop(src);
int pole2TopDisk = pop(dest);
if (pole1TopDisk == INT_MIN) {
push(src, pole2TopDisk);
printf("Move disk %d from pole %c to pole %c\n", pole2TopDisk, d, s);
} else if (pole2TopDisk == INT_MIN) {
push(dest, pole1TopDisk);
printf("Move disk %d from pole %c to pole %c\n", pole1TopDisk, s, d);
} else if (pole1TopDisk > pole2TopDisk) {
push(src, pole1TopDisk);
push(dest, pole2TopDisk);
printf("Move disk %d from pole %c to pole %c\n", pole2TopDisk, d, s);
} else {
push(dest, pole1TopDisk);
push(src, pole2TopDisk);
printf("Move disk %d from pole %c to pole %c\n", pole1TopDisk, s, d);
}
}
void tohIterative(struct Stack* src, struct Stack* dest, struct Stack* aux, int totalDisk
char srcChar = 'A', destChar = 'C', auxChar = 'B';
unsigned totalNumOfMoves = pow(2, totalDisks) - 1;
for (unsigned i = 1; i <= totalNumOfMoves; i++) {
if (i % 3 == 1)
moveDisksBetweenTwoPoles(src, dest, srcChar, destChar);
else if (i % 3 == 2)
moveDisksBetweenTwoPoles(src, aux, srcChar, auxChar);
else if (i % 3 == 0)
moveDisksBetweenTwoPoles(aux, dest, auxChar, destChar);
}
}
int main() {
int numDisks = 3;
struct Stack *src, *dest, *aux;
src = createStack(numDisks);
dest = createStack(numDisks);
aux = createStack(numDisks);
for (int i = numDisks; i >= 1; i--)
push(src, i);
printf("Moves for %d disks:\n", numDisks);
tohIterative(src, dest, aux, numDisks);
return 0;
}
Sample Input: 3 (disks)
Sample Output:
Moves for 3 disks:
Move disk 1 from pole A to pole C
Move disk 2 from pole A to pole B
Move disk 1 from pole C to pole B
Move disk 3 from pole A to pole C
Move disk 1 from pole B to pole A
Move disk 2 from pole B to pole C
Move disk 1 from pole A to pole C
Time Complexity: O(2^n) moves. Space Complexity: O(n). [1]
⁂
1. [Link]
2. [Link]
3. [Link]
4. [Link]
5. [Link]
6. [Link]
7. [Link]
8. [Link]
9. [Link]
10. [Link]