Mumbai University > Information Technology > Sem 3 > Data structure and algorithm analysis

Marks: 3M

Year: May 2014

1. A double ended queue can be defined as a homogeneous list in which elements can be added or removed from both the ends i.e. element can be added or removed from both front and rear end.
2. It is also called as deque.
3. There are two variant of double ended queue depending upon the restriction to perform insertion or deletion operations at the two ends which are as follows:

• Input restricted deque: An input restricted deque is a deque, which allows insertion at only 1 end, rear end, but allows deletion at both ends, rear and front end of the lists.
• Output restricted deque: An output-restricted deque is a deque, which allows deletion at only one end, front end, but allows insertion at both ends, rear and front ends, of the lists.

• Various possible operations performed on double ended queue are as follows:

• Add an element at the rear end+

• Add an element at the front end
• Delete an element from the front end
• Delete an element from the rear end