4.2.1.4, 4.2.2.1 - Abstract data types and queues (VB.NET)
Distinguish an abstract data type from its implementation, compare static and dynamic storage, and maintain linear, circular and priority queues. This VB.NET route uses written code with no Run: incomplete: runnable support pending.
Interfaces, static and dynamic structures
An abstract data type describes the data and permitted operations without requiring one storage method.
Abstract data type
A specification of a collection's values, operations and behaviour, independent of the implementation used to provide them.
A queue's user needs Enqueue, Dequeue and an empty test. The implementation may use an array or linked nodes; either must preserve the promised order. Separating this interface from its implementation lets the calling code remain stable when storage changes.
| Type | Behaviour and use | Representation when no built-in type is available |
|---|---|---|
| Queue | First in, first out; waiting print jobs | Array with front/rear state or linked nodes |
| Stack | Last in, first out; undo actions | Array with a top index or linked nodes |
| Graph | Nodes joined by edges; road connections | Adjacency matrix or neighbour lists |
| Tree | Connected graph without cycles; folder hierarchy when rooted | Node records and child references |
| Hash table | Maps keys to values through a hash; fast record lookup | Slot array and collision policy |
| Dictionary | Accesses values by unique keys; word frequencies | Hash table or another key-search structure |
| Vector | Ordered components; location or displacement | Array, list or index-to-value dictionary |
Creating a fixed array stack means allocating capacity and setting top = -1; pushing changes the top and stores a value, while popping returns the current top and decreases it. Creating a hash table means allocating slots and recording which are occupied; insertion computes a hash and resolves any occupied target before storing a key-value pair. These maintenance rules differ from a queue's front/rear operations; later lessons develop each implementation.
A static structure has fixed storage capacity for its lifetime. It gives predictable storage and straightforward indexing but may waste unused space or become full. A dynamic structure can grow or shrink as needed. Linked nodes require references and allocation overhead; growable array-backed collections sometimes allocate a larger array and copy entries. Dynamic does not mean unlimited: available memory still limits growth. For a fixed 30-seat register, a static array is sensible; an unpredictable waiting list favours dynamic storage. VB.NET Queue(Of T) is growable, whereas the array queue below is deliberately bounded.
Linear queues
A linear queue adds at its rear and removes at its front, preserving first-in, first-out order.
Consider an array of capacity 4. Let front identify the next item to remove and rear identify the next unused slot. Both start at 0. Enqueue stores at rear, then increases rear; dequeue reads at front, then increases front. Empty means front = rear. In this non-compacting implementation, enqueue has no space when rear = 4, even if removals left unused cells at the start.
After adding A, B and C, the live items are [A, B, C], front = 0, rear = 3. Removing returns A and sets front = 1; adding D sets rear = 4. Adding E now fails. Shifting remaining items down would reclaim space but requires extra movement. Alternatively, reset both indices when the queue becomes empty; a circular queue reuses vacated slots without shifting.
The following complete source uses the growable library queue to provide the same FIFO contract without our fixed-array capacity restriction.
Option Strict On
Imports System
Imports System.Collections.Generic
Module Program
Sub Main()
Dim jobs As New Queue(Of String)()
jobs.Enqueue("A")
jobs.Enqueue("B")
Console.WriteLine(jobs.Dequeue())
Console.WriteLine(jobs.Peek())
Console.WriteLine(jobs.Count)
End Sub
End Module
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account