What do you mean by queue in Data structure and an algorithm?

Question

Queue

• What is queue? 
• Examples
• figure
• Basic features of queue
• Reprsentation of queue
• various types of queue
• algorithm
• application of queue

Answer 1

Queue

• A queue is a linear list of elements in which deletions can take place only at one end, called the front and insertion can take place only at the other end called the rear.
• A queue is a non-primitive linear data structure. Queues are called First in first out (FIFO) .
• Queue is a linear data structure in which the insertion and deletion operations are performed at two different ends.

Real- Time Examples :

1. Single line one way road, where the vehicle enters first, exist first.
2. Queues at movie theater ticket counter whoever is standing first will get the first turn so it is like first in first out.
3. Queues at Bus-stops or Railway Stations or Airports.
4. When multiple users send print jobs to a printer, each printing job is kept in the printing queue. Then, the printer prints jobs according to FIFO basis.

Basic features of queue

• Like stack, the queue is also an ordered list of elements of similar data types.
• Queue follows first in first out principle. To perform insertion operation on a queue called as Enqueues.
• To delete any data item from the queue. The deletion operation called Dequeue.
• An element in a queue is known as an item.
• The number of elements that a queue can accommodate is known as length.
• To perform insertion and deletion operation must be check the conditions are:
• The queue is empty then, the condition is front==rear
• If the queue is full then, the condition is Rear=N(N is a maximize of the array).

Operations on Queue:

A queue is an abstract data structure(ADT) that allows the following basic operations can be performed on queue.

• Enqueue: The enqueue operation is used to add(insert) the element at the rear end of the queue. If the queue is full, then it is said to be an Overflow condition.
• Dequeue: This deletes element from the front-end of the queue. It also returns the element which has been removed from the front-end. It returns an integer value. The dequeue operation can also be designed to void. If the queue is empty, then it is said to be an Underflow condition.
• Peek:  Gets the element at the front of the queue without removing it.
• Queue overflow (isfull): When the Queue is completely full, then it shows the overflow condition.
• Queue underflow (isempty): When the Queue is empty, i.e., no elements are in the Queue then it throws the underflow condition.

Python Program using list as a queue:-

#Python program using list as a queue

#declaring an empty list

list = []

list.append(1)

print("enqueue:",list)

list.append(2)

print("enqueue:",list)

list.append(3)

print("enqueue:",list)

#always pop first item

list.pop(0)

print("dequeue:",list)

print("peek:",list[-1])

Output:

enqueue:[1]

enqueue:[1, 2]

enqueue:[1, 2,3]

dequeue:[2, 3]

peek:3

Using collections.deque as a queue

from collections import deque

q = deque()

q.appendleft(100)

q.appendleft(200)

q.appendleft(300)

print(q)

q.pop()

print(q)

q.pop()

q.pop()

Output:-

deque([300, 200, 100])

deque([300, 200])

300 

Implement queue class using collections.deque

from collections import deque

class Queue:

    

    def __init__(self):

        self.queue = deque()

    

    def enqueue(self, val):

        self.queue.appendleft(val)

        

    def dequeue(self):

        return self.queue.pop()

    

    def is_empty(self):

        return len(self.queue)==0

    

    def size(self):

        return len(self.queue)

pq = Queue()

pq.enqueue(300)

pq.enqueue(200)

pq.enqueue(100)

print(pq.size())

print(pq.dequeue())

print(pq.dequeue())

Output:

size of queue 3

300

200

Representation of Queues

There are two ways to represent a queue in a memory

• Using an array
• Using a linked list.

Representation of a queue using an array

• A one-dimensional array can be used to represent a queue. With this representation, two pointers FRONT and REAR are used to indicate the two ends of the queue.

Three states of a queue

• Queue is an empty

Front=0

Rear=0(and/or)

• Queue is full

Rear=N

Front=1

• Queue contains element which are greater than 1:

FRONT≤REAR

Number of elements =Rear-front+1

Insertion enqueue operation

Algorithm

Steps

1. Start
2. If (rear=n) then 
3. Print “queue is full” 
4. Exit  
5. Else  
6. If (rear=0) and (front=0) then// queue is empty.
7. Front=1 
8. End if  
9. Rear=rear+1 
10. Q[rear]=item 
11. End if  
12. Stop 

Deletion or dequeue operation

Algorithm

Steps

1. Start 
2. If (front=0) then 
3. Print “queue is empty” 
4. Exit  
5. Else 
6. Item=Q[front] 
7. If [front==rear] 
8. Rear=0 
9. Front=0 
10. Else 
11. Front=front+1 
12. End if  
13. End if  
14. Stop 

Representation of queue using linked list

A double linked list which allows us to move both ways.

Two states if the queue:

Queue is empty:

Front=rear=header

Queue contains at least one element

Various queue structure

We have discussed two different queue structures: using array and using a linked list. Other than two, there are some more known queue structure and are as follows:

• Circular queue
• Double-ended queue
• Priority queue   

More detail about different types o queue- click here

Application of queues:

• Serving requests on the single shared resources like a Printer, CPU Scheduling,  Disk Scheduling, etc.

• Queues are used, when data is transferred asynchronously (data not necessarily received at the same rate as sent) between two processes. For eg. include pipes, IO Buffers, file IO, sockets, etc.

• Breadth-first search(BFS) uses a queue data structure to find an element from a graph.  

• Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.

• It is used in operating systems for handling interrupts.