Stack Data Structure

A Stack is a linear data structure that follows a particular order in which the
operations are performed. The order may be LIFO(Last In First
Out) or FILO(First In Last Out). LIFO implies that the element that is
inserted last, comes out first and FILO implies that the element that is
inserted first, comes out last.
It behaves like a stack of plates, where the last plate added is the first one to
be removed. Think of it this way:
Pushing an element onto the stack is like adding a new plate on top.
Popping an element removes the top plate from the stack.

LIFO(Last In First Out) Principle

The LIFO principle means that the last element added to a stack is the first
one to be removed.
 New elements are always pushed on top.
 Removal (pop) also happens only from the top.
 This ensures a strict order: last in → first out.
Real-world examples of LIFO:
 Stack of plates – The last plate placed on top is the first one you pick up.
 Shuttlecock box – The last shuttlecock inserted is the first one taken out,
since both operations happen from the same end.
Basic Terminologies of Stack
 Top: The position of the most recently inserted element. Insertions (push)
and deletions (pop) are always performed at the top.
 Size: Refers to the current number of elements present in the stack.
Types of Stack:
Fixed Size Stack
 A fixed size stack has a predefined capacity.
 Once it becomes full, no more elements can be added (this
causes overflow).
 If the stack is empty and we try to remove an element, it
causes underflow.
 Typically implemented using a static array.
Example: Declaring a stack of size 10 using an array.
Dynamic Size Stack
 A dynamic size stack can grow and shrink automatically as needed.
 If the stack is full, its capacity expands to allow more elements.
 As elements are removed, memory usage can shrink as well.
 Can be implemented using:
-> Linked List → grows/shrinks naturally.
-> Dynamic Array (like vector in C++ or ArrayList in Java) → resizes
automatically.
Example: Stack implementation using linked list or resizable array.
Note: We generally use dynamic stacks in practice, as they can grow or
shrink as needed without overflow issues.
Common Operations on Stack:
In order to make manipulations in a stack, there are certain operations
provided to us.
 push() to insert an element into the stack.
 pop() to remove an element from the stack.
 top() Returns the top element of the stack.
 isEmpty() returns true if stack is empty else false.
 size() returns the size of the stack.

Basic Stack Operations

1. Push (Insert)

 Definition: Adds (pushes) an element onto the top of the stack.

 Conditions:
o If the stack is full → Overflow condition.
 Time Complexity: O(1)
 Example:
 Stack: [10, 20]
 push(30) → [10, 20, 30]

2. Pop (Remove)

 Definition: Removes (pops) the top element from the stack.

 Conditions:
o If the stack is empty → Underflow condition.
  Time Complexity: O(1)
 Example:
 Stack: [10, 20, 30]
 pop() → returns 30, stack becomes [10, 20]

3. Peek (Top)

 Definition: Returns the top element without removing it.

 Conditions:
o If the stack is empty → return error / NULL.
 Time Complexity: O(1)
 Example:
 Stack: [10, 20, 30]
 peek() → returns 30 (stack remains unchanged)

4. isEmpty

 Definition: Checks whether the stack is empty.

 Returns: True if empty, False otherwise.
 Time Complexity: O(1)

5. isFull (for array-based stack)

 Definition: Checks whether the stack is full.

 Returns: True if full, False otherwise.
 Time Complexity: O(1)

6. Display (Optional Utility)

 Definition: Prints all elements in the stack (top → bottom).

 Example:
 Stack: [10, 20, 30]
 display() → 30 20 10

Summary Table
Operation Purpose Condition Example (Stack = [10,20,30])

Push(x) Insert element on top Overflow if full push(40) → [10,20,30,40]

Operation Purpose Condition Example (Stack = [10,20,30])

Pop() Remove element from top Underflow if empty pop() → returns 30 → [10,20]

Peek() View top element Error if empty peek() → 30

isEmpty() Check if stack is empty — returns False

isFull() Check if stack is full (array) — returns True if max reached

