Full or Empty: Telling Them Apart

2. Sacrifice one cell

Never let the queue hold more than capacity - 1 items. Then a full queue always leaves one gap, so the markers never coincide when full.

For: no extra field at all. Against: one cell of the array is never used, and the tests are less obvious. A queue declared with capacity 5 holds 4.

This is the version many textbooks print, so it must be recognised, and the full test is the line to memorise: (rear + 1) mod capacity == front.

3. Keep a flag

Hold a boolean saying whether the last operation was an enqueue. If the markers coincide and the last operation was an enqueue, it is full; if it was a dequeue, it is empty.

For: all cells usable, only one bit. Against: the flag has to be correct after every operation, and reasoning about it is harder than either of the others. Rarely used.

All three, run side by side

class CountQueue:
    def __init__(self, capacity):
        self.capacity, self.cells = capacity, [None] * capacity
        self.front = self.rear = self.count = 0

    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.count == self.capacity

    def enqueue(self, item):
        if self.is_full():
            return False
        self.cells[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        self.count += 1
        return True


class SacrificeQueue:
    def __init__(self, capacity):
        self.capacity, self.cells = capacity, [None] * capacity
        self.front = self.rear = 0

    def is_empty(self):
        return self.front == self.rear

    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front

    def enqueue(self, item):
        if self.is_full():
            return False
        self.cells[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        return True


for cls in (CountQueue, SacrificeQueue):
    q = cls(5)
    accepted = 0
    while q.enqueue(accepted):
        accepted += 1
    print("%-16s capacity 5 accepted %d items before reporting full"
          % (cls.__name__, accepted))

CountQueue       capacity 5 accepted 5 items before reporting full
SacrificeQueue   capacity 5 accepted 4 items before reporting full

There is the cost of the second method, measured: a five cell array holding four items.

Which to write in an examination

Either of the first two, stated clearly. The marks are for:

1. Explaining why the ambiguity exists: both states give front == rear.
2. Naming the method chosen.
3. Giving the correct full and empty tests for that method, which is where answers go wrong by mixing

the count method's empty with the sacrifice method's full.

Mixing them is the error to avoid. If you keep a count, use count == 0 and count == capacity. If you sacrifice a cell, use front == rear and (rear + 1) mod capacity == front.

Quick revision

• In a circular queue with only front and rear, empty and full both give front == rear.
• Three answers: keep a count; sacrifice one cell; keep a flag.
• Count: empty is count == 0, full is count == capacity. All cells usable, one field to maintain.
• Sacrifice: empty is front == rear, full is (rear + 1) mod capacity == front. No extra field,

one cell lost, so capacity 5 holds 4.

• Flag: a boolean recording whether the last operation was an enqueue. Rarely used.
• In an answer: say why the ambiguity exists, name the method, and give that method's own two tests

without mixing them.

Test yourself

1. Why can front and rear alone not distinguish full from empty? Because in both states the two markers hold the same value: an empty queue has never advanced rear past front, and a full one has advanced it all the way round to meet front again.

2. Give the full and empty tests for the count method. Empty is count == 0; full is count == capacity.

3. Give the full and empty tests for the sacrifice method. Empty is front == rear; full is (rear + 1) mod capacity == front.

4. What does the sacrifice method cost, exactly? One cell of the array. A queue declared with capacity 5 can hold only 4 items, as the run showed.

5. Describe the flag method and say why it is rare. Keep a boolean recording whether the last operation was an enqueue; when the markers coincide it distinguishes full from empty. It is rare because the flag must be maintained correctly by every operation and is harder to reason about than a count.

6. What is the standard error in answering this question? Mixing the methods: using the count method's empty test with the sacrifice method's full test, or the reverse. Each method has its own pair and they must be used together.