Abstract Data Types
Abstract Data Types
Objectives
➢ Explain that an ADT is a collection of data and a set of operations on those
data.
➢ Explain how a stack, queue and linked list are examples of ADTs.
➢ Use a stack, queue and linked list to store data.
➢ Describe how a queue, stack and linked list can be implemented using
arrays.
Abstract Data Types
An Abstract Data Type is a collection of data and a set of associated operations:
● create a new instance of the data structure
● find an element in the data structure
● insert a new element into the data structure
● delete an element from the data structure
● access all elements stored in the data structure in a systematic manner.
Key Benefits of ADT
Abstraction: Hides complexity, making code easier to understand.
Encapsulation: Bundles data and operations together, promoting organization.
Data Hiding: Protects data from accidental changes.
Modularity: Breaks down problems into smaller, reusable parts.
Flexibility: Allows you to change the implementation without affecting the rest of the program.
ADTs
● Stacks
● Queues
● Linked lists
Stack
a stack is an abstract data type (ADT) that follows a specific order for adding and
removing items. This order is often described as "Last In, First Out" (LIFO), or First
in, Last one Out(FILO)meaning the last item added to the stack is the first one to be
removed
[Link]
Key features and operations of a stack:
Push: Adds an item to the top of the stack. push()
Python: [Link](“D”)
Pop: Removes and returns the item from the top of the stack.
[Link]()
Peek: Returns the item at the top of the stack without removing it.
peek() return “D” Python: print(data[len(data)-1]) def isEmpty(data):
isEmpty: Checks if the stack is empty.
if len(data)==0:
return True
isEmpty() returns either True when stack is empty or False when stack is not empty
else:
return False
Stacks in real life
Undo/Redo Functionality: In text editors or graphic design software, each action you take
(typing, formatting, drawing) is pushed onto a stack. When you undo, the last action is
popped off the stack, reversing its effect. Redo works by pushing the undone actions onto
another stack.
Function Calls: When a program calls a function, the current state of the program is pushed
onto a stack. When the function finishes, the state is popped off the stack, and the program
resumes from where it left off.
Browser History: Your web browser uses a stack to keep track of the pages you visit. The
"Back" button pops the most recent page off the stack.
Queues
A queue is an abstract data type (ADT) that follows a specific order for adding and
removing items. This order is often described as "First In, First Out" (FIFO), Last In , Last
Out(LILO) meaning the first item added to the queue is the first one to be removed.
[Link]
Key features and operations of a queue:
Enqueue: Adds an item to the back (rear) of the queue.
Python: [Link]("A")
For x = 1 TO 6
INPUT Letter
Enqueue(Letter)
END FOR
Dequeue: Removes and returns the item from the front (head) of the queue.
[Link](0)
Peek: Returns the item at the front of the queue without removing it.
print(data[0])
isEmpty: Checks if the queue is empty.
Queues in real life
Print Jobs:
Event Handling: In graphical user interfaces (GUIs), events like mouse clicks or
keyboard presses are placed in a queue. The system then processes these events one
by one, ensuring that none are missed.
Resource Scheduling: Operating systems use queues to schedule tasks like printing
or accessing disk drives. This ensures fair access and prevents one task from
monopolizing a resource.
Linked list
a linked list is a linear data structure where elements, called nodes, are not stored
sequentially in memory. Instead, each node contains:
1. Data: The information you want to store.
2. Pointer: A reference (or link) to the next node in the list.
[Link]
[Link]
Key Characteristics
Dynamic Size: Linked lists can grow or shrink during program execution, making them
flexible for handling data sets of varying sizes.
Non-Contiguous Storage: Nodes can be scattered throughout memory, unlike arrays,
which require a continuous block of memory.
Efficient Insertion/Deletion: Adding or removing elements at any position is generally
faster than in arrays, especially for large lists.
Types of Linked Lists
Singly Linked List: Each node has a pointer to the next node.
Doubly Linked List: Each node has pointers to both the next and previous nodes.
Circular Linked List: The last node points back to the first node, creating a closed
loop.
Linked lists
Music Playlists: The songs in a playlist are often stored in a linked list. Each
song node contains the song data and a pointer to the next song.
Image Galleries: Images in a gallery can be organized as a linked list, allowing
you to easily navigate to the previous or next image.
Question
Solution
Question
Solution