Display() Print all elements (top → bottom) — prints 30 20 10

Stack using ArrayStack is a linear data structure which

follows LIFO principle. To implement a stack using an array, initialize an
array and treat its end as the stack’s top. Implement push (add to
end), pop (remove from end), and peek (check end) operations, handling
cases for an empty or full stack.
Step-by-step approach:
1. Initialize an array to represent the stack.
2. Use the end of the array to represent the top of the stack.
3. Implement push (add to end), pop (remove from the end),
and peek (check end) operations, ensuring to handle empty and full stack
conditions.
Here are the following operations of implement stack using array:
Push Operation in Stack:
Adds an item to the stack. If the stack is full, then it is said to be an Overflow
condition.
 Before pushing the element to the stack, we check if the stack is full .
 If the stack is full (top == capacity-1) , then Stack Overflows and we
cannot insert the element to the stack.
 Otherwise, we increment the value of top by 1 (top = top + 1) and the
new value is inserted at top position .
 The elements can be pushed into the stack till we reach the capacity of
the stack.
Pop Operation in Stack:
Removes an item from the stack. The items are popped in the reversed order
in which they are pushed. If the stack is empty, then it is said to be
an Underflow condition.
 Before popping the 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 any element from the stack.
 Otherwise, we store the value at top, decrement the value of top by 1 (top
= top – 1) and return the stored top value.
Top or Peek Operation in Stack:
Returns the top element of the stack.
 Before returning the top element from the stack, we check if the stack is
empty.
 If the stack is empty (top == -1), we simply print “Stack is empty”.
 Otherwise, we return the element stored at index = top .
isEmpty Operation in Stack:
Returns true if the stack is empty, else false.=
 Check for the value of top in stack.
 If (top == -1) , then the stack is empty so return true .
 Otherwise, the stack is not empty so return false .
isFull Operation in Stack :
Returns true if the stack is full, else false.
 Check for the value of top in stack.
 If (top == capacity-1), then the stack is full so return true .
 Otherwise, the stack is not full so return false.
Implementation using Fixed Sized Array
In this implementation, we use a fixed sized array. We take capacity as
argument when we create a stack. We create an array with size equal to
given capacity. If number of elements go beyond capacity, we throw an
overflow error.

#include <iostream>

using namespace std;

#define MAX 5 // Maximum size of stack

