A1 Theory W3 Flashcards
Briefly describe Queue ADT giving details about
Main property of a Queue ADT;
Key operations of the Queue ADT;
Name a few applications where Queues are of use.
A queue ADT represents a linear collection of elements with two characteristics: Inserting elements at the rear and retrieving elements from the front. A queue follows the First In First Out principle, meaning the first element in is the first element retrieved out. Accessing other elements is not allowed in queues.
Key operations include:
- making the queue (Queue)
- Add an item to the back of the queue (append)
- take an item from the front of the queue (serve)
Application of queue use:
- Breadth-First searching: Queues are often used in graph algorithms like BFS to explore graphs level by level
- Task scheduling: operating systems use queues to manage processes and allocate resources
- Print job management: Queues are used to manage print jobs in the order they are submitted
- Call center systems: Queues are used to managing incoming calls and assign them in order.
- Simulations: Queues are used to model real world systems, like traffic flow and customer service systems.
Distinguish between a linear queue and a circular queue, providing at least 2 points of difference? Which one is better? Why?
In terms of boundaries:
A linear has elements served from the front of the queue and the remaining elements are shuffled forwards to fill the empty space. This operation can be time consuming when dealing with a large amount of elements.
A circular queue elements are stored in a circular system and front and rear pointers wrap around as they reach the end of the queue. This removes the need for shuffling as the pointers will move to the next position.
In terms of maximum capacity and space:
A linear queue can become full as the rear pointer moves to the end of the queue and maximum capacity is reached. Even when elements are served, the pointer will remain which leads to inefficient space use.
A circular queue has a rear pointer that wraps around to the beginning of the array when it reaches the end, this allows for efficient reuse of space.
A circular queue is generally considered to be better due to efficient use of memory and no shuffling required. However, there may be instances where a linear queue is a more appropriate choice. For example, if the queue size is fixed and small.
What is the best-case and worst-case complexity of the below operations for a Circular Queue ADT, if implemented with an array? Explain the reason for the best and worst case. No explanation no marks.
append()
serve()
is_full()
Serve:
Best-case O(1): removing front element of queue involves updating the front pointer and returning the element. Can be done in constant time.
Worst-case is O(1): similar to best-case, takes constant time.
Append:
Base-case is O(1): adding an element to the queue involves updating the rear pointer and placing the element in the next available position which takes constant time.
Worst-case is O(1): similar to best-case, adding an element to the circular queue takes constant time.
is_full:
Best-case is O(1): checking if the queue is full involves comparing the current number of elements with the capacity of the queue, can be done in constant time.
Worst-case is O(1): Similar to best-case, takes constant time.
Briefly describe List ADT giving details about
Main property of a List ADT;
Key operations of the List ADT;
Name a few applications where Lists are of use.
A list ADT is a linear collection of elements, where elements can be any type and are ordered. Lists are a flexible way to store and manage data, allowing for dynamic resizing and manipulation of elements. Main properties of list ADT is that it maintains an order of elements, meaning they are stored and retrieved in a sequential matter.
Key operations:
Insert: adds an element to a specific position in the list
Delete: removes the element at a particular position in the list
Append: adds an element to the back of the list
Remove: removes the first occurence of an element
Clear: clears the list
To-do list: used in task management applications to keep track of tasks in specific order
Contact lists: used to store and organise contact information, names, numbers, emails
Music playlists: used to create and manage ordered playlists of songs
Menu navigation: lists are used to display options on a menu interface to help users navigate through choices
Word processing:
lists are used for bullet points, numbered lists and outlining content in documents
What is the best-case and worst-case complexity of the below operations for a List ADT, if implemented with an array? Explain the reason for the best and worst case. No explanation no marks.
insert()
index()
delete_at_index()
Insert:
Best-case is O(n): when inserting an element at the beginning of the array all existing elements need to be shifted to the right to accomodate new element.
Worst-case is O(n): no shifting may be required but if the array needs to be resized then shifting the elements to the new array takes linear time.
Index:
Best-case is O(1): retrieves element from a known position in the array which takes constant time
Worst-case is O(1): similar to best-case, done in constant time.
Delete at index:
Best-case is O(n): when deleting an element from the beginning of the array, all existing elements need to shifted on position, this is done in linear time.
Worst-case is O(n): No shifting may be required but if the array needs to be resized then copying existing elements to the new array takes linear time.
