Please enable JavaScript.

Coggle requires JavaScript to display documents.

Data structures - Coggle Diagram

- - - - A list can involve a static or dynamic implementation.
        Static array implementation
        Maximum number of elements is fixed. This means that:
        
        When the array structure is full you cannot add any more items to the list
        
        When the array structure is empty, or partially full, you can be wasting valuable memory space
        
        You still have some choices to make about how you organise the data. You could populate the array sequentially but this can cause maintenance problems. If items are constantly added and deleted from the list, you will end up with gaps that you will have to locate with a linear search to find space for new items. You could choose to keep moving the items towards the start of the array to fill any gaps. This processing can be avoided if you include an index pointer to the next occupied element in the list; in this way your array will act as a form of linked list.
        Dynamic linked list implementation
        A list can be implemented dynamically using a linked list.
        Which should you choose?
        Linked list is useful when size of the list is not known in advance because the structure is dynamic and the size can change at run time. Maintaining data in a linked list is time efficient because items can be added and deleted by adjusting pointers.
        An array will allow you to implement efficient sorting and searching algorithms. Binary search algorithm requires you to repeatedly find the mid-point of the array, an operation that is straightforward as the elements (of the array) are contiguous in main memory. The location (index value) of the midpoint can be determined by a simple calculation.
- - - - Since only the items at the head and tail of a queue can be accessed, that makes those the two key parts of the structure. Any new items added to the queue have to appear at one of those two locations.
        Adding an item to a queue is called a PUSH command in assembly language. When an item is added, the pointers are updated to connect them to the existing items.
        The POP command retrieves and removes an item from the queue. Once an item is removed, the pointers in the queue are updated (usually incremented by 1) so they no longer point to it.
    - - FIFO queue = 'buffer'. If data is coming in too fast an error called a 'buffer overflow' happens where it just cannot store any more data because it has used up its allocated memory, and if the buffer runs empty a 'buffer underflow' occurs which or may not be an issue depending on the system.
    - - We need to have a class that can do the following
        
        Create a queue instance
        
        Add items - enqueue
        
        Retreive items - dequeue
        
        Is queue empty query
        
        Report the size of the queue
        Python has good support of the list data structure. This will be used to create a queue class. The tail of the queue is to be at position zero in the list so we can use the built-in Python .insert function to add items. The head of the queue is the last item in the list.
        
        class Queue: def__init__(self): self.items = [] # create an empty list def isEmpty(self): return self.items == [] # the == is a comparison True if empty def enqueue(self,item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def size(self): return len(self.items
    - - The main operations for a queue are adding items to the back of the queue (called enqueue) and removing items from front of the queue (called dequeue).
        With a linear queue, stored in an array, the queue will gradually move "up" along the array until the end of the array is reached.
        Notice that when an item dequeued, the front pointer moves.
    - - The front index pointer is initialised to 0 and the rear index pointers is initialised to −1. The rear index pointer will be incremented every time you add an item to the queue, so this initial value will ensure that the first item is added into the first position of the array (position 0). Once the first item has been added, front and rear will point to this element in the array.
    - - Before adding an item to the queue you need to check that the queue is not full. When the rear index pointer is pointing to the final slot of the array, there is no room to add new items. A subroutine is_full() can be defined to carry out this check.
        If the end of the array has not been reached, the rear index pointer is incremented and the new element is added to the queue.
        As this queue is a linear queue, no attempt is made to re-use space at the start of the array. Thus you will get a 'queue is full' message when the last position in the array is used, no matter how many items are on the queue.
    - - Before taking an element from the queue you need to check that the queue is not empty. A subroutine is_empty() can be defined for this purpose. The subroutine will check whether the front index pointer is ahead of the rear index pointer.
        If the queue is not empty, the element at the front of the queue is returned and front is incremented by 1
    - - Circular queue reuses the empty slots at the front of the array that are caused when elements are removed from the queue. As items are enqueued, and the rear index pointer reaches the last position of the array, it wraps around to point to the start of the array. As items are dequeued front index pointer will wrap around until it passes the rear index pointer (shows queue is empty).
    - - When you write code to manipulate items in a circular queue, you must be able to advance the index pointers so that they will reset to 0 once the end of the array has been reached.
        You can calculate the new position for the index pointer by using the following expression: (pointer + 1) MOD MAX_SIZE
        where pointer is front or rear and MAX_SIZE is the maximum number of elements of the queue.
    - - Front index pointer is initialised to −1. This will allow you to be certain that you are dealing with an empty queue.
    - - Before a item can be enqueued, you must check whether the array is full. It will be full if the next position to be used is occupied by the item at the front of the queue.
        If the queue is not full, the rear index pointer must be adjusted to reference the next free position so that the new element can be added. With a circular queue, the next free position may be position 0.
        If the item is the first to be added to the queue, the front index pointer is set to 0.
    - - Before attempting to remove an element from the queue you need to check that the queue is not empty. Subroutine is_empty() is called to check whether the front index pointer is -1.
        If the queue is not empty, the item at the front of the queue is dequeued. If this is the only item that was in the queue, the front and rear pointers are reset. Otherwise the front pointer is advanced to reference the next item in the queue.
        You do not need to delete the element that has been dequeued. The front index pointer is adjusted and the position in the array will be overwritten in future enqueue operations.
    - - If you want to implement a priority queue, you may find it best to use OOP. Encapsulating the data and methods within a class definition provides a neat solution.
        The class has public methods to:
        
        get the value of data
        
        get the value of priority
        
        get and set the value of next
        
        The PriorityQueue class has two private attributes:
        
        front - a pointer to the front of the queue
        
        rear - a pointer to the end of the queue
        
        The class also has public methods to:
        
        get and set the value of front
        
        get and set the value of rear
        
        It is possible to implement the class without a rear pointer but having one allows a new node of the lowest priority to be inserted directly at the end without having to traverse the whole list.
        The enqueue method
        You must find the correct position for the new element. Items are positioned ahead of elements of lower priority and behind elements of higher priority. If there are elements with equal priority the new element will be placed at the end of this part of the list. Solution must take into account specific cases:
        
        the queue might be empty
        
        there may be no items of equal priority
        
        there may be no items of lower priority
        
        there may be no items of higher priority
        
        The dequeue method
        When you remove an element from a queue, you always take the item at the front (of the queue) and adjust the pointer so that front points to next node (or is set to Null if the queue is then empty).
        Using the classes
        To use the classes you need to create an instance of a priority queue and then deploy its methods. The code shows:
        
        instantiation of the queue
        
        enqueueing two items
        
        dequeueing an item
  - - - A stack can involve a static or dynamic implementation.
        Static array implementation
        First element of the array, located at position 0, will be the bottom of the stack. The stack will have a fixed capacity, if you continuously add items to the stack, it will result in a stack overflow. Static implementations must include an is_full() operation to check whether a stack is at its maximum capacity. Stack underflow can occur if you try remove elements from an empty stack.
        Dynamic linked list implementation
        New elements will be added to the front of the linked list, so the head of the list can be used as the top pointer. When head is a null pointer the stack is empty. If the size of the stack needs to be constrained, an additional variable can be used to track the number of elements on the stack.
    - - When using a static array, you need to check that there is space in the stack, before pushing an element onto the stack. A subroutine is_full() can be used to check whether top has reached the maximum capacity.
        If there is room on the stack, the variable top is incremented by 1 and the element is added.
    - - Before popping an element from the stack, you need to check that the stack is not empty. A subroutine is_empty() can be defined for this purpose.
        If the stack is not empty, the element at the top of the stack will be returned and top will be decremented to point to the element below. Element does not need to be removed from the array, as it can be overwritten next time a new item is pushed onto the stack.
    - - When you peek an element, you must return the data that is located at the top of the stack, you must not adjust the top pointer.
        The subroutine is_empty() is called to check if the stack is empty. If the stack is not empty, element referenced by top will be returned.
    - - Stacks have many uses: checking for balanced parentheses in an expression, and converting postfix to infix notation and vice versa. They can be used to maintain a list of operations for an 'undo' function in a piece of software, where the most recent operation is the first to be undone. Stacks are used to facilitate recursive subroutines where the state of each call is stored in a stack frame and placed on a stack.
    - - Using the classes
        To use the classes, you need to create an instance of a stack and then deploy its methods.
        
        Instantiation of the stack
        
        Pushing two items onto the stack
        
        Peeking at the item on top of the stack
        
        Popping an item from the stack