🧠 Stack

Shivani
2 days ago
3 min read

📌 Introduction to Stack

A stack is a linear data structure that follows the Last In First Out (LIFO) principle.
You can imagine a stack of plates: the last plate placed on top is the first to be removed.
Stack is used where order of processing matters, and where reversing or tracking the most recent operation is key.

🏗️ Key Properties / Functions of a Stack

Function	Description
push()	Insert an element onto the stack (top of stack).
pop()	Remove and return the top element of the stack.
top() / peek()	Retrieve the current top element without removing it.
size()	Return the number of elements in the stack.
isEmpty()	Check whether the stack is empty.

🧮 Internal Working

Stack is implemented using an array or linked list.
A variable called top tracks the index of the current top element.
When top == -1, the stack is empty.
push(x) → top++ then assign stack[top] = x.
pop() → return stack[top] then top--.

⏱️ Time Complexity

Operation	Time Complexity
push()	O(1)
pop()	O(1)
top()	O(1)
size()	O(1)

🎒 Real-Life Analogies

Wardrobe of clothes
Browser history
Backtracking in games or mazes

🧪 Example

Initialisation
int stack[10]; int top = -1;
Push operations
- push(5) → top becomes 0, stack = [5]
- push(10) → top becomes 1, stack = [5, 10]
- push(15) → top becomes 2, stack = [5, 10, 15]
Top element
- top() → returns 15
Pop operation
- pop() → returns 15, top becomes 1, stack = [5, 10]
Push more
- push(20) → top = 2, stack = [5, 10, 20]
Check top
- top() → returns 20

✅ Code Snippet (Array-based)


#include <stdio.h>

#define SIZE 10
int stack[SIZE];
int top = -1;

void push(int x) {
    if (top == SIZE - 1) {
        printf("Stack Overflow\\n");
    } else {
        stack[++top] = x;
        printf("Pushed: %d\\n", x);
    }
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow\\n");
        return -1;
    } else {
        int popped = stack[top--];
        printf("Popped: %d\\n", popped);
        return popped;
    }
}

int peek() {
    if (top == -1) {
        printf("Stack is empty\\n");
        return -1;
    } else {
        printf("Top: %d\\n", stack[top]);
        return stack[top];
    }
}

int main() {
    push(5);
    push(10);
    push(15);
    peek();    // 15
    pop();     // 15 removed
    peek();    // 10
    push(20);  // 20 added
    peek();    // 20
    return 0;
}

🏠 Homework Assignment

✅ Part 1 – Stack Implementation

Implement a stack using array with:
- push(), pop(), peek(), isEmpty(), size()
- Limit size to 5
- Handle overflow and underflow cases

✅ Part 2 – Manual Stack Trace

Perform the operations and draw the final stack:


push(1)
push(2)
push(3)
pop()
push(4)
peek()
push(5)
push(6) // Should trigger "Stack Overflow"

✅ Part 3 – Reverse an Array Using Stack

Task:

Write a program to reverse an array using a stack.

Example:



Input:  [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

Hint:

Push all elements of the array into a stack.
Pop elements one by one and put them back into the array.

Sample Code (Skeleton):


#include <stdio.h>

#define SIZE 5
int stack[SIZE];
int top = -1;

void push(int x) { /* same as above */ }
int pop() { /* same as above */ }

void reverseArray(int arr[], int n) {
    for (int i = 0; i < n; i++) push(arr[i]);
    for (int i = 0; i < n; i++) arr[i] = pop();
}

int main() {
    int arr[SIZE] = {1, 2, 3, 4, 5};
    reverseArray(arr, SIZE);
    for (int i = 0; i < SIZE; i++) printf("%d ", arr[i]);
    return 0;
}