QUEUE

QUEUE

================================================================================

• A Queue is defined as a linear data structure that is open at both ends. 
• The operations are performed in First In First Out (FIFO) order.

• A Queue is like a line waiting to purchase tickets, where the first person in line is the first person served. (i.e. First come first serve).
• Position of the entry in a queue ready to be served, that is, the first entry that will be removed from the queue, is called the front of the queue(sometimes, head of the queue)
• Similarly, the position of the last entry in the queue, that is, the one most recently added, is called the rear (or the tail) of the queue

• Queue Operations:
• enqueue: Add a new element to the rear of queue. It requires element to be added and returns nothing.
• dequeue:  Removes the elements from the front of queue. It does not require any parameters and returns the deleted item.
• isEmpty: Check the whether the queue is empty or not. It does not require any parameter and returns a Boolean value.
• isFull: Check the whether the queue is full or not. It does not require any parameter and returns a Boolean value.

• Types Of Queues:
• Linear Queue
• Circular Queue
• Priority Queue
• Double Ended Queue (deque)

• Linear Queue:
• It is generally referred as Queue
• No proper utilization of memory

• Operations of Linear Queue:

• Algorithm for Insertion:
1. begin
2. if (rear == sizeof(queue)-1)
1. return "Queue is full"
3. end if
4. else
1. increment rear 
2. queue[rear] = assign value
3. increment front
5. end else
6. end

• Flow Chart for Insertion: 

• Algorithm for Deletion:
1. begin
2. if (front == -1)
1. return "Queue is empty"
3. end if
4. else
1. store value of queue[front]
2. increment front
3. if (front == rear)
1. set front = -1 and rear = -1
4. end if
5. else
1. increment front
6. end else
5. end else
6. end

• Flow Chart for Deletion:

• Algorithm for isFull:
1. begin
2. if (rear == sizeof(queue)-1)
1. return true
3. end if
4. else
1. return false
5. end else
6. end

• Flow Chart for isFull:









• Algorithm for isEmpty:

1. begin
2. if (front == -1)
1. return true
3. end if
4. else
1. return false
5. end else
6. end

• Flow Chart for isEmpty:

• Circular Queue:
• Proper utilization of memory
• Increment front and rear in circular fashion i.e. 0, 1, 2, ...... , Size-1, 0, 1, ....

• Operations of Circular Queue:

• Algorithm for Insertion:

1. begin
2. if ((front == -1 && rear == sizeof(queue)-1) || (rear== front&& rear!= -1) )
1. return "Queue is full"
3. end if
4. else
1. if (rear == sizeof(queue) -1)
1. rear = 0
2. end if
3. else
1. increment rear
4. end else
5. queue[rear] = assign value
5. end else
6. end

• Flow Chart for Insertion:









• Algorithm for Deletion:
1. begin
2. if (rear == -1 && front == -1)
1. return "Queue is empty"
3. end if
4. else
1. if(front == sizeof(queue)-1)
1. store value of queue[0]
2. end if
3. else
1. store value of queue[front++]
4. end else
5. if (front == sizeof(queue)-1)
1. front = 0
6. end if
7. else
1. increment front
8. end if
9. if (front == rear)
1. set front = -1 and rear = -1
10. end if
5. end else
6. end

• Flow Chart for Deletion:

• Algorithm for isFull:
1. begin
2. if ((front == -1 && rear == sizeof(queue)-1) || (rear== front&& rear!= -1) )
1. return true
3. end if
4. else
1. return false
5. end else
6. end

• Flow Chart for isFull:






• Algorithm for isEmpty():
1. begin
2. if (rear == -1 && front == -1)
1. return true
3. end if
4. else
1. return false
5. end else
6. end

• Flow Chart for isEmpty():

• Priority Queue:
• Each element is associated with some priority
• Element with highest priority is popped out first
• No FIFO behavior (First In First Out)
• Typically it is implemented as sorted linked list
• While insertion element is added at appropriate position as per its priority
• So insertion time complexity will be 0(1)
• While deleting first element is deleted, as it is element with highest priority.

• Double Ended Queue (deque):
• Can push/pop elements from both sides i.e. front as well as rear
• Usually implemented as doubly linked list with head and tail

• Algorithm for Insertion using rear:
1. begin
2. if (rear == sizeof(queue)-1)
1. return "Queue is full"
3. end if
4. else
1. increment rear
2. queue[rear] = assign value
5. end else
6. if (front == -1)
1. set front = 0
7. end if
8. end

• Flow Chart for Insertion using rear : 

• Algorithm for Insertion using front:

1. begin
2. if (front == -1)
1. return "Queue is full"
3. end if
4. else
1. decrement front
2. queue[front] = assign value
5. end else
6. if (rear == sizeof(queue)
1. set rear = sizeof(queue)-1
7. end if
8. end

• Flow Chart for Insertion using front:

• Algorithm for Deletion using front:

1. begin
2. if (front == -1)
1. return "Queue is empty"
3. end if
4. else
1. store value of queue[front]
2. if (front == rear)
1. set front = -1 and rear = -1
3. end if
4. else
1. increment front
5. end else
5. end else
6. end

• Flow Chart Deletion using front:













• Algorithm for Deletion using rear:

1. begin
2. if (rear == sizeof(queue))
1. return "Queue is empty"
3. end if
4. else
1. store value of queue[rear]
2. if (front == rear)
1. set front = sizeof(queue) and rear = sizeof(queue)
3. end if
4. else
1. decrement rear
5. end else
5. end else
6. end

• Flow chart for Deletion using rear:

• Algorithm for isFull using rear:

1. begin
2. if (rear == sizeof(queue)-1)
1. return true
3. end if
4. else
1. return false
5. end else
6. end

• Flow Chart for isFull using rear:

• Algorithm for isFull using front:

1. begin
2. if (front== -1)
1. return true
3. end if
4. else
1. return false
5. end else
6. end

• Flow Chart for isFull using front:

• Algorithm for isEmpty using front:

1. begin
2. if (front== -1)
1. return true
3. end if
4. else
1. return false
5. end else
6. end

• Flow Chart for isFull using front:



• Algorithm for isEmpty using rear:

1. begin
2. if (rear== sizeof(queue))
1. return true
3. end if
4. else
1. return false
5. end else
6. end

• Flow Chart for isEmpty using rear: