Queue implemented with a singly linked list. Examples: >>> q = LinkedListQueue() >>> q.enqueue(1) >>> q.dequeue() 1
| 136 | |
| 137 | |
| 138 | class LinkedListQueue(AbstractQueue): |
| 139 | """Queue implemented with a singly linked list. |
| 140 | |
| 141 | Examples: |
| 142 | >>> q = LinkedListQueue() |
| 143 | >>> q.enqueue(1) |
| 144 | >>> q.dequeue() |
| 145 | 1 |
| 146 | """ |
| 147 | |
| 148 | def __init__(self) -> None: |
| 149 | super().__init__() |
| 150 | self._front: QueueNode | None = None |
| 151 | self._rear: QueueNode | None = None |
| 152 | |
| 153 | def __iter__(self) -> Iterator[object]: |
| 154 | probe = self._front |
| 155 | while True: |
| 156 | if probe is None: |
| 157 | return |
| 158 | yield probe.value |
| 159 | probe = probe.next |
| 160 | |
| 161 | def enqueue(self, value: object) -> None: |
| 162 | """Add an item to the rear of the queue. |
| 163 | |
| 164 | Args: |
| 165 | value: The value to enqueue. |
| 166 | """ |
| 167 | node = QueueNode(value) |
| 168 | if self._front is None: |
| 169 | self._front = node |
| 170 | self._rear = node |
| 171 | else: |
| 172 | self._rear.next = node |
| 173 | self._rear = node |
| 174 | self._size += 1 |
| 175 | |
| 176 | def dequeue(self) -> object: |
| 177 | """Remove and return the front item. |
| 178 | |
| 179 | Returns: |
| 180 | The front element. |
| 181 | |
| 182 | Raises: |
| 183 | IndexError: If the queue is empty. |
| 184 | """ |
| 185 | if self.is_empty(): |
| 186 | raise IndexError("Queue is empty") |
| 187 | value = self._front.value |
| 188 | if self._front is self._rear: |
| 189 | self._front = None |
| 190 | self._rear = None |
| 191 | else: |
| 192 | self._front = self._front.next |
| 193 | self._size -= 1 |
| 194 | return value |
| 195 |
no outgoing calls