"Arrays, Stacks, Queues & Linked Lists" — Practice

Question 1

What is the worst-case time to insert an element at the beginning of an array of n elements?

Accepted Answer

C

Question 2

A circular queue of capacity 10 sacrifices one slot to distinguish full from empty. What is its maximum number of elements?

Accepted Answer

B

Question 3

Which data structure is used to convert an infix expression to postfix?

Accepted Answer

A

Question 4

A circular queue of capacity 12 has front = 9 and rear = 3, with one slot sacrificed. How many elements does it hold, how many more can be added, and is it full?

Accepted Answer

Use the modular count formula, which handles the wrap correctly.

Elements = (rear minus front plus N) mod N = (3 minus 9 plus 12) mod 12 = 6 mod 12 = 6.

The queue holds 6 elements. Computing 3 minus 9 directly gives minus 6, and taking that modulo 12 is either wrong or implementation-dependent, which is why the capacity is added first.

For fullness, check whether advancing rear would collide with front: (3 plus 1) mod 12 = 4, which is not 9, so the queue is not full.

With one slot sacrificed, the maximum occupancy is 12 minus 1 = 11 elements. Holding 6, the queue can accept 5 more before the full condition fires.

A sanity check confirms this: after 5 more enqueues, rear would advance from 3 to 8, and (8 plus 1) mod 12 = 9, which equals front. The full condition fires exactly as expected.

Question 5

Convert (A + B) * (C - D) / E to postfix, showing the stack at each step.

Accepted Answer

Scan left to right. Operands go straight to the output; operators use the stack; parentheses force a flush.

Open bracket: push it. Stack: (

A: output. Output: A

Plus: the stack top is an open bracket, which never blocks, so push. Stack: ( +

B: output. Output: A B

Close bracket: pop until the matching open bracket, outputting each. Pop plus. Discard the bracket pair. Output: A B +. Stack: empty.

Times: the stack is empty, so push. Stack: *

Open bracket: push. Stack: * (

C: output. Output: A B + C

Minus: the top is an open bracket, so push. Stack: * ( -

D: output. Output: A B + C D

Close bracket: pop until the open bracket. Pop minus. Discard the pair. Output: A B + C D -. Stack: *

Divide: the top is times, which has equal precedence and is left-associative, so pop it. Then push divide. Output: A B + C D - *. Stack: /

E: output. Output: A B + C D - * E

End of input: pop the remainder. Pop divide.

The postfix expression is A B + C D - * E /.

The decisive step is the equal-precedence pop between times and divide. Because both are left-associative, the multiplication must be applied before the division, and popping on equal precedence is what enforces that.

Question 6

Compare the cost of deleting a known node in a singly linked list and a doubly linked list, and explain what the extra pointer buys.

Accepted Answer

In a singly linked list, deleting a node requires updating its predecessor's next pointer so that it skips the doomed node. But a singly linked node holds no reference to its predecessor, so the only route is to traverse from the head until the node whose next pointer equals the target is found.

That traversal is linear in the list length, so the deletion costs O(n) despite the pointer surgery itself being constant.

In a doubly linked list, each node carries a previous pointer as well as a next pointer. The predecessor is therefore immediately available, and the deletion sets the predecessor's next to the successor and the successor's previous to the predecessor.

That is two pointer writes with no traversal, so the cost is O(1).

What the extra pointer buys is precisely the removal of that search. The costs are one additional pointer per node, which for small elements can approach a doubling of memory, and two extra pointer updates on every insertion.

The singly linked workaround — copying the successor's data into the node and deleting the successor — achieves constant time without the extra pointer, but it fails for the last node and leaves any external pointer to the successor dangling, so it is a trick rather than a solution.

Question 7

Implement a queue using two stacks and prove that the amortised cost per operation is constant, despite a single dequeue costing linear time.

Accepted Answer

Keep two stacks, in and out.

Enqueue pushes onto in and always costs one operation.

Dequeue examines out. If out is non-empty, pop from it, costing one operation. If out is empty, pop every element from in and push each onto out, then pop from out. The transfer reverses the order, so the element that entered in earliest ends on top of out, which is exactly first-in-first-out.

A single dequeue that triggers a transfer of k elements costs 2k plus 1 operations, which is linear in the queue size, so the worst case per operation is genuinely O(n).

For the amortised bound, use aggregate analysis. Follow one element through its entire lifetime. It is pushed onto in exactly once. It is popped from in at most once. It is pushed onto out at most once. It is popped from out at most once. That is at most four stack operations per element, no matter how the enqueues and dequeues interleave.

A sequence of n queue operations involves at most n elements, so the total work is at most 4n stack operations, which is O(n). Dividing by n operations gives O(1) amortised per operation.

The key insight is that an element is never transferred twice: once it reaches out, it stays there until popped. A design that transferred back and forth would destroy the bound.

Question 8

Evaluate the postfix expression 6 2 / 3 - 4 2 * + and state the maximum stack height reached.

Accepted Answer

Scan left to right, pushing operands and applying operators to the top two, with the first popped as the right operand.

Push 6. Stack: 6. Height 1.
Push 2. Stack: 6, 2. Height 2.
Divide: pop 2 then 6, compute 6 divided by 2 = 3, push 3. Stack: 3. Height 1.
Push 3. Stack: 3, 3. Height 2.
Minus: pop 3 then 3, compute 3 minus 3 = 0, push 0. Stack: 0. Height 1.
Push 4. Stack: 0, 4. Height 2.
Push 2. Stack: 0, 4, 2. Height 3.
Times: pop 2 then 4, compute 4 times 2 = 8, push 8. Stack: 0, 8. Height 2.
Plus: pop 8 then 0, compute 0 plus 8 = 8, push 8. Stack: 8. Height 1.

The result is 8 and the maximum stack height reached is 3.

Two checks are worth performing. The stack must end with exactly one value, and it does; ending with more means the expression had too few operators, and ending empty or attempting to pop from an empty stack means too many. And the operand order matters for the division and the subtraction: popping 2 then 6 gives 6 divided by 2, not 2 divided by 6, and reversing it would have given 0 rather than 3.

Question 9

A collection of 4-byte integers must support frequent traversal and occasional insertion at arbitrary positions. Analyse whether an array or a doubly linked list is preferable, considering both asymptotics and memory behaviour.

Accepted Answer

Asymptotically the list appears to win on insertion. An array insertion at an arbitrary position shifts on average half the elements, giving O(n), while a doubly linked list splices in O(1) once the position is known.

But the qualification is decisive. Finding an arbitrary position in a list costs O(n) traversal, so the total cost of inserting at a given index is O(n) for both structures. The list only wins when the position is already held as a pointer, for example during a traversal that decides to insert.

Memory behaviour then favours the array strongly. Each 4-byte integer in a doubly linked list carries two pointers, which on a 64-bit machine is 16 bytes, so the node is 20 bytes for 4 bytes of data — a five-fold overhead before allocator padding.

Cache behaviour compounds this. An array traversal reads full cache lines, obtaining perhaps 16 integers per miss. List nodes allocated at different times are scattered, so a traversal can miss on nearly every node, and a cache miss costs on the order of a hundred cycles against the few cycles the shifting would have taken.

The practical conclusion is that for a traversal-dominated workload with only occasional insertion, the array is preferable despite the worse asymptotic insertion cost. The list becomes preferable when n is large, insertions are frequent, and positions arrive as pointers rather than indices — for instance in a free-list allocator or an LRU chain.

Practice — "Arrays, Stacks, Queues & Linked Lists"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities