Double Ended Queue

Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both ends.

Operations on Double Ended Queue:

• Front: Get the front item from the deque. Accessing the front element has O(1) time complexity.
• Rear: Get the last item from the deque. Accessing the rear element has O(1) time complexity.
• push_front(x): Inserts the element x at beginning of the deque. Time Complexity is O(1).
• push_back(x): Inserts the element x at the back of the deque. Time Complexity is O(1).
• pop_front(): Removes the first element from the deque. Time Complexity is O(1).
• pop_back(): Removes the last element from the deque. Time Complexity is O(1).

Applications of Double Ended Queue:

• Used in Job scheduling algorithms.
• In a web browser’s history, recently visited URLs are added to the front of the deque and the URL at the back of the deque is removed after some specified number of operations of insertions at the front.
• Storing a software application’s list of undo and redo operations.
• In caching systems to cache frequently accessed data. Deques can be used to store cached data and efficiently support operations such as adding or removing data from both ends of the deque.

A Queue is defined as a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order. Queue is a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end.  The element, which is first pushed into the order, the operation is first performed on that.