Skip to main content

Data Structures · Abstract data types, representation, and invariants

A ring buffer (circular array) of fixed capacity C ≥ 1 stores a sequence of at most C…

Problem

Data Structures practice problem

A ring buffer (circular array) of fixed capacity C≥1C\ge 1 stores a sequence of at most CC elements using an underlying array B[0..C−1]B[0..C-1] together with two integers head and size, where 0≤head<C0\le\text{head}<C and 0≤size≤C0\le\text{size}\le C. The sequence in logical order isB[head], B[(head+1) mod C], …, B[(head+size−1) mod C].B[\text{head}],\ B[(\text{head}+1)\bmod C],\ \ldots,\ B[(\text{head}+\text{size}-1)\bmod C].Design procedures ENQUEUE-BACK(x), DEQUEUE-FRONT(), and PEEK(i) (0≤i<size0\le i<\text{size}) for this representation.

(a) Write pseudocode for the three procedures. ENQUEUE-BACK must fail (and leave the structure unchanged) if size=C\text{size}=C. DEQUEUE-FRONT must fail if size=0\text{size}=0. PEEK must return the element at logical index ii without mutating the buffer.
(b) State the representation invariant relating BB, head, size, and CC.
(c) For each procedure, give a worst-case Θ\Theta bound in terms of CC and size, and argue that the bound does not hide a scan of the buffer.

Hint

Hint

The live data occupy a wrap-around interval of length size starting at head; the back of that interval is determined by those two integers.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

Create a free account to check your answer and see the solution. Create a free account.

More Data Structures practice problems

Back to Data Structures

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.