Stack using Arrays

What is a Stack?

A stack is a linear data structure that follows the Last In First Out (LIFO) principle.

• Last In First Out (LIFO) means:
  ➔ The element added last is the first one to be removed.

Think of a stack of plates:

• You add (push) plates on top.

• You remove (pop) plates from the top.

---

🧠 Basic Stack Operations:

Operation	Meaning
push(x)	Add element x to the top.
pop()	Remove the topmost element.
peek()	View the topmost element (without removing).
isEmpty()	Check if the stack is empty.

---

How to Implement a Stack Using Arrays?

We maintain:

• An array to hold the elements

• An integer top that keeps track of the index of the top element

• If stack is empty, top = -1

• When we push, we increment top

• When we pop, we decrement top

Important Points:

• Stack Overflow happens when you push into a full stack.

• Stack Underflow happens when you pop from an empty stack.

• This stack implementation has a fixed size (MAX), so it is static.

• You can also implement a dynamic stack using linked lists 

Algorithms for Stack Operations

We assume:

• stack[MAX] is an array to store elements.

• top is an integer that tracks the top of the stack.

• Initially, top = -1.

Algorithm for PUSH (Insert an element)

1. If top == MAX - 1 then
       Output "Stack Overflow"
       Exit
2. Else
       top = top + 1
       stack[top] = item
3. End If
4. Return

Algorithm for POP(Remove top element)
1. If top == -1 then
       Output "Stack Underflow"
       Exit
2. Else
       item = stack[top]
       top = top - 1
3. End If
4. Return item

Algorithm for PEEK (View top element)
1. If top == -1 then
       Output "Stack is Empty"
       Exit
2. Else
       item = stack[top]
3. End If
4. Return item

Algorithm for isEmpty (Check if stack is empty)
1. If top == -1 then Return TRUE 
2. Else Return FALSE 



🚀 Time Complexity of Stack Operations

Operation
Time Complexity
Reason
Push (Insert)
    O(1)
Add element on top, only pointer update needed
Pop (Remove)
    O(1)
Remove element from top, only pointer update needed
Peek / Top
    O(1)
Access the top element directly
isEmpty
    O(1)
Check if the top pointer is -1 (array) or NULL (linked list)

C- Program Stack Implementation
/*******************************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_SIZE 100

// Global variables for the stack
int stack[MAX_SIZE];
int top = -1; // Initialize an empty stack

// Function to push an element onto the stack
void Push(int element) {
 if (top == MAX_SIZE - 1) {
     printf("Stack overflow: Cannot push element onto a full stack\n");
     return; // Handle overflow (stack is full)
 }
 top++;
 stack[top] = element;
}


// Function to pop an element from the stack
int Pop() {
 if (top == -1) {
     printf("Stack underflow: Cannot pop element from an empty stack\n");
 return -1; // Handle underflow (stack is empty)
 }
 int element = stack[top];
 top--;
 return element;
}


// Function to peek at the top element of the stack
int Peek() {
 if (top == -1) {
     printf("Stack is empty Underflow!\n");
     return -1; // Handle underflow (stack is empty)
 }
 return stack[top];
}


// Function to check if the stack is empty
bool IsEmpty() {
 return (top == -1);
}
void Display()
{ int i;
 if(IsEmpty()) printf("Stack is empty Under flow!\n");
 else
 {
     printf("Stack contents are\n");
     for(i=top;i>=0;i--)
     printf("%d\n",stack[i]);
 }
}
int main() {
int item, choice;
printf("\t\t\tImplementation Of Stack ");

do {

printf("\n\n1.Push\n2.Pop\n3.Peek\n4.Display\n5.exit\n");
printf("\nEnter Your Choice :: ");
scanf("%d", &choice);
switch (choice) {
case 1:
     printf("\nEnter The item to be pushed :: ");
     scanf("%d", &item);
     Push(item);
     break;
case 2:
     if (IsEmpty())
     printf("\nEmpty stack!Underflow !!");
     else {
     item = Pop();
     printf("\nThe popped element is %d", item);
     }
     break;
case 3:
     if (IsEmpty())
     printf("\nEmpty stack!Underflow !!");
     else {
     item = Peek();
     printf("\nThe Top element is %d", item);
     }
     break;
case 4:
     Display();
     break;
case 5:
     exit(0);
    }
} while (1);
return 0;
}

Complexity Analysis:

Push, Pop, Peek, and IsEmpty operations in a stack typically have a time complexity of O(1) when implemented using an array or linked list.

Use Cases:(Applications)

Function Call Stack: Stacks are crucial in programming languages for managing function calls and maintaining the order of execution.

Expression Evaluation: Stacks are used to evaluate mathematical expressions, such as converting infix expressions to postfix (RPN) or solving equations

Undo/Redo Functionality: Stacks are used to implement undo and redo functionality in applications like text editors.

Backtracking Algorithms: Stacks help in backtracking algorithms like depth-first search (DFS).


In summary, a stack is a simple yet powerful data structure that follows the Last-In, First-Out (LIFO) principle. It is widely used in computer science and programming for managing data and controlling the flow of execution in various applications. Understanding how to use stacks effectively is essential for any programmer or computer scientist.