Abstract Data Types in Software Development

• These notes concern Software Development & Problem Solving, specifically abstract data types
• The lecture will focus on abstract data types

Important Dates

• It is week 5 of the course
• Assignment 5.1 is due at the start of class next week
• Midterm exam 1 will be units 1-3

Assignment Acceptence

• A new repository needs creation for each unit
• Accept the Github Classroom assignment and clone to a computer
• Instructors provide a Github Classroom invite for every unit
• Accept the invite and get a URL for new repo
• Click it to verify creation
• The SoftDevII directory needs creation
  • Navigate to it then clone new repository there
• Open the repo in VSCode, ensure the PROBLEMS tab is visible

Data Structures

• Abstract Data Types (ADTs) are explored
• An ADT describes data structure behavior from the perspective of a user
• ADTs do not provide implementation details
• ADTs can be implemented in multiple ways
• Choosing efficiency means identifying the correct data structure for a problem
• Arrays, queues, stacks, lists, sets, and dictionaries all utilize data structures
• There are several abstract data types: Queues, Generics, Lists, Iterators, and the Java Collections Framework (JCF)
• Queues will be a key focus

Abstract Data Types

• A data structure, which is a grouping of related data is referred to as elements
• Data structures offer store, retrieve, remove, and size operations
• An Abstract Data Type (ADT) defines the the data structure's behavior from the perspective of the user, including values and operations
• ADTs can be implemented in multiple ways
• It is important to understand the complexity of each operation

ADT Examples

• A queue is a first-in, first-out (FIFO) data structure and does not provide random access
• A dictionary stores key/value pairs and keys are unique
  • Using the same key more than once replaces a previous value
  • Key's are not maintained in any particular order
• A stack is a last-in, first out (LIFO) data structure and does not provide random access
• A set stores unique elements, meaning duplicated are ignored, and elements are not maintained in any particular order
• A list is a variable length ADT that grows as elements are added and shrinks as they are removed
  • Elements are maintained in the added order and can be accessed using an index

Recursive Data Structures

• A recursive function calls itself
• A recursive data structure comprises a class/classes with at least one field of its own type and is used to build linked sequences
• A linked sequence is the basis for implementing data structures
• A node is the simplest recursive data structure with 2 fields
  • A value of some type
  • A reference to the next node in the sequence
• Nodes creates a sequence and each refers to the next node
  • The first node is a head while the last node is a tail, and the tails next node is null

Sequences of Nodes

• Train cars serve as an analogy for node visualization
• Each train car carries a value, and is akin to a node
• The train cars connect to create a sequence
• The first car becomes the “head" while the last becomes the “tail”
• The tail does not have a next car

Node Class Package

• Use nodes to implement abstract data types, starting with a node class
• Create a package called "unit05.mcf" to write code in (mcf=my collections framework)

Node Class Creation

• Create a Java Node Class
• The UML diagram is a reference when implementing a node class
  • Fields consist of value (String) and next (Node)
  • "Methods consist of (value: String), (value: String, next: Node), getValue(): String, setNext(next: Node), getNext(): Node
• The string representation of a node " -> "
• There needs to be a defined main method with an appropriate signature for testing the new Node class

Queues

• A queue is a data type that provides enqueue, dequeue, and size operations
  • Enqueue adds elements to the back
  • Dequeue removes elements from the front
  • Size returns current element count
• A queue may also provide front, back and is Empty operations
  • front and back return values without removing the element on either side
  • isEmpty returns true (empty) or false (otherwise)
• A Queue stores elements in First-In, First-Out (FIFO) order
• The element enqueued first will also be dequeued first
• Queue ADT defines its behavior but lacks implementation details
• In Java a feature can define behavior without an implementation

Queue Abstract Data Type

• The Queue abstract data type should define the behavior of all queues without the implementation
• Using a Java interface is an ideal mechanism for defining behavior in this case
• Use the UML diagram showing methods + enqueue(value: String), + dequeue(): String, + size(): int - to create a Queue interface in the MCF package

Node-Based Queue Values

• Use linked nodes to store values within a node based queue
• The oldest node is in the front
• A linked sequence defines the sequence
  • No values = null
    • That said, there should be at least on node, and one value
    • The value should be of some type
• A node based queue keeps tracks of 3 values
  • a node at the front of the queue
    • A node at the back of the queue
    • The total number of Nodes, including front an back
  • In a queue, if empty, both the tail and head are null
    • The front and back need to be considered

Special Conditions

• Needs to consider special conditions
  • empty queues
  • The queue contains one value.

Designing the Queue

• Remaining values are between the back and front
• If only one value is in the queue, the head and tail refers to the same node
• Use the UML model as an aid to creating/implementing your own model of the queue
  • Node queue will be referred to as ""Nodequeue""

Queues: the toString Method

• Implement a method that string to a format that reads <size>, <front> - Example output: "2, 5 -> 4 -> null""
• main method needs use for testing the nodequeue class
  • output data by use of standard methods

Implementation: Enqueue

• Create a ""NodeQueue"" class as well as implementing the ""enqueue"" process method
  • the enqueue method creates nodes to make additional spots in the queue
• front and back need to be equal when null new created; creates a new node
• "size"" is also required to increment, so the queue size is known

Testing: Enqueue Method

• After finishing the method ""Main""" should enqueue if used properly
• Code should now be used to test the queue

Dequeuing

• When a value is dequeued, it's always from the front
  • size will also correspondently shrink
    • the ""new front"" correlates to the next node
      • in this event, size must also decrement
    • null front means all nodes have been de-queued
    • back == null

Coding the dequeue Method""

• Must use the correct ""class"" when referring to/using methods
  • Code functions with certain ""methods""
    • Method: create the first ""node""
      • Also to save the value of the ""front node""
    • Create a ""new front node"" with """"old fronts"" next node""

Array Based Lists""

• Queues using a ""Circular Array"" is implemented in the structure and stored -""fronts"" indexes use the back to store themselves and save as fields, 1st-Enqueued/de-queued"" The back indexes are increment""

Array-Based Queue Benefits

• Implement with the queue interface code is expected to work with
• "From a perspective"" user - it will also ""Hide details behind it ""

Array queue class

• UML, fields and constructors will refer to arrays and are expected to ""implment the """size""" method.
• ""queue""" string expected format as: >

""Main method"" can then be used in the same class

• print results to ""test"""

Enqueueing""

""Fixed size-based"" or initialized arrays (or back-ends) needs""filling""

• The ""size index"" is increment if """enQueueing""" happens
• new ""Queue"" in progress""" "" backIndex= array length"" (module operator wraps back again