10.4 Introduction to Abstract Data Types (ADT) - Array Implementations

Abstract Data Types (ADTs)

An Abstract Data Type (ADT) is a mathematical model that defines a set of data and the operations that can be performed on that data. It focuses on what the data does, rather than how it is implemented. This separation of concerns allows for flexibility in implementation.

Common ADTs include queues, stacks, and linked lists. These are fundamental data structures used in various algorithms and applications.

Implementing ADTs using Arrays

Arrays are a simple and often efficient way to implement ADTs. The key is to understand how the array's indexing can represent the abstract operations of the ADT.

1. Queue Implementation using Arrays

A queue is a First-In, First-Out (FIFO) data structure. Elements are added to the rear (enqueue) and removed from the front (dequeue).

We can implement a queue using a fixed-size array. The front of the queue is typically represented by an index, and the rear is represented by another index.

Operation	Array Index	Description
Enqueue	Rear Index	Add an element to the rear of the queue. Increment the rear index, then place the element at the new rear index.
Dequeue	Front Index	Remove the element from the front of the queue. Increment the front index. The element at the old front index is now available (but may need to be shifted).
isEmpty	(Front Index == Rear Index)	Check if the queue is empty.
isFull	(Rear Index == Maximum Index)	Check if the queue is full.

Example: Consider a queue with a capacity of 5. If the front index is 0 and the rear index is 4, the queue has space. If the rear index is 4 and the front index is also 0, the queue is full.

2. Stack Implementation using Arrays

A stack is a Last-In, First-Out (LIFO) data structure. Elements are added to the top (push) and removed from the top (pop).

We can implement a stack using a fixed-size array. The top of the stack is represented by an index.

Operation	Array Index	Description
Push	Top Index	Add an element to the top of the stack. Increment the top index, then place the element at the new top index.
Pop	Top Index	Remove the element from the top of the stack. Decrement the top index.
isEmpty	(Top Index == -1)	Check if the stack is empty.
isFull	(Top Index == Maximum Index)	Check if the stack is full.

Example: If the top index is 4, the top of the stack is at the array index 4. Pushing an element will move the top index to 5 (if the array has a capacity of 5).

3. Linked List Implementation using Arrays

While linked lists are typically implemented using pointers, we can simulate a linked list using an array. Each element in the array represents a node in the linked list. We use special values (e.g., a specific value or null) to indicate the 'next' node.

Operation	Array Index	Description
Insert at Beginning	Head Index	Insert a new element at the beginning of the list. Shift existing elements forward.
Delete from Beginning	Head Index	Remove the element at the beginning of the list. Shift existing elements backward.
Insert at End	Tail Index	Insert a new element at the end of the list.
Delete from End	Tail Index	Remove the element at the end of the list.
isEmpty	(Head Index == -1)	Check if the list is empty.

Note: This array-based linked list implementation can be less efficient than a standard linked list, especially for insertion and deletion at the beginning, as it requires shifting elements.

Conclusion

Arrays provide a straightforward way to implement ADTs. The choice of implementation depends on the specific requirements of the ADT and the desired performance characteristics. Understanding the underlying array indexing is crucial for implementing these data structures correctly.