Data Structures: Stacks, Queues, Linked Lists and Binary Trees, ISC Class 12 Computer Science

What Data Structures is about

Weightage: CISCE publishes no chapter or unit weightage for ISC Computer Science. Data Structures is part of Section C, 13 of the 2027 syllabus and can be asked anywhere in the 70-mark Paper 1 (Part I compulsory: ten 1-mark items and a 10-mark short-answer question; Part II: two of three 10-mark questions in each of Sections A and B, and two of three 5-mark questions in Section C).Source: CISCE ISC Computer Science (868) syllabus, examination year 2027; latest Paper 1 specimen (2025) and the 2025 board paper

Key concepts

Stack (LIFO) as an abstract data type

A stack is a linear structure in which insertion (push) and deletion (pop) happen at one end, the top: last in, first out (LIFO).

Array implementation with top = -1 for an empty stack:

• push(v): if top == cap - 1 → overflow; else st[++top] = v.
• pop( ): if top == -1 → underflow (return a sentinel such as -9999); else return st[top--].
• peek( ): st[top] without removing. isEmpty( ): top == -1.

If top starts at 0 instead, the conditions change (full when top == cap, empty when top == 0, and pushes use st[top++]); always match the conditions to the initial value of top.

Abstract data type through an interface: declare the operations in an interface (IntStack with push, pop, isEmpty); any class that implements it (array-based, linked-list-based) can be used interchangeably.

// A stack defined as an abstract data type through an interface, with an array implementation.
interface IntStack
{
    void push(int v);
    int pop();          // returns -9999 if empty
    boolean isEmpty();
}

class ArrayStack implements IntStack
{
    int[] st;
    int cap, top;

    ArrayStack(int c)
    {
        cap = c;
        st = new int[cap];
        top = -1;                       // empty stack
    }

    public void push(int v)
    {
        if (top == cap - 1)
            System.out.println("STACK OVERFLOW");
        else
            st[++top] = v;              // move top up, then store
    }

    public int pop()
    {
        if (top == -1)
            return -9999;               // underflow
        return st[top--];               // return, then move top down
    }

    public boolean isEmpty()
    {
        return top == -1;
    }

    void display()
    {
        for (int i = top; i >= 0; i--)
            System.out.print(st[i] + " ");
        System.out.println("(top first)");
    }
}

public class Stacks
{
    public static void main(String[] args)
    {
        ArrayStack s = new ArrayStack(3);
        s.push(10);
        s.push(20);
        s.push(30);
        s.push(40);                     // fourth push: overflow
        s.display();
        System.out.println("popped " + s.pop() + ", popped " + s.pop());
        s.display();
        System.out.println("popped " + s.pop() + ", popped " + s.pop());
        System.out.println("empty? " + s.isEmpty());
    }
}

Output:

STACK OVERFLOW
30 20 10 (top first)
popped 30, popped 20
10 (top first)
popped 10, popped -9999
empty? true

Applications: function calls and recursion (the call stack), undo in editors, back button in browsers, expression evaluation and conversion, bracket matching, reversing.

Worked example

[2] A stack of capacity 3 starts empty with top = -1. Show top and the contents after push(10), push(20), pop( ), push(30), push(40), push(50). (Apply)

Try it first, then show the solutionSolution

1. push 10 (top 0), push 20 (top 1), pop returns 20 (top 0), push 30 (top 1), push 40 (top 2) - 1 mark.
2. push 50: top == cap - 1, so overflow; final contents 10 30 40 (bottom to top), top = 2 - 1 mark.

Answer: Final stack (bottom to top): 10, 30, 40 with top = 2; the last push reports overflow.

Queue, circular queue and dequeue

Queue: insertion at the rear and deletion at the front: first in, first out (FIFO). Uses: printer jobs, CPU scheduling, call-centre lines, buffering.
Linear array queue (front = 0, rear = -1): insert at q[++rear]; delete from q[front++]; empty when front > rear. Problem: once rear reaches the end, the queue reports full even if earlier slots have been freed.

Circular queue: the array is treated as a circle so freed slots are reused: index moves with (index + 1) % cap.
With front = rear = 0 (one slot kept empty):

• push(v): if (rear + 1) % cap == front → full; else rear = (rear + 1) % cap; Q[rear] = v.
• remove( ): if front == rear → empty (return -999); else front = (front + 1) % cap; return Q[front].

So a circular queue of capacity n holds at most n - 1 items in this scheme. Applications: CPU round-robin scheduling, memory buffers, traffic signal cycles, streaming buffers.

Dequeue (double-ended queue): insertion and deletion at both ends (addFront, addRear, popFront, popRear). It can act as both a stack and a queue. Input-restricted (insert at one end only) and output-restricted variants exist.

// Linear queue, circular queue and double-ended queue (dequeue) using arrays.
class LinQueue
{
    int[] q;
    int cap, front, rear;

    LinQueue(int c)
    {
        cap = c;
        q = new int[cap];
        front = 0;
        rear = -1;                          // empty when front > rear
    }

    void insert(int v)
    {
        if (rear == cap - 1)
            System.out.println("QUEUE FULL");
        else
            q[++rear] = v;
    }

    int delete()
    {
        if (front > rear)
            return -999;
        return q[front++];
    }
}

class CirQ
{
    int[] q;
    int cap, front, rear;                   // front and rear start at 0; one slot is kept empty

    CirQ(int c)
    {
        cap = c;
        q = new int[cap];
        front = 0;
        rear = 0;
    }

    void push(int v)
    {
        if ((rear + 1) % cap == front)
            System.out.println("CIRCULAR QUEUE FULL");
        else
        {
            rear = (rear + 1) % cap;        // wrap round to index 0 after the last slot
            q[rear] = v;
        }
    }

    int remove()
    {
        if (front == rear)
            return -999;                    // empty
        front = (front + 1) % cap;
        return q[front];
    }
}

class Deq
{
    int[] d;
    int cap, front, rear;                   // linear dequeue: elements in d[front..rear]

    Deq(int c)
    {
        cap = c;
        d = new int[cap];
        front = c / 2;
        rear = front - 1;                   // start in the middle so both ends can grow
    }

    void addFront(int v)
    {
        if (front == 0)
            System.out.println("NO SPACE AT FRONT");
        else
            d[--front] = v;
    }

    void addRear(int v)
    {
        if (rear == cap - 1)
            System.out.println("NO SPACE AT REAR");
        else
            d[++rear] = v;
    }

    int popFront()
    {
        if (front > rear)
            return -999;
        return d[front++];
    }

    int popRear()
    {
        if (front > rear)
            return -999;
        return d[rear--];
    }
}

public class Queues
{
    public static void main(String[] args)
    {
        LinQueue lq = new LinQueue(3);
        lq.insert(1); lq.insert(2); lq.insert(3);
        System.out.println("linear: " + lq.delete() + " " + lq.delete());
        lq.insert(4);                       // full although two slots were freed
        CirQ cq = new CirQ(4);              // capacity 4 holds at most 3 items
        cq.push(1); cq.push(2); cq.push(3);
        cq.push(4);                         // full
        System.out.println("circular: " + cq.remove() + " " + cq.remove());
        cq.push(5); cq.push(6);             // reuse the freed slots by wrapping round
        System.out.println("circular: " + cq.remove() + " " + cq.remove() + " " + cq.remove() + " " + cq.remove());
        Deq dq = new Deq(6);
        dq.addRear(10); dq.addRear(20); dq.addFront(5); dq.addFront(1);
        System.out.println("dequeue: " + dq.popFront() + " " + dq.popRear() + " " + dq.popFront() + " " + dq.popRear() + " " + dq.popRear());
    }
}

Output:

linear: 1 2
QUEUE FULL
CIRCULAR QUEUE FULL
circular: 1 2
circular: 3 5 6 -999
dequeue: 1 20 5 10 -999

The linear queue reports full after two deletions; the circular queue reuses those slots by wrapping round.

Worked example

[4] Write the methods void push(int v) and int remove( ) for a circular queue Q[ ] of capacity cap with front = rear = 0 initially. (Create)

Try it first, then show the solutionSolution

1. push: if ((rear + 1) % cap == front) print "CIRCULAR QUEUE FULL" - 1 mark.
2. else { rear = (rear + 1) % cap; Q[rear] = v; } - 1 mark.
3. remove: if (front == rear) return -999; - 1 mark.
4. front = (front + 1) % cap; return Q[front]; - 1 mark.

Answer: void push(int v) { if ((rear + 1) % cap == front) System.out.println("CIRCULAR QUEUE FULL"); else { rear = (rear + 1) % cap; Q[rear] = v; } } int remove() { if (front == rear) return -999; front = (front + 1) % cap; return Q[front]; }

Infix, postfix and prefix

Infix: operator between operands (A + B). Postfix (reverse Polish): operator after operands (AB+). Prefix (Polish): operator before operands (+AB). Postfix and prefix need no brackets and no precedence rules, so computers evaluate them easily with a stack.

Manual method (brackets):
1. Fully bracket the infix expression according to precedence (* and / before + and -; equal precedence left to right).
2. Convert the innermost bracket first, moving each operator after (postfix) or before (prefix) its two operands.

Stack method for postfix: scan left to right; operands go to the output; '(' is pushed; on ')' pop to the output until '('; for an operator, pop operators of higher or equal precedence, then push it; at the end pop everything.

Examples (checked by the converter below):
(A + B) * C - D / E → postfix AB+C*DE/- ; prefix -*+ABC/DE
P / (Q - R) * S + T → postfix PQR-/S*T+ ; prefix +*/P-QRST
A - B - C → postfix AB-C- ; prefix --ABC (left to right: (A - B) - C)

// Infix to postfix with an operator stack (single-letter operands; + - * / and brackets),
// and infix to prefix by converting the reversed expression.
public class Convert
{
    static int prec(char op)
    {
        return (op == '*' || op == '/') ? 2 : (op == '+' || op == '-') ? 1 : 0;
    }

    static String toPostfix(String in)
    {
        StringBuilder out = new StringBuilder();
        char[] st = new char[in.length()];
        int top = -1;
        for (char ch : in.toCharArray())
        {
            if (Character.isLetter(ch))
                out.append(ch);
            else if (ch == '(')
                st[++top] = ch;
            else if (ch == ')')
            {
                while (st[top] != '(')
                    out.append(st[top--]);
                top--;                              // discard '('
            }
            else if (ch != ' ')
            {
                // pop operators of higher or EQUAL precedence (left to right)
                while (top >= 0 && prec(st[top]) >= prec(ch))
                    out.append(st[top--]);
                st[++top] = ch;
            }
        }
        while (top >= 0)
            out.append(st[top--]);
        return out.toString();
    }

    static String toPrefix(String in)
    {
        // reverse, swap brackets, convert with "pop only higher" for equal precedence, reverse again
        StringBuilder rev = new StringBuilder();
        for (int i = in.length() - 1; i >= 0; i--)
        {
            char c = in.charAt(i);
            rev.append(c == '(' ? ')' : c == ')' ? '(' : c);
        }
        StringBuilder out = new StringBuilder();
        char[] st = new char[in.length()];
        int top = -1;
        for (char ch : rev.toString().toCharArray())
        {
            if (Character.isLetter(ch))
                out.append(ch);
            else if (ch == '(')
                st[++top] = ch;
            else if (ch == ')')
            {
                while (st[top] != '(')
                    out.append(st[top--]);
                top--;
            }
            else if (ch != ' ')
            {
                while (top >= 0 && prec(st[top]) > prec(ch))
                    out.append(st[top--]);
                st[++top] = ch;
            }
        }
        while (top >= 0)
            out.append(st[top--]);
        return out.reverse().toString();
    }

