4.2.1.4, 4.2.2.1 - Abstract data types and queues (C#)
Separate a structure's behaviour from its implementation, then create and maintain linear, circular and priority queues in C#. This route is incomplete: runnable support pending; code questions are written practice with no Run.
Interfaces, static and dynamic structures
An abstract data type specifies permitted operations and their meaning without choosing how values are stored.
Abstract data type
An abstract data type (ADT) describes a collection's behaviour through an interface of operations. A data structure is an implementation of that behaviour.
For a queue, adding at the rear and removing at the front defines first in, first out (FIFO) behaviour. An array plus indexes, or linked nodes with front and rear references, can both implement it. The caller should not have to know which representation is used.
| ADT | Simple use and equivalent representation |
|---|---|
| Queue | Waiting print jobs; an array with front/rear state, or C# Queue<T> |
| Stack | Undo history; an array with top index, or Stack<T> |
| Graph | Roads joining places; adjacency matrix or lists |
| Tree | Folder hierarchy; nodes linked to children |
| Hash table | Lookup by identifier; array of slots selected by a hash |
| Dictionary | Name-to-number mapping; Dictionary<string, string> or a searched list of key-value records |
| Vector | Coordinates or measurements; a same-type array or index-to-value dictionary |
These representations preserve the required behaviour even when there is no built-in type. Creating an array stack means allocating slots and setting top to −1; maintenance increments top for push and decrements it for pop after boundary checks. Creating a simple hash table means marking all slots empty; maintenance hashes a key, checks the candidate slot and probes another slot on collision. Lookup must follow the same probe sequence and compare stored keys. Later lessons develop these two implementations.
A static structure has a fixed capacity; a dynamic structure can change its capacity during use. A bounded array queue allocates predictable storage and is simple, but reserves unused space and rejects additions when full. A linked queue grows as items arrive and frees nodes when they leave, but needs link storage and allocation work. A resizable C# collection can grow its internal storage; its current element count is not its capacity. Dynamic does not mean unlimited: available memory is finite. Here “static” describes capacity, not C#'s static member keyword.
Linear queues
A linear queue stores its live items in a contiguous array interval, from front through rear.
Use front = 0, rear = -1 initially. Empty means front > rear. Add checks rear == items.Length - 1; if false, increment rear and store the new value. Remove first checks empty, returns items[front], then increments front. The array may still contain a removed value, but it is outside the live interval.
For capacity 3, adding A, B and C gives front 0/rear 2. Removing A gives front 1/rear 2, leaving B and C. This simple linear implementation cannot add D because rear has reached index 2, even though slot 0 is unused. This is wasted capacity, sometimes called a false-full condition. If every item is removed, reset front to 0 and rear to −1 so a new queue can begin. Shifting live values down would reuse space, but costs work proportional to the number shifted.
The built-in dynamic queue offers the same FIFO operations without exposing indexes:
Queue<string> jobs = new Queue<string>();
jobs.Enqueue("A");
jobs.Enqueue("B");
string first = jobs.Dequeue(); // A
bool empty = jobs.Count == 0; // false
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account