Deque in Data Structure

A Deque (Double-Ended Queue) is a linear data structure that allows insertion and removal of elements from both the front and the rear ends, unlike a regular queue which only allows insertion at the rear and removal at the front.

Core Operations

• addFront(item) — insert an element at the front.
• addRear(item) — insert an element at the rear.
• removeFront() — remove and return the front element.
• removeRear() — remove and return the rear element.
• isEmpty() / size() — utility operations.

from collections import deque

dq = deque()
dq.append(10)        # addRear
dq.appendleft(5)      # addFront
dq.pop()              # removeRear -> 10
dq.popleft()          # removeFront -> 5

Types of Deques

• Input-restricted deque: insertion allowed only at one end, deletion at both ends.
• Output-restricted deque: deletion allowed only at one end, insertion at both ends.

Complexity

Applications

• Implementing both stacks and queues using a single structure.
• Sliding window problems (e.g., maximum in every window of size k).
• Undo operations that need access from both ends of a history list.