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

0 like 0 dislike
1.9k views

edited

Queue

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

0 like 0 dislike
by (562 points)
edited

## 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(selfval):

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

### 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:

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