Linear Data Structures: Arrays, Stacks, Queues & Linked Lists: 17 MCQs with answers

Each element has at most one predecessor and one successor.

A linear data structure stores elements in a sequence where each element has at most one predecessor and one successor. Contiguity is an array property, not a requirement for all linear structures.

The size of each element in bytes

In the array address formula, $B$ is the base address, $i$ is the index, and $w$ is the width or size of each element in bytes.

LIFO — Last In, First Out

A stack inserts and deletes only at the top, so the last element pushed is the first one popped — LIFO.

At the rear

A queue enqueues at the rear and dequeues from the front, giving FIFO behaviour.

Reverse Polish (postfix) notation

Reverse Polish or postfix notation writes the operator after the operands, e.g. $A\,B\,+$. Polish notation is prefix, with the operator first.

True

Array element access is $O(1)$ because the address is computed directly as $B + i \times w$.

Queue

Print spooling is a fair-order process, so FIFO applies — a queue. A stack would reverse the order, and a priority queue would reorder by importance.

Elements after the insertion point must be shifted to keep memory contiguous.

Arrays occupy contiguous memory, so making room in the middle requires shifting subsequent elements — an $O(n)$ operation.

$16$

Push 5 and 3; on $+$ pop 3 and 5, push 8; push 2; on $\times$ pop 2 and 8, push 16. The result is 16.

Circular queue

A circular queue wraps the rear index using modulo arithmetic, so freed slots at the front are reused while enqueue and dequeue stay $O(1)$.

Array

An array gives $O(1)$ random access through the address formula, which suits fixed-size, access-heavy workloads. Linked lists need $O(n)$ traversal for access.

It stores only 50 triples instead of $10^6$ cells.

A sparse matrix wastes memory when stored fully. Triplet form keeps only $(row, column, value)$ for non-zero entries, so 50 triples replace a million cells.

Insertion at a known node position

Once the position is known, a linked list inserts in $O(1)$ by relinking pointers, whereas an array must shift elements. Access is the reverse: $O(1)$ for arrays, $O(n)$ for linked lists.

Priority queue

A priority queue dequeues the highest-priority element rather than the earliest, which matches urgency-based scheduling. A heap implementation keeps dequeue at $O(\log n)$.

It requires $2^n - 1$ moves and mirrors stack push/pop discipline.

The recursive solution to Tower of Hanoi takes $2^n - 1$ moves, and each recursive call pushes a frame on the call stack while each return pops it.

Deque and linked list

A deque restricted to one end behaves like a stack, and a linked list with insertion and deletion only at the head also behaves like a stack. The other pairs lack this single-end restriction.

Priority Queue

A **Priority Queue** allows for elements to be dequeued based on their priority rather than their arrival time. This meets the requirement of processing higher priority tasks first while maintaining the order of tasks with the same priority.