![]() ![]() IsEmpty: It is used to check whether the queue is empty or not. Basic Functions of QueueĮnqueue: It is used to add an element at the rear of the queue.ĭequeue: It is used to remove an element from the front of the queue. The value of both the Rear and Front is set to -1 initially and then these values are incremented or decremented as the elements are inserted and deleted. Hence we can say that the Queue's working principle is based on First-In-First-Out(FIFO).Ī Queue is a linear data structure in which elements are inserted from one end called the Rear and are removed from the other end called the Front. Whoever is first, is going to get the ticket first. You feedback is highly appreciated.The concept of a Queue data structure is similar to the queue we come across in our day-to-day life like at a bus stop.Īnd you have to wait until your number arrives, right? Link to the above code on my github profile, Queue using linked list. Space complexity = O(1) since no extra or any auxiliary space is used for the above operations. Time complexity of display operation is O(N) where N = number of elements in the queue, since all the elements of the queue are iterated. O(1), since only the rear and front pointers need to be updated and no iteration is performed over the elements. Time complexity of enqueue and dequeue operations is constant i.e. QueueUsingLinkedList q = new QueueUsingLinkedList() * method to display all elements of the queue */ * method to remove an element from the queue */ attach the new node at the rear end and update rear pointer * method to add a new element to the queue */ ![]() QueueNode class representing a node in the linked list constructor to initialize front and rear pointers To dequeue an element, a node is removed from the front end of the queue.ĭiagrammatic representation: Code implementation:.To enqueue an element, a new node is created and attached to the rear end of the queue.Declare a QueueNode class with data as an integer variable which will hold the data of a queue node and a next pointer of type QueueNode which will point to the next node in the queue.display(): This method is used to display all the queue elements by iterating over the elements.dequeue(): This operation is used to dequeue en element from the front of the linked list.enqueue(int data): This operation is used to enqueue an element to the rear end of the linked list.Two node pointers front and rear is maintained at the head and at the tail end of the linked list. The enqueue operation is performed at the tail end of the linked list and dequeue is performed at the head end of the linked list. To solve the above problem, queue can be implemented using linked list. But when the number of elements stored in the array becomes large it can give poor performance. This works well when the number of elements is small. In the queue implementation using array, a major drawback is when an element is dequeued from the front of the array, all the elements have to be shifted to the left by 1 position. Knowledge of Java, basic data structures, working of queue, linked list and understanding of time and space complexity. This post discusses how queue implementation using linked list gives better performance and reduces the overhead of shifting the elements to the left, every time an element is dequeued from the queue. Queue can also be implemented using linked list to overcome the disadvantages of the queue implementation using array. In the previous post I discussed about queue implementation using circular array.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |