Chapter 6
Queue
*Note
Linear and Non-Linear data structures. A data structure is said to be linear if the elements form a sequence, for example, Array, Linked list, queue etc. Elements in a nonlinear data structure do not form a sequence, for example, Tree, Hash tree, Binary tree, etc.
What is Queue?
In general, a line or sequence of people or vehicles awaiting their turn to be attended to or to proceed and a list of data items, commands, etc., stored so as to be retrievable in a definite order, usually the order of insertion.
In the data structure, a queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle.
Enqueue The process to add an element to the queue, means to insert an item into the entrance of the queue.
Dequeue The process of removal of an element from the queue, means removing through Exit item.
The picture demonstrates the FIFO access.
The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.
Another Queue representation
Figure 1 Queue
Explaining the First-In-First-Out methodology we can understand from diagram given below.
The queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR (also called tail), and the deletion of existing element takes place from the other end called as FRONT (also called head), can be seen in the diagram below.
Basic features of Queue
Like Stack, Queue is also an ordered list of elements of similar data types.
The 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 often used to return the value of the first element without dequeuing it or Gets the element at the front of the queue without removing it.
isfull() − Checks if the queue is full.
isempty() − Checks if the queue is empty.
Example Peek ( )
int peek() {
return queue[front];
}
isfull (Algorithm)
begin procedure isfull
if rear equals to MAXSIZE
return true
else
return false
endif
end procedure
Example
bool isfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
isempty () Algorithm
begin procedure isempty
if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure
Example
bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}
Applications of Queue
Queue, as the name suggests is used whenever we need to manage any group of objects in an order in which the first one coming in, also gets out first while the others wait for their turn, like in the following scenarios:
Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
In real life scenario, Call Center phone systems use Queues to hold people calling them in an order, until a service representative is free.
Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e. First come first served.
Implementation of Queue
The queue can be implemented using an Array, Stack or Linked List. The easiest way of implementing a queue is by using an Array. Initially the head (FRONT) and the tail (REAR) of the queue points at the first index of the array (starting the index of the array from 0). As we add elements to the queue, the tail keeps on moving ahead, always pointing to the position where the next element will be inserted, while the head remains at the first index.
Steps for Queue
Operation Enqueue
Step 1 − Check if the queue is full.
Step 2 − If the queue is full, produce overflow message and exit.
Step 3 − If the queue is not full, increment the rear pointer to point the next empty space.
Step 4 − Add data element to the queue location, where the rear is pointing.
Step 5 − return success
Figure 2 adding a new Element in Queue (enqueue operation)
Algorithm for enqueue operation
procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
Example
int enqueue(int data)
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
end procedure
Operation dequeue
Accessing data from the queue is a process of two tasks − access the data where the front is pointing and remove the data after access. The following steps are taken to perform dequeue operation −
Step 1 − Check if the queue is empty.
Step 2 − If the queue is empty, produce underflow message and exit.
Step 3 − If the queue is not empty, access the data where the front is pointing.
Step 4 − Increment front pointer to point to the next available data element.
Step 5 − Return success.
Figure 3 Dequeue
Algorithm for dequeue operation
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure
Example
int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
Please understand this process carefully as explained in lecture. Given below in Figure 4
Figure 4 Enqueue and Dequeue
When we remove an element from Queue, we can follow two possible approaches (mentioned [A] and [B] in above diagram). In [A] approach, we remove the element at head position, and then one by one shift all the other elements in forwarding position. In approach [B] we remove the element from head position and then move the head to the next position.
In approach [A] there is an overhead of shifting the elements one position forward every time we remove the first element. In approach [B] there is no such overhead, but whenever we move head one position ahead, after removal of the first element, the size of Queue is reduced by one space each time.
Key terms (Just for Knowledge) |
FIFO queue A queue in which the first item added is always the first one out. Priority queue A queue in which the items are sorted so that the highest priority item is always the next one to be extracted. Life critical systems Systems on which we depend for safety and which may result in death or injury if they fail: medical monitoring, industrial plant monitoring and control and aircraft control systems are examples of life critical systems. Real time systems Systems in which time is a constraint. A system which must respond to some event (e.g. the change in attitude of an aircraft caused by some atmospheric event like wind-shear) within a fixed time to maintain stability or continue correct operation (e.g. the aircraft systems must make the necessary adjustments to the control surfaces before the aircraft falls out of the sky!). |
Priority Queue
In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
Heap
Heap is a special tree-based data structure that satisfies the following special heap properties
Shape Property
Heap Property
Shape Property
A heap is a complete binary tree – all levels are fully filled, except possibly the bottom level, which may be partially filled from left to right
Difference between Complete and incomplete tree is given below.
Heap Property
All nodes are either [greater than or equal to] or [less than or equal to] each of its children. If the parent nodes are greater than their child nodes, heap is called a Max-Heap, and if the parent nodes are smaller than their child nodes, heap is called Min-Heap.
Min-Heap − Where the value of the root node is less than or equal to either of its children.
Figure 5 for Input → 35 33 42 10 14 19 27 44 26 31
Max-Heap − Where the value of the root node is greater than or equal to either of its children. (Gif is also available in folder)
Figure 6 for Input → 35 33 42 10 14 19 27 44 26 31
Max Heap Construction Algorithm
Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.
Max Heap Deletion Algorithm
Let us derive an algorithm to delete from max heap. Deletion in Max (or Min) Heap always happens at the root to remove the Maximum (or minimum) value.
Please see the max_heap_animation.gif to understand properly