Kerala Plus Two Computer Science (DHSE): Data Structures: Arrays, Stacks and Queues

Data Structures: Arrays, Stacks and Queues

Questions test representation, operations, and the LIFO/FIFO behaviour that decides output sequences.

Arrays

• A fixed-size, contiguous collection of same-type elements; index starts at 0.
• Access is O(1) by index; insertion/deletion in the middle costs O(n) due to shifting.
• In C++, int a[5]; has valid indices 0–4; going outside is undefined behaviour.

Stack

• LIFO: insertion (push) and deletion (pop) happen at one end, top.
• Empty stack: top = -1. Push checks overflow; pop checks underflow.
• Applications: function call management, undo, expression conversion/evaluation, backtracking.

Queue

• FIFO: enqueue at rear, dequeue from front.
• Linear queue suffers false overflow; a circular queue reuses slots with rear = (rear + 1) % size.
• Applications: scheduling, buffers, breadth-first traversal.

Worked example

Push 10, push 20, pop, push 30, then pop. Stack after first two pushes: bottom 10, top 20. First pop removes 20, leaving top 10. Push 30 makes top 30. Second pop removes 30. Remaining top is 10. The output order is 20, 30 - not 10 - because LIFO reverses arrival order.

Traps

• Calling pop on an empty stack (underflow) or pushing beyond capacity (overflow).
• Confusing top (peek) with pop; peek does not remove.
• Using a linear queue until rear reaches the end and wrongly assuming the queue is full.
• Off-by-one errors in circular queue full/empty tests; often one slot is left unused.
• Forgetting array indices start at 0.