A queue is a linear data structure that follows the First In, First Out (FIFO) principle, which
means that the element which is inserted first in the queue will be the first one to be removed
from the queue. A good example of a queue is a queue of customers purchasing a train ticket,
where the customer who comes first will be served first.
A linked queue consists of two pointers, i.e., the front pointer and the rear pointer. The front
pointer stores the address of the first element of the queue, and the rear pointer stores the address
of the last element of the queue.
Insertion is performed at the rear end, whereas deletion is performed at the front end of the queue.
If front and rear both points to NULL, it signifies that the queue is empty.
•Insertion
Insertion
Insert operation or insertion on a linked queue adds an element to the end of the queue. The new
element which is added becomes the last element of the queue.
• Deletion
Deletion
Deletion or delete operation on a linked queue removes the element which was first inserted in
the queue, i.e., always the first element of the queue is removed.
• Display
Print function is used to display the content of the queue. Since we need to iterate over each
element of the queue to print it, the time complexity of the print function is O(n), where n =
number of nodes in a queue.
• Check if queue contains at least one element or not.
• If the queue is empty print “No elements in the queue.”
• Else, define a node pointer and initialize it with the front.
• Display data of node pointer until the next node pointer becomes NULL.
Step 1: Create a new node pointer: ptr = (struct node *) malloc (sizeof(struct node))
Step 2: Now, two conditions arise, i.e., either the queue is empty, or the queue contains at least one element.
Step 3: If the queue is empty, then the new node added will be both front and rear, and the next pointer of front and rear will point to NULL.
Step 4: If the queue contains at least one element, then the condition front == NULL becomes false. So, make the next pointer of rear point to new node ptr and point the rear pointer to the newly created node ptr Hence, a new node(element) is added to the queue
Step 1: Check if the queue is empty or not
Step 2: If the queue is empty, i.e., front==NULL, so we just print 'underflow' on the screen and exit.
Step 3: If the queue is not empty, delete the element at which the front pointer is pointing. For deleting a node, copy the node which is pointed by the front pointer into the pointer ptr and make the front pointer point to the front's next node and free the node pointed by the node ptr. This can be done using the following statement: *ptr = front; front = front -> next; free(ptr)