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

Abstract and concrete structures

An abstract data type states what operations mean without prescribing the storage used to implement them.

A queue normally removes the earliest remaining arrival: first in, first out (FIFO). Printer jobs and customer requests use this ordering. It could be implemented with an array and indices or linked nodes. The client calls enqueue and dequeue; it need not know which storage lies underneath.

These ADTs are developed in the following lessons. They are useful even where a language has no directly named built-in type: arrays, records/classes, references and indices can implement their operations. Creation establishes empty state; maintenance updates both values and the state that locates them. A stack must maintain its top and a hash table must handle occupied hash locations, just as a queue must maintain its front.

Static and dynamic storage

Capacity choices affect both the space a structure reserves and the work needed to grow it.

A static structure has a fixed capacity once created, such as a Java array. It offers predictable capacity and simple indexed access, but may waste reserved space or fill up. A dynamic structure can grow and shrink during use, such as a linked structure or a Java ArrayList. Linked nodes need references as well as values; resizable arrays may occasionally allocate a larger array and copy existing elements. Dynamic means variable size or capacity, not that memory is unlimited.

Use fixed storage when an upper bound is known and predictable allocation matters. Use dynamic storage when arrivals vary and reserving the maximum is undesirable. Distinguish logical emptiness from physical capacity: an allocated array with five slots can represent an empty queue.

Linear queues

A linear array queue moves its front and rear forward without wrapping around the array.

In this convention front identifies the next item to remove and rear identifies the next free slot. Both begin at zero. Add by writing at rear then incrementing it; remove by reading at front then incrementing it. The queue is empty when front == rear, and this implementation cannot add when rear == data.length.

final class LinearQueue {
    private final int[] data = new int[3];
    private int front = 0;
    private int rear = 0;
    boolean isEmpty() { return front == rear; }
    boolean isFull() { return rear == data.length; }
    void add(int value) {
        if (isFull()) throw new IllegalStateException("Full");
        data[rear++] = value;
    }
    int remove() {
        if (isEmpty()) throw new IllegalStateException("Empty");
        int value = data[front++];
        if (isEmpty()) { front = 0; rear = 0; }
        return value;
    }
}

After add 10, add 20, add 30 and remove, the returned value is 10 and the state is front=1, rear=3. Slots before the front are no longer live data, but this linear implementation still reports full until the remaining items are removed and it resets. Shifting remaining items down could reclaim space but costs copying. A circular queue reuses it without shifting.

Circular queues

A circular queue wraps an index back to zero so that vacant early slots can be reused.