Chapter # 06 : Queue Applications,Features & Types | Heap & Types

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.

ADAat2boujxcSfUBZokqFwa1VdIbqr+D+wxCqQWAafvjjz8BNHckVd690P4AAAAASUVORK5CYII= - Chapter # 06 : Queue Applications,Features & Types | Heap & Types

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

 

vHqgAAAAASUVORK5CYII= - Chapter # 06 : Queue Applications,Features & Types | Heap & Types

Figure 1​​ Queue

Explaining the First-In-First-Out methodology we can understand from diagram given below.

ueL048gAAAAASUVORK5CYII= - Chapter # 06 : Queue Applications,Features & Types | Heap & Types

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.

41FeuAwif8YAAAAASUVORK5CYII= - Chapter # 06 : Queue Applications,Features & Types | Heap & Types

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

wcggsk81jhbkgAAAABJRU5ErkJggg== - Chapter # 06 : Queue Applications,Features & Types | Heap & Types

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.

 

XlSHPTMxwAAAAASUVORK5CYII= - Chapter # 06 : Queue Applications,Features & Types | Heap & Types

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

9k= - Chapter # 06 : Queue Applications,Features & Types | Heap & Types

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

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.

9k= - Chapter # 06 : Queue Applications,Features & Types | Heap & Types9k= - Chapter # 06 : Queue Applications,Features & Types | Heap & Types

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.

2Q== - Chapter # 06 : Queue Applications,Features & Types | Heap & Types

 

 

 

 

 

 

 

 

 

 

Min-Heap − Where the value of the root node is less than or equal to either of its children.

 

2Q== - Chapter # 06 : Queue Applications,Features & Types | Heap & Types

 

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)

2Q== - Chapter # 06 : Queue Applications,Features & Types | Heap & Types

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