4.2.1.4, 4.2.2.1 - Abstract data types and queues (Python)

Interfaces, static and dynamic structures

An abstract data type specifies what operations mean, while a data structure implements those operations in storage.

A queue promises to add items and remove them in a specified order. It could use a fixed array and indices or dynamically allocated linked nodes. A caller using add and remove need not know which. If a language lacks a built-in type, arrays, records/classes and indices or references can represent it.

Creation and maintenance follow each structure's rules: initialise queue indices, stack top or empty hash slots; update them after adding/removing; protect against underflow, overflow or collisions. The following lessons develop the stack and hash operations in detail.

A static structure has a fixed logical capacity. It provides predictable allocated space and straightforward indexing, but may waste unused slots and cannot accept more than its capacity. A dynamic structure can change logical size at runtime; it suits uncertain workloads but needs allocation/resizing or link maintenance and may have extra memory overhead. A Python list can grow, although it internally reserves storage and occasionally resizes. Preallocating [None] * capacity and enforcing that capacity gives a static queue model; the programmer, rather than Python, enforces the bound.

Linear queues

A linear first-in, first-out queue stores the next removable item at its front and adds new items at its rear.

Use front as the index of the next item to remove and rear as the next unused index. Initially both are zero. The occupied slice is data[front:rear], so the queue is empty when front == rear. Adding writes to data[rear] then increments rear; removing reads data[front] then increments front. Test before indexing to prevent overwriting or removing nonexistent data.

For capacity four, adding A, B, C gives front = 0, rear = 3. Removing A gives front = 1, rear = 3, with B then C waiting. In this simple no-shift implementation, rear == capacity means no further add is possible, even if slots before front have become unused. This is a limitation of that implementation, rather than a universal definition of queue fullness. When it becomes completely empty, resetting both indices to zero safely reclaims the space. Shifting every remaining item forward also reclaims space but costs work proportional to the queue length.

Python's collections.deque provides convenient dynamic append and left removal. It does not impose the fixed-capacity full condition used in these examples unless the program explicitly checks its own limit. An unbounded dynamic queue still has practical memory limits.

Circular queues

A circular queue reuses released array slots by wrapping its indices around the fixed capacity.

Maintain front as the next removal index, rear as the next insertion index and count as the number of stored items. Empty means count == 0; full means count == len(data). Advancing an index uses (index + 1) % capacity. At both empty and full, front can equal rear, so equality alone cannot distinguish the states in this convention. Other conventions reserve an unused slot; their full test must match that choice.