Stacks 101: A Beginner's Overview

Introduction

Whether it's items in a store or books in a library, once they become more than handful, people naturally start tidying things up by stacking them. When man started programming data, stack was one of the first structures that he thought of when faced with the problem of maintaining data in an orderly fashion. However, there's a subtle distinction: data in a stack is consumed in an orderly manner, which isn't always the case in real-world scenarios.

Stacks in Data Structures

A Stack is a data structure in which addition of new element or deletion of an existing element always takes place at the same end. This end is often known as top of stack. This scenario is akin to a stack of plates in a cafeteria, where each new plate added is placed on top. Likewise, plates are also taken off from the top of the stack.

• Stack works on Last in First out (LIFO) system, meaning the last item added will be the first one removed.

• The last item added to the stack is referred to as the top of the stack.

• Both Insertion and deletion operations are carried out at the top of the stack.

Operations on stack

A stack is typically implemented using two fundamental operations - push and pop. Other operations include peek/top, isFull, and isEmpty.

1. Push():

• Before pushing an element onto the stack, we check if the stack is full.

• If the stack is full (top == size-1), the stack overflows and we cannot add elements to the stack.

void push(int value) {
    if (top >= MAX-1) {
        printf("Stack Overflow\n");
    } else {
        stack[++top] = value;
    }
}

2. Pop():

• Before removing an element from the stack, we check if the stack is empty.

• If the stack is empty (top == -1), then stack underflows and we cannot remove elements from the stack.

int pop() {
    if (top < 0) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        return stack[top--];
    }
}

3. Peek():

• Before returning the top element of the stack, we check if the stack is empty.

• If the stack is empty (top == -1), we just print "The stack is empty".

• Otherwise, we return the element stored at index = top.

int peek() {
    if (isEmpty()) {
        printf("The stack is empty\n");
        return -1;
    } else {
        return stack[top];
    }
}

4. isEmpty():

• Check the value at the top of the stack.

• If (top == -1), then the stack is empty, therefore return true

int isEmpty() {
    return top == -1;
}

5. isFull():

• Check the value at the top of the stack.

• If (top == size-1), then the stack is full, therefore return true

int isFull() {
    return top == MAX-1;
}

Code

#include <stdio.h>
#define MAX 100
int stack[MAX];
int top = -1;
void display(){
    for (int i = top; i >= 0; i--){
        printf("%d ", stack[i]);
    }
    printf("\n");
}

void push(int value){
    if (top >= MAX-1){
        printf("Stack Overflow\n");
    } 
    else{
        stack[++top] = value;
    }
}

int pop(){
    if (top < 0){
        printf("Stack Underflow\n");
        return -1;
    } 
    else {
        return stack[top--];
    }
}

int isEmpty(){
    return top == -1;
}

int peek(){
    if (isEmpty()) {
        printf("The stack is empty\n");
        return -1;
    } 
    else {
        return stack[top];
    }
}

int isFull(){
    return top == MAX-1;
}

void main(){
    push(1);
    push(2);
    push(3);
    display(); 
    // 3 2 1 
    printf("The top element is : %d\n", peek()); 
    // The top element is : 3
    printf("The popped elemnt from stack is: %d\n", pop()); 
    // The popped elemnt from stack is: 3
    printf("The stack is empty : %s\n", isEmpty() ? "true" : "false");
    // The stack is empty : false
    printf("The stack is full : %s\n", isFull() ? "true" : "false");
    // The stack is full : false
    display(); 
    // 2 1 
}

And that concludes our overview of stacks. hope it was a good read for you. Thank you! :)