    public static void main(String[] args)
    {
        String[] e = { "(A + B) * C - D / E", "P / (Q - R) * S + T", "A - B - C", "X * (Y + Z) / W" };
        for (String s : e)
            System.out.println(s + "  ->  postfix " + toPostfix(s) + "   prefix " + toPrefix(s));
    }
}

Output:

(A + B) * C - D / E  ->  postfix AB+C*DE/-   prefix -*+ABC/DE
P / (Q - R) * S + T  ->  postfix PQR-/S*T+   prefix +*/P-QRST
A - B - C  ->  postfix AB-C-   prefix --ABC
X * (Y + Z) / W  ->  postfix XYZ+*W/   prefix /*X+YZW

Worked example

[2] Convert (A + B) * C - D / E to postfix, showing the steps. (Apply)

Try it first, then show the solutionSolution

1. Bracket by precedence: ((A + B) * C) - (D / E); innermost: A + B → AB+, D / E → DE/ - 1 mark.
2. (AB+) * C → AB+C*; then AB+C* - DE/ → AB+C*DE/- - 1 mark.

Answer: AB+C*DE/-

Single linked list

A linked list is a chain of nodes; each node holds data and a reference (link) to the next node; the last node's link is null; a reference start (or head) points to the first node. Unlike an array, its size can grow and shrink, and inserting or deleting needs only link changes, but access to the k-th element requires walking from the start.

Node class:
class Node { int data; Node next; }

Algorithms (always use a temporary pointer so start is not lost):
1. Traverse: t = start; while (t != null) { process t.data; t = t.next; }
2. Check emptiness: start == null.
3. Insert at beginning: n.next = start; start = n.
4. Insert at end: walk t to the last node (t.next == null); t.next = n (if the list is empty, start = n).
5. Delete a value: if start holds it, start = start.next; otherwise stop t at the node before it and set t.next = t.next.next.
6. Reverse: keep prev, cur, nxt; for each node set cur.next = prev, then advance.
7. Extract an element or sublist: walk to the position(s) and copy or link the required nodes.

// Single linked list: insertion at the beginning and end, deletion, reversal, counting, emptiness.
class Node
{
    int data;
    Node next;

    Node(int d)
    {
        data = d;
        next = null;
    }
}

public class LinkedList1
{
    Node start = null;                      // first node

    boolean isEmpty()
    {
        return start == null;
    }

    void insertFirst(int v)
    {
        Node n = new Node(v);
        n.next = start;
        start = n;
    }

    void insertLast(int v)
    {
        Node n = new Node(v);
        if (start == null)
        {
            start = n;
            return;
        }
        Node t = start;                     // temporary pointer
        while (t.next != null)
            t = t.next;
        t.next = n;
    }

    boolean delete(int v)                   // removes the first node holding v
    {
        if (start == null)
            return false;
        if (start.data == v)
        {
            start = start.next;
            return true;
        }
        Node t = start;
        while (t.next != null && t.next.data != v)
            t = t.next;
        if (t.next == null)
            return false;
        t.next = t.next.next;               // bypass the node
        return true;
    }

    void reverse()
    {
        Node prev = null, cur = start;
        while (cur != null)
        {
            Node nxt = cur.next;
            cur.next = prev;                // turn the link round
            prev = cur;
            cur = nxt;
        }
        start = prev;
    }

    int sumEven()
    {
        int s = 0;
        for (Node t = start; t != null; t = t.next)
            if (t.data % 2 == 0)
                s += t.data;
        return s;
    }

    void display()
    {
        for (Node t = start; t != null; t = t.next)
            System.out.print(t.data + " -> ");
        System.out.println("null");
    }

    public static void main(String[] args)
    {
        LinkedList1 l = new LinkedList1();
        System.out.println("empty? " + l.isEmpty());
        l.insertLast(20);
        l.insertLast(35);
        l.insertFirst(8);
        l.insertLast(42);
        l.display();
        System.out.println("sum of even values = " + l.sumEven());
        l.delete(35);
        l.display();
        l.reverse();
        l.display();
        System.out.println("delete 99? " + l.delete(99));
    }
}

Output:

empty? true
8 -> 20 -> 35 -> 42 -> null
sum of even values = 70
8 -> 20 -> 42 -> null
42 -> 20 -> 8 -> null
delete 99? false

Worked example

[2] Nodes of a linked list are objects of class Item { int val; Item link; }. Write a method int countMultiples(Item head, int k) that returns how many nodes hold a multiple of k. (Create)

Try it first, then show the solutionSolution

1. Item t = head; int c = 0; while (t != null) { ... t = t.link; } (temporary pointer, null check, move to next) - 1 mark.
2. Inside: if (t.val % k == 0) c++; after the loop return c - 1 mark.

Answer: int countMultiples(Item head, int k) { int c = 0; Item t = head; while (t != null) { if (t.val % k == 0) c++; t = t.link; } return c; } For 12 → 7 → 30 → 45 → 9 it returns 4 when k = 3 and 2 when k = 5 (checked by running the code).

Binary trees (conceptual): terms and traversals

A binary tree is a hierarchical structure in which each node has at most two children (left and right).

Example tree used below:
A has children B and C; B has children D and E; E has a left child G; C has a right child F; F has children H and I.

Terms:

• Root: the top node (A).
• Leaf (external node): a node with no children (D, G, H, I).
• Internal node: a node with at least one child (A, B, C, E, F).
• Parent, child, siblings: B and C are siblings (same parent A); H and I are siblings.
• Degree of a node: number of children (A: 2, C: 1, E: 1, F: 2, leaves: 0).
• Level: the root is at level 0 (some books use 1); each child is one level below its parent (G, H, I are at level 3).
• Depth of a node: number of edges from the root to it (E: 2). Height of a node: edges on the longest path from it down to a leaf. Height (depth) of the tree: height of the root; here 3 edges, or 4 if counted as the number of levels. State the convention you use.
• Size: number of nodes (9).
• Sub-tree: a node with all its descendants (the left sub-tree of A is rooted at B).
• Complete binary tree: every level full except possibly the last, which is filled from the left. Full (strict) binary tree: every node has 0 or 2 children.
• Balanced tree: for every node, the heights of the left and right sub-trees differ by at most 1.

Traversals (recursive definitions):

• Pre-order: Root, Left, Right → A B D E G C F H I
• In-order: Left, Root, Right → D B G E A C H F I
• Post-order: Left, Right, Root → D G E B H I F C A

(Checked by building this tree in Java: TreeCheck prints exactly these sequences.)

Worked example

[3] For the example tree, give (a) the external nodes, (b) the degree of F and of C, (c) the post-order traversal. (Apply)

Try it first, then show the solutionSolution

1. (a) Leaves: D, G, H, I - 1 mark.
2. (b) F has two children (degree 2); C has one (degree 1) - 1 mark.
3. (c) Left, right, root: D G E B H I F C A - 1 mark.

Answer: (a) D, G, H, I; (b) degree of F = 2, of C = 1; (c) D G E B H I F C A.

Data Structures in real life

Each concept, met in an everyday situation. Read the situation, answer the question in your own words, then compare with the model answer. The one-line hook is what to remember.

Topics in this chapter

• Infix, Prefix and Postfix Notation: Conversion and Evaluation
• Single Linked List Operations and Binary Trees
• Stack, Queue, Circular Queue and Dequeue in Java

Data Structures: syntax and key facts

Stack conditions (top = -1 start)

full: top == cap - 1; empty: top == -1; push st[++top] = v; pop return st[top--]

Change conditions if top starts at 0.

Circular queue (front = rear = 0)

full: (rear + 1) % cap == front; empty: front == rear

Advance with (i + 1) % cap.

Postfix / prefix

A + B → AB+ (postfix), +AB (prefix)

Bracket by precedence, convert innermost first.

Linked list traversal

for (Node t = start; t != null; t = t.next)

Never move start itself.

Traversals

Pre: Root-Left-Right; In: Left-Root-Right; Post: Left-Right-Root

Recursive on each sub-tree.

Tree counts

Max nodes at level L (root level 0) = 2^L; max nodes in height h (levels 0..h) = 2^(h+1) - 1

Binary trees.

How the board asks Data Structures

The question patterns to expect, and the method that works for each.

Tricks to remember Data Structures

Short memory aids. Say each one aloud once, then use it on a question the same day.

• LIFO tray, FIFO queue

  Stack = trays (last on, first off); Queue = bus queue (first come, first served).

  Use it when: Principles.

• Pre-In-Post = where the Root goes

  Pre: Root first; In: Root in the middle; Post: Root last.

  Use it when: Traversals.

• Modulo makes it circular

  next = (i + 1) % cap.

  Use it when: Circular queue movement.

Data Structures: board-level solved questions

Ordered from board level to HOTS. Cover the solution, write your own, then compare step by step.

Case-study practice (Section D style)

Read the situation, then answer every part. In the board paper this is a 6-mark question split into 1 + 2 + 2 + 1 marks.

Where the marks are

How a typical answer is split into step marks. Show every step: a right final answer alone rarely earns full marks.

Where students lose marks in Data Structures

The slips examiners see most often, and what to write instead.

• ✗Mistake: Conversion without working or with wrong precedence

  CISCE examiners' comments, 2024 and 2025: candidates 'Gave answer without working', used 'Wrong operator precedence' and 'Did not follow left-to-right rule'.

  ✓Do this: Write the bracketed form or the stack steps, then the answer; equal-precedence operators associate left to right.

  Usually costs: 1-2 marks.

• ✗Mistake: Wrong full and empty conditions

  CISCE examiners' comments: 2024 'Wrong if condition in addCard and drawCard for the initial value of top'; 2025 'Incorrect overflow and underflow conditions', 'Mishandled incrementing of front and rear', 'Missed wrap-around logic; implemented a linear queue instead of circular'.

  ✓Do this: Write the conditions from the initial values given; for circular queues use (rear + 1) % cap == front and front == rear, and move indices with % cap.

  Usually costs: 2-3 marks.

• ✗Mistake: Linked list without a temporary pointer or null check

  CISCE examiners' comments, 2025: candidates 'Did not create a temporary pointer', had 'Difficulty moving pointer to next node and checking null condition', and the 'Loop construct' was missing.

  ✓Do this: t = start; while (t != null) { ...; t = t.next; }

  Usually costs: 1-2 marks.

• ✗Mistake: Tree answers for the wrong part, or names instead of numbers

  CISCE examiners' comments: 2024 candidates 'Listed extra nodes or missed leaf nodes' and 'Wrote node names instead of the degree as a number'; 2025 candidates 'did in-order for the whole tree instead of the right subtree' and 'Included the root of the right subtree (C) as an internal node'.

  ✓Do this: Read which sub-tree is asked; degree is a number (0, 1 or 2); list leaves carefully.

  Usually costs: 1 mark each.

• ✗Mistake: Writing the principle as an application

  CISCE examiners' comments, 2025: for an application of a circular queue, candidates 'Wrote the principle FIFO as an application' or 'Stated the application vaguely'.

  ✓Do this: Give a concrete use: CPU round-robin scheduling, memory buffering, network traffic management.

  Usually costs: 1 mark.

Practice questions on Data Structures

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

1. Q1 · 1 mark · Very short answerBoard level

   What is the principle of a queue?

   Hint

   First come.

   Answer

   FIFO: first in, first out.

2. Q2 · 1 mark · Very short answerBoard level

   Convert A + B * C to postfix.

   Hint

   • first.

   Answer

   ABC*+

3. Q3 · 1 mark · Very short answerBoard level

   What is a leaf node?

   Hint

   No children.

   Answer

   A node with no children (an external node).

4. Q4 · 1 mark · Very short answerHarder board level

   Give the in-order traversal of the example tree.

   Hint

   Left, root, right.

   Answer

   D B G E A C H F I

5. Q5 · 2 marks · Short answerHarder board level

   [2] Write the condition for overflow and underflow of a stack when top starts at 0 (top is the next free index).

   Hint

   Next free slot.

   Answer

   Overflow: top == cap (push uses st[top++] = v). Underflow: top == 0 (pop uses return st[--top]).

6. Q6 · 2 marks · Short answerHarder board level

   [2] Write a method int count(Node start) that returns the number of nodes in a linked list.

   Hint

   Temporary pointer.

   Answer

   int count(Node start) { int c = 0; Node t = start; while (t != null) { c++; t = t.next; } return c; } For 8 → 20 → 35 → 42 it returns 4.

7. Q7 · 4 marks · Long answerHOTS / competency

   [4] Write int popRear( ) and void addFront(int v) for an array dequeue d[ ] with indices front and rear (elements in d[front..rear]).

   Hint

   Check space at the front.

   Answer

   void addFront(int v) { if (front == 0) System.out.println("NO SPACE AT FRONT"); else d[--front] = v; } int popRear() { if (front > rear) return -999; return d[rear--]; } With addRear 10, 20 and addFront 5, 1: popFront gives 1, popRear gives 20 (program output).

8. Q8 · 10 marks · Long answerHOTS / competency

   [10] (a) Define an interface Queue with void insert(int v), int delete( ) and boolean isEmpty( ). (b) Write a class CircularQueue implementing it with an array of capacity cap (front = rear = 0). (c) Show the output of inserting 1, 2, 3, 4 into a queue of capacity 4, deleting twice, inserting 5 and 6, and deleting four times.

   Hint

   Capacity 4 holds 3.

   Answer

   (a) interface Queue { void insert(int v); int delete(); boolean isEmpty(); } (b) class CircularQueue implements Queue with public methods using (rear + 1) % cap == front for full, front == rear for empty, and (index + 1) % cap for movement. (c) Inserting 4 reports full (only 3 fit); deletes give 1 2; inserting 5 and 6 wraps round; the four deletes give 3 5 6 -999 (the same sequence as the Queues program output).

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1. 1.Stack principle?Show answer

   LIFO.

2. 2.Circular queue full condition (front = rear = 0 start)?Show answer

   (rear + 1) % cap == front.

3. 3.Postfix of (A + B) * C - D / E?Show answer

   AB+C*DE/-.

4. 4.Pre-order rule?Show answer

   Root, Left, Right.

5. 5.Are binary trees programmed in ISC?Show answer

   No, conceptual only.

Quick revision checklist

The night before the exam: can you do each of these without looking?

• ☐Stack LIFO: push st[++top], pop st[top--]; top = -1 empty.
• ☐Queue FIFO; circular: (i + 1) % cap; full (rear + 1) % cap == front; empty front == rear.
• ☐Dequeue: both ends; can act as stack or queue.
• ☐Postfix: operands then operator; prefix: operator first; left to right for equal precedence.
• ☐Linked list: node = data + next; traverse with t, stop at null; reverse with prev, cur, nxt.
• ☐Tree: root, leaf, internal, degree, level, depth, height, size, siblings, complete, balanced.
• ☐Traversals: pre R-L-R, in L-R-R, post L-R-R.

Data Structures: frequently asked questions