Deque.md

Deque(Double Ended Queue)

• Double-ended queue (abbreviated to deque) is an abstract data type that generalizes a Queue, for which elements can be added to or removed from either the front (head) or back (tail)
• In Normal Queue We can perform one operation at only one end. but dequeue can able to perform both insertion and removal of the item at both ends.
• Deque look similar like a queue but doesn't support FIFO structure
• Insertion and deletion of the element can be performed at both side of the queue(FRONT and REAR)

Operations Can Be Performed

- Insert at Front end.
- Delete from the Front end.
- Insert at Rear end.
- Delete from Rear end.
- Check Empty dequeue

Application Of Deque

• A steal Algorithm for job scheduling in multiprocessors environment
• U shaped tube in Science Lab

Types Of Deque

1. Input Restricted Deque

• Insertion can be done only from rear and deletion of the element can be done from both side(FRONT And REAR)

2. Output Restricted Deque

• Deletion from done only from Front End Insertion can be done at both ends.

Implementation Of Deque

• Using "collections" built-in Module
• Using List(Basic data structure)

1.Using "collections" built-in Module

• Using "collections" built in Module Dequeue Can be implemented

Import required following modules

from collections import deque

Initializing Deque

Syntax:

dq=deque(array)

Example:

dq=deque([1,2,3,4,5])

Avialable Option of Deque

options=dir(dq)

Primary Operation on Deque

1.append
2.appendleft
3.pop
4.popleft

1.append

insert an element at the right end of the Deque

Syntax:

dequeobject.append(element)

Example:

#Import deue module from collections
from collections import deque

#Initilizing deque
dq=deque([1,2,3])

#print the deque
print("Normal Deque")
print(dq)


#Append Element at the right end of the deque
#Append 5
dq.append(5)

#print deque after appending 5 element
print("\nDeque After Append 5 at Right Side")
print(dq)

Output:

Normal Deque
deque([1, 2, 3])

Deque After Append 5 at Right Side
deque([1, 2, 3, 5])

2.appendleft

insert an element at the left end of the Deque.

Syntax:

dequeobject.appendleft(element)

Example:

#Import deue module from collections
from collections import deque

#Initilizing deque
dq=deque([1,2,3])

#print the deque
print("Normal Deque")
print(dq)


#Append Element at left end of the deque
#Append 5
dq.appendleft(5)

#print deque after appending 5 element
print("\nDeque After Append 5 at left Side")
print(dq)

Output:

Normal Deque
deque([1, 2, 3])

Deque After Append 5 at left Side
deque([5, 1, 2, 3])

3.pop

Delete Element from the right end of the deque.

Syntax:

dequeobject.pop()

Example:

#Import deue module from collections
from collections import deque

#Initilizing deque
dq=deque([1,2,3])

#print the deque
print("Normal Deque")
print(dq)


#Delete Element from right side
dq.pop()

#print deque after Removing element from right end
print("\nDeque After removing element from right Side")
print(dq)

Output:

Normal Deque
deque([1, 2, 3])

Deque After removing element from right Side
deque([1, 2])

4.popleft

Delete Element from left end of the deque Syntax:

dequeobject.popleft()

Example:

#Import deue module from collections
from collections import deque

#Initilizing deque
dq=deque([1,2,3])

#print the deque
print("Normal Deque")
print(dq)


#Delete Element from left side
dq.popleft()

#print deque after Removing element from left end
print("\nDeque After removing element from left Side")
print(dq)

Output:

Normal Deque
deque([1, 2, 3])

Deque After removing element from left Side
deque([2, 3])