SCC.121 Lecture 1: Data Structures and Abstract Data Types II

SCC.121: Fundamentals of Computer Science

Lecture 1: Introduction to Data Structures and Abstract Data Types

Instructor: Amit Chopra

Email: amit.chopra@lancaster.ac.uk

Overview of the Course Content

  • Three Key Areas of Interest:

    • Abstract Data Type (ADT):

    • Focuses on the facilities and functionality of data types.

    • What the ADT does.

    • Data Structure Employed by the ADT:

    • Defines how the ADT performs its functionalities.

    • How operations are executed.

    • Implementation of the Data Structure:

- Examines how the ADT is stored and manipulated in memory.

Importance of Understanding Data Structures and ADTs

  • Understanding Abstract Data Type (ADT) functionally:

    • As users, we must comprehend the functionality and access methods.

  • Understanding the data structure utilized by the ADT:

    • As programmers, evaluating and selecting the best implementation options is crucial.

  • Knowing the implementation of the data structure:

- Computer scientists must grasp basic data structure principles.

Example ADT: The Queue

  • Definition of Queue ADT:

    • An ordered collection of items added at one end (tail) and removed from another end (head).

    • Maintains FIFO (First In, First Out) ordering.

    • Visual Representation:

-

Queue Example
Queue ADT Operations

  1. Queue()

    • Creates an empty queue.

    • Parameters: None.

    • Returns: Empty queue.

  2. enqueue(item)

    • Adds a new item to the queue's tail.

    • Parameters: Item to add.

    • Returns: Nothing.

  3. dequeue()

    • Removes the front item from the queue if not empty.

    • Parameters: None.

    • Returns: The removed item.

  4. isEmpty()

    • Tests if the queue is empty.

    • Parameters: None.

    • Returns: Boolean; true if empty, false otherwise.

  5. size()

    • Counts the number of items in the queue.

    • Parameters: None.

- Returns: Number of items currently in the queue.

Understanding Queue Functionality

  • The provided description is designed to give an understanding of queue capabilities.

- Conceptual diagrams and practical examples of queue operations assist in illustrating functionality, even if they may not fully represent implementation details.

Queue Behavior Examples
Enqueue Operation

  • Before enqueue:

    • size() = 4

  • Operation: enqueue(item)

  • After enqueue:

- size() = 5

Dequeue Operation

  • Before dequeue:

    • size() = 5

  • Operation: dequeue()

  • After dequeue:

- size() = 4

Definition and Nature of Abstract Data Types

  • An ADT describes only the operations available without detailing their implementation.

  • Does not specify data organization in memory or algorithms used for operations.

- The term abstraction refers to providing necessary information while concealing internal details.

Distinction Between Data Structures and Abstract Data Types

  • Data Structure:

    • Physical representation of data storage in memory.

  • Abstract Data Type (ADT):

- Comprises both the data structure and the procedures/functions for manipulating it.

Support Levels for ADTs in Programming Languages

  • Support for ADTs varies across languages.

  • Most languages allow user-defined types for data structures but with minimal support.

- Some languages enable encapsulation of data structures along with operations as part of ADT definition.

Concept of Encapsulation

  • Users interact with an ADT only through an interface consisting of procedures that operate on the data structure.

  • Direct manipulation of the physical data structure is prohibited.

- Encapsulation is a vital characteristic in Software Engineering.

Strong Encapsulation

  • If encapsulation is strong, details about data structure storage remain hidden from the user.

- Users possess a conceptual understanding of the ADT without knowing its operational intricacies.

Encapsulation in 'C' Language

  • C lacks true encapsulation; hence:

    • Users declare a new data structure to represent their ADT.

    • Provide procedures/functions manipulating the data structures.

  • Example: A string in C:

  Index:    0  1  2  3  4  5  6  7  8  9  10  11  12  13  
  Value:    'H' 'e' 'l' 'l' 'o' ',' ' ' 'W' 'o' 'r' 'l' 'd' '!' '\0'
Encapsulation in Java

  • Java provides encapsulation, allowing the definition of new ADTs as classes.

    • Classes include both data structures and associated methods.

    • Data structure elements can be declared private, hiding them from class users.

    • Non-interface methods may also be private.

- Everything in Java is fundamentally treated as a class.

Queue Implementation Model

  • Example of a Queue Element Representation:

  struct Element { 
      data; 
      nextPtr; 
  }

  • The head pointer points to the queue's head.

- An empty queue signifies head = nil, indicating no pointing element.

Queue State Evolution During Operations

  • Enqueue Sequence:

    • Enqueue(5)

    • Enqueue(3)

    • Result after dequeue: dequeue() returns 5.

  Queue Evolution:  
  5(head) -> next -> nil  
  5(head) -> next -> 3 -> next -> nil  
  3(head) -> next -> nil

  • Continued Sequence:

    • Dequeue() returns 3.

    • Following this, Dequeue operation yields nothing, indicating an “Empty queue.