SME
Data Structures & Algorithms · Problem type
Circular queue indices
Use this for “A circular queue has 8 slots, its front at slot 6 and 4 items. Where is the last item, and where does the next one go?”
This is an example. Type your own values to start a new problem.
L
=
(
f
+
c
−
1)
mod
N
E
=
(
f
+
c
)
mod
N
F
Free slots
worked out (not typed)
Formulas
L
=
(
f
+
c
−
1)
mod
N
1 = (6 + 4 − 1) mod 8
E
=
(
f
+
c
)
mod
N
2 = (6 + 4) mod 8
F
=
N
−
c
4 = 8 − 4
Assumptions
•
The slots are numbered 0 to N − 1; after slot N − 1 comes slot 0 again.
•
The items sit in order from the front, one slot each, so the last is c − 1 slots past the front.
•
An enqueue writes the slot after the last item; a dequeue moves the front one slot on.
•
The page needs a free slot (c < N), or the next enqueue has nowhere to go.
Step-by-step
WE KNOW
N = 8, f = 6, c = 4
FIND
last item’s slot (L), next enqueue slot (E), free slots (F)
Step 1 · Find last item’s slot (L)
Use L = (f + c − 1) mod N
The
last
item
is
c
−
1
slots
past
the
front;
mod
N
wraps
a
count
past
the
end
back
to
slot
0.
L
=
(6
+
4
−
1)
mod
8
9
mod
8
=
9
−
8
×
⌊
9
8
⌋
=
9
−
8
×
1
=
1
L
=
1
Step 2 · Find next enqueue slot (E)
Use E = (f + c) mod N
The
next
item
goes
in
the
slot
just
after
the
last
one,
wrapping
past
N
−
1
to
0.
E
=
(6
+
4)
mod
8
10
mod
8
=
10
−
8
×
⌊
10
8
⌋
=
10
−
8
×
1
=
2
E
=
2
Step 3 · Find free slots (F)
Use F = N − c
Every slot not holding an item is free for an enqueue.
F
=
8
−
4
F
=
4
Check
Put the numbers back in. Both sides should match.
1 = (6 + 4 − 1) mod 8 ✓
2 = (6 + 4) mod 8 ✓
4 = 8 − 4 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Lists, stacks and queues
Main lesson
Address of an array element
Use this for “A two-dimensional array of 8-byte numbers starts at address 2000 and has 10 columns. Where is element (3, 4)?”
Cost of a growing array
Use this for “An array starts with 1 slot and doubles when full. How many items are copied while 1000 are pushed?”
Evaluate a postfix expression
Use this for “Evaluate the postfix expression 3 4 + 2 × 7 − with a stack.”