Bits and Bytes

The tree is an abstract data structure which stores hierarchical data. For example, organisations have a hierarchical structure for employees. It is similar to the image given below. Several sergeants have to report to their respective captain. Now captains report to colonel. This colonel takes order from the general and assigns them to sergeants. Each of these consists of several levels. The general is on level 0, Colonel A and Colonel V are on level 1, Captain A, B and C are on level 2 and so on. Another terminology is height of the tree.  The height of a tree is longest path from the root node to any leaf node of the tree. Height of leaf node n=Level of leaf n+1.  Suppose we want to find the height of Private A. Height of private A= Level of Private A+1                                       =4+1                 ...

  Consider a group of patients waiting outside the doctor's cabin for consultation. The functioning of the clinic is First In First Out basis like a queue . Suddenly, a new patient arrives with a condition which requires immediate treatment.  Then, the doctor would treat this patient first and then continue treating other patients like the previous order. In a priority queue, each data element has priority. So that crucial data does not get stuck. High priority elements are dequeue before low priority elements. If multiple elements have the same priority number, then the deletion is on a first come first serve basis. When  array implements a priority queue, an additional  2-D array is required to store the priority. When a  linked list implements a priority queue, the node stores the priority number. Applications of priority queue: Bandwidth management. Dijkstra Algorithm. Huffman Coding. Best First Search Algorithm. CPU Scheduling

 Let's say another student wants to wait in the  queue to get his/her assignment checked. There is space available on the bench, but the student cannot occupy it.  If the students shift to left, then they can make space the new student. However, this is very time-consuming. So, logically the person would occupy the vacant seat. But, will make sure that when the professor calls the early entrants will go first. Assume a queue of length l. When the queue is empty, the number assigned to the front and rear is -1. In a circular queue, the front index comes right after the last index. Algorithm for enqueue: The queue is overflow if front=0 and rear=l-1. End the program. There are two cases for insertion: There is space from the rear side. If rear<l-1, then insert the element at queue[rear] and increment rear. There is space from front side.If rear=l-1 and front!=0, then set rear=0 and insert element at queue[rear]. Algorithm for dequeue: The queue is underflowing if rear=f...

A stack is a data structure which stores elements one after others.  A unique feature of this data structure is that we can use an  array or  linked list for its implementation. We are concerned about its functionality instead of it is implemented in code. Thus, the queue is an abstract data type.  Consider a group of students waiting outside the professor's cabin in line for project submission.  The queue increases when more people arrive.  The queue decreases when professor calls the student and he/she goes inside the cabin. Note that other students do not shift to fill vacant space. Thus people are served from First Come First Serve basis. This approach is known as First In First Out procedure. The process of addition of elements is called enqueue, and the process of deletion of elements is called dequeue. We can deduce an analogy that people are equivalent to data elements.  We use two variables for performing operations.  Rear/Back- Denotes...

A stack is a data structure which stores elements one above others. Consider a pile of coins. Each coin is a data element. Addition and removal of coins take place at one end. This place is called the top of the stack.  Image Credits: Pixelbay A unique feature of this data structure is that we can use an  array or  linked list for its implementation. We are concerned about its functionality instead of it is implemented in code. Thus, the stack is an abstract data type.  We use push operation for insertion and pop operation for deletion.  Stack uses LIFO approach which is an acronym for, "Last in first out". The newer elements are the ones which get popped first. There are two states which can be determined by the value of the top: Overflow- It means that the stack is full. Underflow- It means that the stack is empty. Advantages of the stack are: Easy insertion and deletion of elements.  Provides LIFO functionality which is not given by array and linked li...

Linked list as the name suggests is a list of elements grouped linearly.  Image Credits: Wikimedia Commons A unit element in a linked list consists of the following components: Data Address of neighbour element/s We refer to this unit element as a node. Therefore, a linked list is a set of nodes. The last node in the linked list points to null, indicating that the linked list has ended. Depending upon the number of nodes that are accessed directly, linked lists are further classified into: Singly Linked List Here, the primary node contains the address of the next node.  Imagine playing a game of treasure hunt. You know the first clue, which contains information to direct you to the second clue and so forth. Image Credits: Wikimedia Commons        2.  Doubly Linked List Here, the primary node contains the address of the previous as well as the next node. Imagine travelling in a metro train. You know the first stop. The trains traverse back and for...