Queue implemented with a dynamic array. Examples: >>> q = ArrayQueue() >>> q.enqueue(1) >>> q.dequeue() 1
| 52 | |
| 53 | |
| 54 | class ArrayQueue(AbstractQueue): |
| 55 | """Queue implemented with a dynamic array. |
| 56 | |
| 57 | Examples: |
| 58 | >>> q = ArrayQueue() |
| 59 | >>> q.enqueue(1) |
| 60 | >>> q.dequeue() |
| 61 | 1 |
| 62 | """ |
| 63 | |
| 64 | def __init__(self, capacity: int = 10) -> None: |
| 65 | """Initialize with a fixed-capacity array. |
| 66 | |
| 67 | Args: |
| 68 | capacity: Initial capacity of the underlying array. |
| 69 | """ |
| 70 | super().__init__() |
| 71 | self._array: list[object | None] = [None] * capacity |
| 72 | self._front = 0 |
| 73 | self._rear = 0 |
| 74 | |
| 75 | def __iter__(self) -> Iterator[object]: |
| 76 | probe = self._front |
| 77 | while True: |
| 78 | if probe == self._rear: |
| 79 | return |
| 80 | yield self._array[probe] |
| 81 | probe += 1 |
| 82 | |
| 83 | def enqueue(self, value: object) -> None: |
| 84 | """Add an item to the rear of the queue. |
| 85 | |
| 86 | Args: |
| 87 | value: The value to enqueue. |
| 88 | """ |
| 89 | if self._rear == len(self._array): |
| 90 | self._expand() |
| 91 | self._array[self._rear] = value |
| 92 | self._rear += 1 |
| 93 | self._size += 1 |
| 94 | |
| 95 | def dequeue(self) -> object: |
| 96 | """Remove and return the front item. |
| 97 | |
| 98 | Returns: |
| 99 | The front element. |
| 100 | |
| 101 | Raises: |
| 102 | IndexError: If the queue is empty. |
| 103 | """ |
| 104 | if self.is_empty(): |
| 105 | raise IndexError("Queue is empty") |
| 106 | value = self._array[self._front] |
| 107 | self._array[self._front] = None |
| 108 | self._front += 1 |
| 109 | self._size -= 1 |
| 110 | return value |
| 111 |
no outgoing calls