introduction to queue

Queue is a linear data structure 

Queue follows First-In-First-Out (FIFO) which means that the element which is inserted first will be accessed first from the queue. 

they are similar to Stacks but a stack is open at one end but a queue is open at both its ends.

One end is always used to insert data (enqueue) and the other is used to remove data (dequeue).

                              

Operations on Queue: 

Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.

Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.

Front: Get the front item from queue.

Rear: Get the last item from queue.

 

array representation of queue:

We can easily represent queue by using arrays. lets take two variables front and rear, that are implemented in the case of every queue. Front and rear variables point to the position from where insertions and deletions are performed in a queue. Initially, the value of front and queue is -1 which represents an empty queue.

insert any element in a queue:

Check if the queue is already full by comparing rear to max - 1. if so, then return an overflow error.

If the item is to be inserted as the first element in the list, in that case set the value of front and rear to 0 and insert the element at the rear end.

Otherwise keep increasing the value of rear and insert each element one by one having rear as the index.

Step 1: IF REAR = MAX - 1

Write OVERFLOW

Go to step

[END OF IF]

Step 2: IF FRONT = -1 and REAR = -1

SET FRONT = REAR = 0

ELSE

SET REAR = REAR + 1

[END OF IF]

Step 3: Set QUEUE[REAR] = NUM

step 4:EXIT

implementation in c:

void enque(int queue[], int max, int front, int rear, int x)   
{  
    if (rear + 1 == max)  
    {  
        printf("overflow");  
    }  
    else  
    {  
     if(front == -1 && rear == -1)  
        {  
            front = 0;  
            rear = 0;  
        }  
      else  
        {  
            rear = rear + 1;   
        }  
        queue[rear]=x;  
    }  
} 

delete an element from the queue:

If, the value of front is -1 or value of front is greater than rear , write an underflow message and exit.

Otherwise, keep increasing the value of front and return the item stored at the front end of the queue at each time.

Step 1: IF FRONT = -1 or FRONT > REAR

Write UNDERFLOW

ELSE

SET VAL = QUEUE[FRONT]

SET FRONT = FRONT + 1

[END OF IF]

Step 2: EXIT

int dequeue (int queue[], int max, int front, int rear)  
{  
    int x;   
    if (front == -1 || front > rear)   
    {  
        printf("underflow");  
    }  
    else   
    {  
        x = queue[front];  
        if(front == rear)  
        {  
            front = rear = -1;  
            else   
            front = front + 1;   
          
        }  
        return x;  
    }  
}   

Time Complexity: Time complexity of all operations like enqueue(), dequeue() is O(1).