JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

SQP2 Queue Implementation Using Array

What is Queue?

A queue is a linear list of elements in which deletions can take place only at one end called the front, and insertions can take place only at the end called the rear. The queue is a First In First Out type of data structure (FIFO), the terms FRONT and REAR are used in describing a linear list only when it is implemented as a queue.

Notes

Note: Zoom for Better Understanding

In computer science queues are used in multiple places e.g. in a time-sharing system program with the same priority from a queue waiting to be executed. A queue is a non-primitive linear data structure. it is a homogeneous collection of elements.
The process to add an element into a queue is called Enqueue and the process of removal of an element from the queue is called Dequeue.

Basic features of Queue

Like Stack, queue is also an ordered list of elements of similar data types.

Queue is a FIFO( First in First Out ) structure.

Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.

peek() function is used to return the value of first element without dequeuing it.

Implementation of Queue Data Structure

The queue can be implemented in two ways :

Static implementation (using arrays)

Dynamic implementation (using linked list)

Some Basics operations on the Queue

push()

pop()

top() or peek()

size()

empty()

Push(): Push Function used for the put the element to the Queue if the Queue limit is Not Overflow under the Limit or The process of adding new elements to the top of the Queue is called Enqueue operation.
Conditions:

Check for the overflow condition.

Check if the queue is empty.

If the queue is empty, then both FRONT and REAR are set to zero, so that the new value can be stored at the 0th location. Otherwise, if the queue already has some values, then REAR is incremented so that it points to the next location in the array.

The value is stored in the queue at the location pointed by REAR.

                    push (Queue, Size, Front, Rear, x) 
                        {
                        if (Rear == Size - 1) 
                            Print Over flow 
                        if (Front == -1) 
                            Set Front = 0 && Rear = 0 
                        Else 
                            Rear = Rear + 1 
                            Queue[Rear] = x 
                            EXIT
                        }
                 

Pop(): Pop Function The process of deleting an element. from the front of the Queue is called POP operation also know as Dequeue
Conditions:

Check for underflow condition. An underflow occurs if FRONT == –1 or FRONT > REAR.

If queue has some values, then FRONT is incremented so that it now points to the next value in the queue.

                    pop (Queue, Size, Front, Rear) 
                        { 
                        if (Front == - 1) 
                            Print Under flow 
                        x = Queue [Front] 
                        if (Front == Rear) 
                            Set Front = -1 && Rear = -1 
                        Else 
                            Front = Front + 1 
                            EXIT
                        }
                 

Top() or Peek(): Means Print the Front Element from the Queue.
Conditions:

Check if the Queue is not Empty.

If the Queue is empty, then print error of underflow and exit the program.

If the Queue is not empty, then print the element at the front of the Queue

                    top (Queue, Size, Front, Rear) 
                    { 
                        if (Front == - 1) 
                            Print Under flow 
                        else:
                            x = Queue [Front] 
                            print(x)
                            Exit
                        }
                 

Size(): Size function used for find the Size of the Queue.
Conditions:

Check if the Queue is not Empty.

If the Queue is empty, then print -1

If the Queue is not empty, then print Limit is our Size of the Queue

                    size (Queue, Size, Front, Rear) 
                    { 
                        if (Front == - 1) 
                            Print Under flow 
                        else:
                           print(Size)
                            Exit
                        }
                 

Empty(): Empty function is Used for check Queue Stck is Empty or Not.
Conditions:

Check if the Queue is not Empty.

If the Queue is Not empty, then print -1 or False

If the Queue is empty, then print 1 or True

                    empty (Queue, Size, Front, Rear) 
                    { 
                        if (Front == - 1) 
                            Print print(1)
                        else:
                            print(-1)
                            Exit
                        }
                 

Code Zone!

Time Complexity:Push Operation : O(1)
Pop Operation : O(1)
Top Operation : O(1)
Empty Operation: O(1)
Size Operation: O(1)
Search Operation : O(n)
Space Complexity:O(N) O(N) Size of the Queue