Introduction to Queue Data Structure

The Queue is an ordered set of elements in which insertions are from the rear and deletions are from the front. It is a First in First Out structure.

1. Static Implementation:
A Queue is implemented statically by using an array of size MAX to hold stack elements and two integers – front and rear. The ‘front’ stores the position of the current front element and ‘rear’ stores the position of the current rear element of the queue. A queue is a single entity that is a structure made up of the array, rear, and front. The Queue elements can be integers, characters, strings or user-defined types.



The operations to be performed on a Queue are:
1. init (Q) – Create an empty queue by initializing both front and rear to -1 indicating the queue is empty
2. add (Q, x) – adding an element x to the rear end of the queue Q
3. delete (Q) – deletes the element from the front of the queue Q
4. peek (Q) - returns the front element from the queue without deleting the element from the Queue
5. isEmpty (Q) – check if the queue is empty, that is, when rear equals front
6. isFull (Q) – check if the Queue is full which happens when rear equals MAX -1

2. Dynamic Implementation:
A Queue is implemented dynamically by using a Linked list where each node in the linked list has two parts, the data element and the pointer to the next element of the queue. Since Queue should be a single entity, we need to use only one external pointer while here we need two one for the rear and one to the front. To avoid this we use a circular linked list and
Queue pointer is pointing to the rear of the queue. The front can be easily accessed as it is next to rear. The Queue elements can be integers, characters, strings or user-defined types. There is no restriction on how big the Queue can grow.
The operations to be performed on a Queue:
1. init (Q) – Create an empty queue as a circular linked list by initializing S to NULL indicating that the queue is empty.
2. add (Q, x) – Adding an element x to the queue Q requires the creation of node containing x and putting it next to the rear and rear points to the newly added element. This changes the rear pointer Q and the function should return the changed value of Q. The function call will be as follows
Q=add(Q, x);
3. delete (Q) – deletes the front node from the queue Q which is actually next element to the rear pointer Q. However if the queue contains only one element, (Q->next == Q) then deleting this single element can be achieved by making empty Q (Q =NULL). Since the rear pointer Q is changed in this case, the function should return the changed value of Q. The function call will be as follows
Q=delete(Q);
4. peek (Q) - returns the data element in the front (Q->next) node of the Queue Q.
5. isEmpty (Q) – Check if the Queue is empty which is equivalent to checking if Q==NULL


Thanks
Mukesh Rajput
Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..

Post A Comment:

0 comments:

Thanks
Mukesh Rajput