DSA Tutorial

STACK USING ARRAY

🔲 Stack using Array in DSA

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last element added is the first to be removed. While a stack can be implemented using a linked list, it is also commonly implemented using an array, which offers better memory usage in situations where the stack size is known in advance.

Stack Implementation using Array

In this implementation, the stack is represented as an array. The top pointer keeps track of the last pushed element. When an element is pushed onto the stack, it is placed at the position indicated by the top. When an element is popped, it is removed from the top of the stack.

#include 
#include 

#define MAX 5 // Maximum size of the stack

// Define the Stack structure
struct Stack {
    int arr[MAX];
    int top;
};

// Function to initialize the stack
void initStack(struct Stack* s) {
    s->top = -1; // Indicates the stack is empty
}

// Function to push an element to the stack
void push(struct Stack* s, int value) {
    if (s->top == MAX - 1) {
        printf("Stack Overflow\n");
        return;
    }
    s->arr[++(s->top)] = value;
    printf("Pushed %d\n", value);
}

// Function to pop an element from the stack
int pop(struct Stack* s) {
    if (s->top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    int poppedData = s->arr[s->top--];
    return poppedData;
}

// Function to peek the top element of the stack
int peek(struct Stack* s) {
    if (s->top == -1) {
        printf("Stack is Empty\n");
        return -1;
    }
    return s->arr[s->top];
}

// Function to check if the stack is empty
int isEmpty(struct Stack* s) {
    return (s->top == -1);
}

int main() {
    struct Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("Popped: %d\n", pop(&s));
    printf("Top element: %d\n", peek(&s));

    return 0;
}

Applications of Stack (Array-based)

The array-based stack implementation is commonly used in scenarios where the size of the stack is fixed or known in advance. Some use cases include:

Expression Evaluation: Stacks are used in evaluating arithmetic expressions, converting infix expressions to postfix, etc.
Function Call Stack: In programming, function calls are managed using a stack (call stack) to keep track of function execution.
Undo Mechanism: Stacks are used in applications like text editors to implement the undo feature, storing previous states.
Backtracking Algorithms: Solving problems like mazes, puzzles, or pathfinding using stack-based backtracking algorithms.

🚀 Advantages of Array-based Stack:
- Memory is contiguous, offering faster access to elements.
- Simple to implement and very efficient when the stack size is known.
- No additional overhead for memory allocation (as in linked list implementations).

🚀 Try Implementing Array-based Stack:
- Add a function to display the elements of the stack.
- Modify the implementation to support dynamic resizing of the stack when it reaches full capacity.
- Create a function that checks if the stack contains a specific element.

🌟 Enjoyed Learning with Us?

Help others discover Technorank Learning by sharing your honest experience.
Your support inspires us to keep building!