Queue ADT (arrays based), List ADT (arrays based) Flashcards
What is the main property of a Queue ADT?
A queue ADT is a collection of values that follows the first-in first-out (FIFO) principle, meaning that the first value added to the queue is the first one removed from the queue. The main property of a queue ADT is that it only allows access to the front and rear elements of the queue, and does not allow random access to other elements.
Key operations of the Queue ADT
The key operations of a queue ADT are queue, append and serve ( front, rear, and isEmpty are other examples of operations). Queue creates a queue, append adds a value to the rear of the queue, serve removes and returns the value from the front of the queue, front returns the value from the front of the queue without removing it, rear returns the value from the rear of the queue without removing it, and isEmpty checks if the queue is empty or not
Name a few applications where Queues are of use.
Some applications where queues are of use are:
Simulating waiting lines in real-world scenarios, such as customers at a bank, passengers at an airport, or tasks at a printer
Implementing breadth-first search algorithms in graphs and trees
Buffering data in communication networks, such as packets in a router or messages in a chat app
Distinguish between a linear queue and a circular queue, providing at least 2 points of difference? Which one is better? Why?
A linear queue is a queue that uses a linear data structure, such as an array or a linked list, to store the values in the queue. A circular queue is a queue that uses a circular data structure, such as a circular array or a circular linked list, to store the values in the queue. The difference between a linear queue and a circular queue are:
A linear queue has a fixed capacity, which may be too large or too small for the queue, and may require resizing the data structure when the queue grows or shrinks. A circular queue has a variable capacity, which can be adjusted by wrapping around the data structure when the queue grows or shrinks.
A linear queue may suffer from the problem of wasted space, as the front of the queue may move forward and leave empty slots at the beginning of the data structure. A circular queue does not have this problem, as the front and rear of the queue can move around the data structure and utilize all the slots.
The choice of which queue is better depends on the situation and the trade-offs involved. A linear queue may be simpler and easier to implement, but it may have a higher time and space complexity than a circular queue. A circular queue may be more efficient and flexible, but it may have a higher complexity and difficulty in implementation than a linear queue
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()
The best-case and worst-case complexity of the below operations for a circular queue ADT, if implemented with an array, are:
append(): O(1)
in both cases, because it involves adding an element to the rear of the queue, which can be done in one step by incrementing the rear pointer and wrapping it around the array if necessary
serve(): O(1)
in both cases, because it involves removing an element from the front of the queue, which can be done in one step by incrementing the front pointer and wrapping it around the array if necessary
is_full(): O(1)
in both cases, because it involves checking if the rear pointer is one position behind the front pointer, or if the front and rear pointers are at the same position and the queue is not empty, which can be done in one step by comparing the pointers and the queue size
Main property of a List ADT
A list ADT is a collection of values that can be accessed by index, and can have a variable size. The main property of a list ADT is that it allows random access to any element in the list, and supports insertion and deletion of elements at any position.
Key operations of the List ADT
The key operations of a list ADT are insert, index, delete_at_index, len, and getitem. Insert adds a value to the list at a given position, index returns the position of a value in the list, delete_at_index removes and returns the value from the list at a given position, len returns the number of elements in the list, and getitem returns the value from the list at a given position without removing it.
Name a few applications where Lists are of use.
Some applications where lists are of use are:
Storing and manipulating sequences of data, such as numbers, strings, or objects
Implementing other ADTs, such as stacks, queues, or trees
Sorting and searching algorithms, such as merge sort, quick sort, binary search, or linear search
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()
The best-case and worst-case complexity of the below operations for a list ADT, if implemented with an array, are:
insert(): O(1)
in the best case, when the position is at the end of the list and the array is not full, and O(n)
in the worst case, when the position is at the beginning of the list or the array is full, because it involves shifting the elements in the array and possibly resizing the array
index(): O(1)
in the best case, when the value is at the beginning of the list, and O(n)
in the worst case, when the value is at the end of the list or not in the list, because it involves searching the array for the value
delete_at_index(): O(1)
in the best case, when the position is at the end of the list, and O(n)
in the worst case, when the position is at the beginning of the list, because it involves shifting the elements in the array