class Stack {

int arr[MAX]; // Array to hold stack elements

int top; // Index of the top element

public:
// Constructor

Stack() {

top = -1; // Stack initially empty

// Push operation: insert element at top

void push(int x) {

if (top == MAX - 1) {

cout << "Stack Overflow! Cannot push " << x << endl;

return;

arr[++top] = x;

cout << x << " pushed into stack.\n";

// Pop operation: remove top element

void pop() {

if (top == -1) {

cout << "Stack Underflow! Cannot pop.\n";

return;

cout << arr[top--] << " popped from stack.\n";

}

// Peek operation: view top element

void peek() {

if (top == -1) {

cout << "Stack is empty.\n";

return;

cout << "Top element: " << arr[top] << endl;

// Display operation: show all elements

void display() {

if (top == -1) {

cout << "Stack is empty.\n";

return;

cout << "Stack elements: ";

for (int i = top; i >= 0; i--) {

cout << arr[i] << " ";

cout << endl;

 }

};

// Main function

int main() {

Stack s;

s.push(10);

s.push(20);

s.push(30);

s.display();

s.peek();

s.pop();

s.display();

s.push(40);

s.push(50);

s.push(60); // Will show overflow

s.display();

return 0;
}

 Stack is represented by an array arr[MAX].

 top keeps track of the index of the last inserted element.

 top = -1 → stack is empty.

 top = MAX-1 → stack is full.

 Operations implemented:

 push(x) → Insert element.

 pop() → Remove top element.
 peek() → View top element.
 display() → Show all elements.

Dry Run of Stack (Using Array)

Initial state:

 top = -1 → Stack is empty.

Operation 1: s.push(10);

 top = -1 → 0
 arr[0] = 10
 Stack: [10]

Output:

10 pushed into stack.

Operation 2: s.push(20);

 top = 0 → 1
 arr[1] = 20
 Stack: [10, 20]

Output:

20 pushed into stack.

Operation 3: s.push(30);

 top = 1 → 2
 arr[2] = 30
 Stack: [10, 20, 30]

Output:

30 pushed into stack.

Operation 4: s.display();

Stack elements are printed from top to bottom:

 30 20 10

Output:

Stack elements: 30 20 10

Operation 5: s.peek();

 Top element = arr[2] = 30

Output:

Top element: 30

Operation 6: s.pop();

 Element removed = arr[2] = 30

 top = 2 → 1
 Stack: [10, 20]

Output:

30 popped from stack.

Operation 7: s.display();

 Stack elements = 20 10

Output:
Stack elements: 20 10

Operation 8: s.push(40);

 top = 1 → 2
 arr[2] = 40
 Stack: [10, 20, 40]

Output:

40 pushed into stack.

Operation 9: s.push(50);

 top = 2 → 3
 arr[3] = 50
 Stack: [10, 20, 40, 50]

Output:

50 pushed into stack.

Operation 10: s.push(60);

 top = 3 → 4
 arr[4] = 60
 Stack: [10, 20, 40, 50, 60]

Output:

60 pushed into stack.

Operation 11: s.push(70);

 top = 4 (already full, since MAX = 5)

 Stack Overflow occurs.

Output:

Stack Overflow! Cannot push 70

Final s.display();

 Elements = 60 50 40 20 10
Output:

Stack elements: 60 50 40 20 10

 Push adds items to the top until overflow.

 Pop removes items from the top until underflow.

 Peek shows the top element.

 Display shows the full stack from top → bottom.

Task: implement it in python or with classes

Stack - Linked List Implementation
A stack is a linear data structure that follows the Last-In-First-Out
(LIFO) principle. It can be implemented using a linked list, where each
element of the stack is represented as a node. The head of the linked list
acts as the top of the stack.
Declaration of Stack using Linked List
A stack can be implemented using a linked list where we maintain:
 A Node structure/class that contains:
data → to store the element.
next → pointer/reference to the next node in the stack.
 A pointer/reference top that always points to the current top node of the
stack.
Initially, top = null to represent an empty stack.

# Node structure in python

class Node:

def __init__(self, x):

self.data = x

self.next = None

# Stack class
class myStack:

def __init__(self):

# initially stack is empty

self.top = None
Operations on Stack using Linked List
Push Operation
Adds an item to the stack. Unlike array implementation, there is no fixed
capacity in linked list. Overflow occurs only when memory is exhausted.
 A new node is created with the given value.
 The new node’s next pointer is set to the current top.
 The top pointer is updated to point to this new node.

def push(self, x):

temp = Node(x)

temp.next = self.top

self.top = temp
Pop Operation
Removes the top item from the stack. If the stack is empty, it is said to be
an Underflow condition.
 Before deleting, we check if the stack is empty (top == NULL).
 If the stack is empty, underflow occurs and deletion is not possible.
 Otherwise, we store the current top node in a temporary pointer.
 Move the top pointer to the next node.
 Delete the temporary node to free memory.

Peek (or Top) Operation

Returns the value of the top item without removing it from the stack.
 If the stack is empty (top == NULL), then no element exists.
 Otherwise, simply return the data of the node pointed by top.
isEmpty Operation
Checks whether the stack has no elements.
 If the top pointer is NULL, it means the stack is empty and the function
returns true.
 Otherwise, it returns false.

Stack Implementation using Linked List in c++

#include <iostream>

using namespace std;

// Node structure

class Node {

public:

int data;

Node* next;

Node(int x) {

data = x;

next = NULL;

}
};

// Stack implementation using linked list

class myStack {

Node* top;

// To Store current size of stack

int count;

public:

myStack() {

// initially stack is empty

top = NULL;

count = 0;

// push operation

void push(int x) {

Node* temp = new Node(x);

temp->next = top;

top = temp;
 count++;

// pop operation

int pop() {

if (top == NULL) {

cout << "Stack Underflow" << endl;

return -1;

Node* temp = top;

top = top->next;

int val = temp->data;

count--;

delete temp;

return val;

// peek operation

int peek() {

if (top == NULL) {
 cout << "Stack is Empty" << endl;

return -1;

return top->data;

Dry Run of Linked List Stack

Initial State

 top = NULL
 count = 0
 Stack is empty.

Operation 1: st.push(1);

 Create new node → data = 1

 temp->next = NULL (since top = NULL)
 top = temp
 count = 1

Stack (top → bottom): 1

Operation 2: st.push(2);

 Create new node → data = 2

 temp->next = top (1)
 top = temp
 count = 2

Stack: 2 → 1

Operation 3: st.push(3);

 Create new node → data = 3

  temp->next = top (2)
 top = temp
 count = 3

Stack: 3 → 2 → 1

Operation 4: st.push(4);

 Create new node → data = 4

 temp->next = top (3)
 top = temp
 count = 4

Stack: 4 → 3 → 2 → 1

Operation 5: st.pop();

 top = 4
 Remove node with data = 4
 top = 3
 count = 3

Output:

Popped: 4

Stack: 3 → 2 → 1

Operation 6: st.peek();

 top = 3
 Return data = 3

Output:

Top element: 3

Operation 7: st.isEmpty();

 top != NULL → Stack is not empty

Output:

Is stack empty: No

Operation 8: st.size();

 count = 3

Output:

Current size: 3

Final Output of Program

Popped: 4
Top element: 3
Is stack empty: No
Current size: 3

✅ So the stack evolved like this:

1 → 2 → 3 → 4 → (pop 4) → 3 → 2 → 1

// check if stack is empty

bool isEmpty() {

return top == NULL;

// size of stack

int size() {

return count;

}
};

int main() {

myStack st;

// pushing elements

st.push(1);

st.push(2);

st.push(3);

st.push(4);

// popping one element

cout << "Popped: " << st.pop() << endl;

// checking top element

cout << "Top element: " << st.peek() << endl;

// checking if stack is empty

cout << "Is stack empty: " << (st.isEmpty() ? "Yes" : "No") << endl;

// checking current size

cout << "Current size: " << st.size() << endl;

 return 0;

Output of Program

Dry Run Table

Operation Top Element Count Stack (top → bottom)
Initial State NULL 0 (empty)
push(1) 1 1 1
push(2) 2 2 2→1
push(3) 3 3 3→2→1
push(4) 4 4 4→3→2→1
pop() → removes 4 3 3 3→2→1
peek() → returns 3 3 3 3→2→1
isEmpty() → No 3 3 3→2→1
size() → 3 3 3 3→2→1

Final Output
Popped: 4
Top element: 3
Is stack empty: No
Current size: 3

Stack Implementation using Deque

A doubly ended queue or deque allows insertion and deletion at both ends.
In a stack, we need to do insertions and deletions at one end only. We can
use either end of deque (front or back) to implement a stack,
In the below implementation, we use back (or rear) of stack to do both
insertions and deletions. Please note that the time complexities of all the
operations (insertions and deletions at both ends) in a deque is O(1). So the
time complexity of the below implementation is O(1) only.
 In Java, the deque implementation of stack is preferred over standard
Stack class, because the standard Stack class is legacy class and mainly
designed for multi threaded environment.
 In Python, there is no standard stack class, so we can either use list or
deque. The deque implementation is preferred because it is optimized for
insertion and deletion at ends.
#include <iostream>

#include <deque>

using namespace std;

int main() {

deque<int> stack;

stack.push_back(10);

stack.push_back(20);

stack.push_back(30);

cout << stack.back() << " popped from deque" << endl;

stack.pop_back();

cout << "Top element is: " << stack.back() << endl;
 return 0;