Stack and queue bug hunt

Questions 1 to 5 of 8

1. 1. This is_full method is from a stack built on a list of capacity 3. What is wrong with it? ``python def is_full(self): return self.top == len(self.data) ``

   It should be self.top == 0, because the stack is full when nothing is left to pop.The last valid index is len(self.data) - 1, so the check never becomes true before push writes past the end of the list and raises IndexError.It is only checked inside push, so pop can run past the end of the list.It should be self.top == len(self.data) + 1, because indexes start at zero.
2. 2. A ring queue uses these two tests. What is the bug? ``python def is_empty(self): return self.front == self.rear def is_full(self): return self.front == self.rear ``

   is_empty should compare self.front with 0, because the queue starts at index 0.The bug is only in dequeue, where front should move before the value is read.Both tests use the same condition, so an empty queue also reports full and the first enqueue raises RuntimeError.rear does not wrap with % len(self.data), so the queue can never be full.
3. 3. A linked-list queue has this dequeue. It is run on a queue with one item. What is the bug? ``python def dequeue(self): if self.is_empty(): raise IndexError("queue is empty") value = self.head.value self.head = self.head.next return value ``

   self.tail still points to the removed node after self.head becomes None, so the next enqueue links onto that old node and the new item cannot be reached from head.value = self.head.value should come after self.head = self.head.next, because the value must be read from the new head.It should raise when self.head is not None, because a non-empty queue cannot be dequeued.It returns the wrong node's value because it skips the first node.
4. 4. A bracket check should return True for (). What is the bug in this part of the loop? ``python open_bracket = stack[-1] if (ch == ")" and open_bracket != "(") or (ch == "]" and open_bracket != "["): return False ``

   The ] check should compare with ( instead of [, because the open bracket must match the close bracket.The function should return True inside the loop, because a matched pair ends the check early.The brackets are pushed in the wrong order, so ([]) always fails.stack[-1] leaves the matched open bracket on the stack, so not stack at the end is False for () and the function returns False for a balanced input.
5. 5. Using the fixed ArrayStack from the first bug (capacity 3), what does this code print? ``python s = ArrayStack(3) s.push(4) s.push(9) s.push(2) print(s.is_full()) print(s.pop()) s.push(7) print(s.pop()) print(s.pop()) ``

   True, 2, 7, 9 (one per line)True, 9, 7, 2 (one per line)False, 2, 7, 9 (one per line)True, 2, 7, 4 (one per line)