Data Structures — mr. TEA

Stack (LIFO)

A stack is a Last-In, First-Out (LIFO) structure. The last item added is the first one removed — like a stack of plates.

Operation	Description	Example
PUSH	Add item to the top	Push(5) — adds 5 on top
POP	Remove & return item from the top	Pop() — removes top item
PEEK / TOP	View top item without removing	Peek() — returns top value
isEmpty	Check if stack is empty	Returns true/false
isFull	Check if stack is full (for fixed-size)	Returns true/false

✓ Trace: Stack Operations

Stack (max size 5), Top pointer starts at -1

Operation        Stack State (bottom→top)     Top
─────────        ────────────────────────     ───
PUSH(10)         [10]                          0
PUSH(20)         [10, 20]                      1
PUSH(30)         [10, 20, 30]                  2
POP()  → 30      [10, 20]                      1
PUSH(40)         [10, 20, 40]                  2
PEEK() → 40      [10, 20, 40]                  2  (unchanged)
POP()  → 40      [10, 20]                      1
POP()  → 20      [10]                          0
POP()  → 10      []                           -1
POP()  → ERROR!  Stack underflow              -1

Real-World Uses

Undo/Redo in text editors — each action is pushed; undo = pop
Function call stack — CPU tracks return addresses
Expression evaluation — converting infix to postfix
Backtracking — maze solving, browser back button

Pseudocode Implementation

CONSTANT MaxSize = 100
DECLARE Stack : ARRAY[0:MaxSize-1] OF INTEGER
DECLARE Top : INTEGER
Top ← -1

PROCEDURE Push(value : INTEGER)
  IF Top >= MaxSize - 1 THEN
    OUTPUT "Stack overflow"
  ELSE
    Top ← Top + 1
    Stack[Top] ← value
  ENDIF
ENDPROCEDURE

FUNCTION Pop() RETURNS INTEGER
  IF Top < 0 THEN
    OUTPUT "Stack underflow"
    RETURN -1
  ELSE
    value ← Stack[Top]
    Top ← Top - 1
    RETURN value
  ENDIF
ENDFUNCTION

C++ Implementation

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int stack[MAX_SIZE];
int top = -1;

void push(int value) {
    if (top >= MAX_SIZE - 1) {
        cout << "Stack overflow!" << endl;
    } else {
        top++;
        stack[top] = value;
    }
}

int pop() {
    if (top < 0) {
        cout << "Stack underflow!" << endl;
        return -1;
    } else {
        int value = stack[top];
        top--;
        return value;
    }
}

int peek() {
    if (top < 0) {
        cout << "Stack is empty!" << endl;
        return -1;
    }
    return stack[top];
}

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

int main() {
    push(10);
    push(20);
    push(30);
    cout << "Top: " << peek() << endl;    // 30
    cout << "Pop: " << pop() << endl;     // 30
    cout << "Pop: " << pop() << endl;     // 20
    return 0;
}

Queue (FIFO)

A queue is a First-In, First-Out (FIFO) structure. The first item added is the first removed — like a queue of people at a shop.

Operation	Description
ENQUEUE	Add item to the rear (back)
DEQUEUE	Remove & return item from the front
PEEK / FRONT	View front item without removing
isEmpty	Check if queue is empty
isFull	Check if queue is full

✓ Trace: Queue Operations

Queue (max size 5), Front=0, Rear=-1

Operation           Queue State (front→rear)   Front  Rear
─────────           ────────────────────────   ─────  ────
ENQUEUE(10)         [10]                        0      0
ENQUEUE(20)         [10, 20]                    0      1
ENQUEUE(30)         [10, 20, 30]                0      2
DEQUEUE() → 10      [20, 30]                    1      2
DEQUEUE() → 20      [30]                        2      2
ENQUEUE(40)         [30, 40]                    2      3
DEQUEUE() → 30      [40]                        3      3

Circular Queue

A circular queue wraps around — when the rear reaches the end of the array, it loops back to the start. This avoids wasting space at the front after dequeuing.

Rear = (Rear + 1) MOD MaxSize     // Wrap around
Front = (Front + 1) MOD MaxSize   // Wrap around

Real-World Uses

Print queue — documents printed in order received
CPU scheduling — processes wait in a queue
Message queues — network packets, chat messages
Breadth-first search — graph/tree traversal

C++ Implementation

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int queue[MAX_SIZE];
int front = 0, rear = -1, count = 0;

void enqueue(int value) {
    if (count >= MAX_SIZE) {
        cout << "Queue overflow!" << endl;
    } else {
        rear = (rear + 1) % MAX_SIZE;  // Circular wrap
        queue[rear] = value;
        count++;
    }
}

int dequeue() {
    if (count == 0) {
        cout << "Queue underflow!" << endl;
        return -1;
    } else {
        int value = queue[front];
        front = (front + 1) % MAX_SIZE;  // Circular wrap
        count--;
        return value;
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    cout << "Dequeue: " << dequeue() << endl;  // 10
    cout << "Dequeue: " << dequeue() << endl;  // 20
    return 0;
}

Binary Tree

A binary tree is a hierarchical data structure where each node has at most two children (left and right). A Binary Search Tree (BST) adds an ordering rule: left child < parent < right child.

Term	Definition
Root	Top node of the tree (no parent)
Parent	A node that has children
Child	A node connected below a parent
Leaf	A node with no children
Subtree	A node and all its descendants
Height / Depth	Number of edges from root to deepest leaf

✓ Building a BST: Insert 50, 30, 70, 20, 40, 60, 80

Insert 50:     50         (root)
Insert 30:     50         (30 < 50 → go left)
              /
            30
Insert 70:     50         (70 > 50 → go right)
              / \
            30   70
Insert 20:     50         (20 < 50 → left, 20 < 30 → left)
              / \
            30   70
           /
         20
Insert 40:     50         (40 < 50 → left, 40 > 30 → right)
              / \
            30   70
           / \
         20   40
Insert 60:     50
              / \
            30   70
           / \  /
         20  40 60
Insert 80:     50
              / \
            30   70
           / \  / \
         20  40 60 80

Tree Traversals

Traversal	Order	Mnemonic	Result (for tree above)
In-order	Left → Root → Right	L-N-R	20, 30, 40, 50, 60, 70, 80
Pre-order	Root → Left → Right	N-L-R	50, 30, 20, 40, 70, 60, 80
Post-order	Left → Right → Root	L-R-N	20, 40, 30, 60, 80, 70, 50

Key Fact

In-order traversal of a BST always gives values in ascending order. This is a common exam question.

C++ Implementation (BST)

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->left = nullptr;
    newNode->right = nullptr;
    return newNode;
}

