Stack Operations: Insertion
& Deletion
Presenters:
1. MUHAMMAD RAYAN (CSC 25 S 618)
2. GHULAM AHMED (CSC 25 S 623)
3. ZOHAIR ZANZIBAR (CSC 25 S 638)
Course Instructor
Sir Ameen Khwaja
Sub-Topic 1 — What is a Stack?
Definition
A stack is a linear abstract data type that follows Last-In,
First- Out (LIFO). Elements are added and removed from the
top only.
● Primary operations: push (insert), pop (remove), peek (top)
● Use cases: function call stacks, undo functionality, expression
evaluation
Stack — Insertion (Push):
Concept
Push adds an element to the top of the stack.
If stack uses an array, check for overflow; if
linked list, allocate a new node and link it as
the new top.
Keep operations O(1) in time if implemented properly.
Push — Code Example (Array
Implementation) • top starts at -1 for an empty stack
• Check capacity to avoid overflow
void push(int stack[], int &top, int capacity, int value) • Time complexity: O(1)
{
// Check for Stack Overflow
if (top == capacity - 1)
{
printf("Stack Overflow\n");
return;
}
// Increment top
top = top + 1;
// Insert value at the top position
stack[top] = value;
}
Sub-Topic 2 — Deletion
(Pop): Concept
Pop removes and returns the top element. If stack is
empty, handle underflow. For linked list stacks, detach
the head node and free memory.
Always check for empty stack before popping to avoid runtime errors.
Pop — Code Example (Array Implementation)
Example
Given stack [2, 4, 7] with top at index 2, pop returns 7 and top becomes 1. After pop, stack logically is
[2, 4].
int pop(int stack[], int &top)
{
if (top = = -1)
{
// Underflow
printf("Stack Underflow\n");
return INT_MIN;
}
int value = stack[top];
top = top - 1;
return value;
}
Sub-Topic 3 — Best Case Analysis
Best Case Time Complexity
For both push and pop, the best-case time is O(1). This
occurs when memory operations and boundary checks
succeed immediately (no resizing needed).
● Array stack: O(1) if capacity is available
● Linked list stack: O(1) — single pointer update
Worst Case Analysis
Worst Case Time Complexity
Push can be O(n) in worst case if the array-backed stack
needs resizing (e.g., dynamic array doubling). Pop remains
O(1). Memory allocation failures or heavy garbage
collection can also degrade performance.
● Array resizing during push: O(n) for that operation
(amortized O(1)
overall)
● Linked list: worst-case still O(1) for push/pop
Summary
When to Use Which Implementation
Array-based Stack
Simple, low overhead, fixed capacity or dynamic resizing. Good when max size known or
amortized performance acceptable.
Linked-list Stack
Flexible size, no resizing cost. Preferred when unpredictable or large sizes and frequent
allocations are acceptable.
Key Take aways Push/pop are O(1) typically. Watch for array resizing (push worst-case
O(n)). Always handle overflow/underflow.
Real-World Applications
Stacks power many everyday features and core programming techniques.
Browser Back Button Undo / Redo Function Call Stack Expression Evaluation
Applications keep track of Programming languages use
Recently visited pages are actions in order, making it a call stack to manage active Stacks help convert infix to
stored so users can move easy to reverse or reapply functions, local variables, and postfix and evaluate
backward through their changes. return points. expressions efficiently.
browsing history.
Depth-First Search
DFS uses a stack, either explicitly or through recursion, to explore paths deeply before backtracking.