The Heap Space

  // Linked list node to maintain the queue class Node{     int data;     Node next;       // Cretaion of a queue node     // Time Complexity - O(1) , Space Complexity - O(1)     Node(int x){         this.data = x;         this.next = null;     } } public class Main {       // head and tail of the linked list     Node head;     Node tail;       // function to enqueue an element 'x' to the end of queue     // Time Complexity - O(1) , Space Complexity - O(1)     public void enQueue(int x){         // create a new linked list node         Node newNode = new Node(x);               // if linked list / queue is empty         if(head==null){             head=newN...

  Algorithm : Enqueue: Check if the queue is full. If the queue is full, throw an error else : Fixing the position of endOFQueue: Check if endOFQueue has reached the last cell of the array if yes, then make endOFQueue=0 , as the queue is not full and it has space left towards the start of the array if no, then just simply increment endOFQueue by 1, as the queue is not full and it has space left towards the end of the array Once the position of endOFQueue is fixed by above, we simply put the data in the array at endOFQueue using arr[endOFQueue] Dequeue: Check is the queue is empty. If the queue is empty, throw an error else: Remove the element from start of queue i.e. arr[startOFQueue] Fix the new Postion of startOFQueue: Check if there was only one element in queue, using if(startOFQueue==endOFQueue) if yes, just simply set startOFQueue=endOFQueue=-1 if no, i.e. there are more than 1 element in queue, check the current position of start: if st...

  public class Main {     // Array to implement Linear queue     int[] arr;     // variables to maintain indexes of start and end of queue     int startOFQueue;     int endOfQueue;       // constructor     // Creating a queue - Time Complexity - O(1), Space Complexity - O(n) , where n = size     Main(int size){         this.arr=new int[size];         this.startOFQueue=0;         this.endOfQueue=-1;     }       // function to initialize the queue array      //Time Complexity - O(n), Space Complexity - O(1)     public void initializeArray(){         if(this.startOFQueue==0 && this.endOfQueue==-1){             for(int i=0; i<arr.length; i++){                 this.arr[i...

Follows First In First Out (FIFO) Implementation Options of queue : Arrays Linear queue Circular queue Linked List Linear queue (only, and not Circular queue) Why we need circular queue ?         Because in the array implementation of linear queue, when we perform deque operation, it causes few blank cells in linear queue (at the start of queue). Due to this, we waste a lot of space. Also, we do not want to shift the elements in the array to left (or start) so as to prevent empty cells at start as it will take O(n) time. We have to do it in O(1) time. For doing that we can again add new elements to the start and at the same time maintaining two pointers i.e. startOfQueue and endOfQueue. (See actual code implementation of circular queue using arrays) When to use queue / Advantages of queue ? 1. When we want to access data in FIFO order. 2. Data is not easily corrupted as the insertion and deletion of the elements in queue is done in ...