Node* insert(Node* root, int value) {
    if (root == nullptr) {
        return createNode(value);
    }
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }
    return root;
}

// In-order traversal: Left → Node → Right
void inOrder(Node* root) {
    if (root == nullptr) return;
    inOrder(root->left);
    cout << root->data << " ";
    inOrder(root->right);
}

// Pre-order traversal: Node → Left → Right
void preOrder(Node* root) {
    if (root == nullptr) return;
    cout << root->data << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// Post-order traversal: Left → Right → Node
void postOrder(Node* root) {
    if (root == nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->data << " ";
}

// Search for a value
bool search(Node* root, int value) {
    if (root == nullptr) return false;
    if (root->data == value) return true;
    if (value < root->data) return search(root->left, value);
    return search(root->right, value);
}

int main() {
    Node* root = nullptr;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    cout << "In-order:   "; inOrder(root);   cout << endl;
    cout << "Pre-order:  "; preOrder(root);  cout << endl;
    cout << "Post-order: "; postOrder(root); cout << endl;

    cout << "Search 40: " << (search(root, 40) ? "Found" : "Not found") << endl;
    return 0;
}

Stack vs Queue vs Binary Tree

Feature	Stack	Queue	Binary Tree
Order	LIFO	FIFO	Hierarchical / sorted
Insert	Push (top)	Enqueue (rear)	Insert (correct position)
Remove	Pop (top)	Dequeue (front)	Delete (maintain structure)
Access	Top only	Front only	Traverse (in/pre/post order)
Search	O(n) — must pop through	O(n) — must dequeue through	O(log n) for balanced BST
Use case	Undo, recursion	Scheduling, printing	Sorted data, searching

Pitfalls & Common Errors

Confusing LIFO and FIFO

Stack = LIFO (Last In First Out). Queue = FIFO (First In First Out). Read the question carefully — many students mix these up under exam pressure.

Forgetting Stack/Queue Overflow/Underflow

Always check for overflow (push/enqueue when full) and underflow (pop/dequeue when empty). Forgetting these checks loses marks.

Getting Traversal Orders Wrong

Use the mnemonic: In=LNR, Pre=NLR, Post=LRN. The name tells you where N (Node/root) goes.

Pro-Tips for Exams

Data Structure Strategy

For trace tables: draw the structure after each operation — examiners want to see the state
Always mention error handling: what happens if you pop an empty stack?
BST in-order = sorted order — state this fact explicitly in BST questions
For circular queue: always use the MOD formula and explain why it wraps
When asked about a "suitable data structure" — justify with the ordering property (LIFO/FIFO/sorted)

Graded Tasks

Remember

Define: LIFO, FIFO, push, pop, enqueue, dequeue, root, leaf, in-order traversal.

Apply

Trace: Start with an empty stack. Perform: PUSH(5), PUSH(10), PUSH(15), POP(), PUSH(20), PEEK(), POP(), POP(). Show the stack state after each operation.

Apply

Build a BST by inserting these values in order: 45, 25, 65, 15, 35, 55, 75. Draw the tree and perform in-order, pre-order, and post-order traversals.

Apply

Write pseudocode for a circular queue's enqueue and dequeue operations.

Analyze

A text editor needs an undo feature. Explain why a stack is a more appropriate data structure than a queue for this purpose.

Self-Check Quiz

1. What does LIFO stand for?

Click to reveal: Last In, First Out.

2. What happens when you pop an empty stack?

Click to reveal: Stack underflow — an error because there are no items to remove.

3. What traversal gives BST values in ascending order?

Click to reveal: In-order traversal (Left → Node → Right).

4. What is the advantage of a circular queue over a linear queue?

Click to reveal: A circular queue reuses empty spaces at the front after dequeuing, preventing wasted space.

5. Where are new nodes inserted in a BST?

Click to reveal: If the value is less than the current node → go left. If greater → go right. Repeat until an empty position is found.

Data Structures: Stack, Queue & Binary Tree

Learning Objectives

Lesson Presentation

Stack (LIFO)

✓ Trace: Stack Operations

Real-World Uses

Pseudocode Implementation

C++ Implementation

Queue (FIFO)

✓ Trace: Queue Operations

Circular Queue

Real-World Uses

C++ Implementation

Binary Tree

✓ Building a BST: Insert 50, 30, 70, 20, 40, 60, 80

Tree Traversals

Key Fact

C++ Implementation (BST)

Stack vs Queue vs Binary Tree

Pitfalls & Common Errors

Confusing LIFO and FIFO

Forgetting Stack/Queue Overflow/Underflow

Getting Traversal Orders Wrong

Pro-Tips for Exams

Data Structure Strategy

Graded Tasks

Self-Check Quiz