Algorithm Guidecomplexity: O(1) at both ends

Deque

A double-ended queue that allows insertion and removal at both ends. It can mimic both a stack and a queue, making it useful for sliding windows, palindrome checks, and bidirectional search.

01Deque

Explore How It Works

Starting the deque. A double-ended queue you can insert into and remove from at both ends.

append(10) · Add 10 at the rear end.

appendleft(5) · This time add 5 at the front end.

append(20) · Add 20 at the rear end again.

popleft() · Mark the front-end 5 for removal.

The front 5 is removed. 10 · 20 remain.

pop() · This time mark the rear-end 20 for removal.

The rear 20 is removed. Inserting and removing freely at both ends is what defines a deque.

empty

Live Python

1from collections import deque

3dq = deque()

4dq.append(x) # append at rear

5dq.appendleft(x) # add at front

6dq.pop() # remove from rear

7dq.popleft() # remove from front

8dq[0], dq[-1] # peek both ends

1 / 8

02 Understand It Simply

For Everyone

🔑How It Works

Both ends accept insertion and removal, so it can serve as either a stack or a queue.

💡In Plain Words

A blend of queue and stack: you can add and remove at both ends, so it's more flexible.

📍Where It's Used

–Recently-used lists (drop old ones at the front
–add new ones at the back)
–palindrome checks
–sliding windows

03 Python Implementation

A clean, readable reference implementation of the core logic of Deque.

core_implementation.py

from collections import deque

dq = deque()
dq.append(x)        # append at rear
dq.appendleft(x)    # add at front
dq.pop()            # remove from rear
dq.popleft()        # remove from front
dq[0], dq[-1]       # peek both ends

04 Frequently Asked Questions

FAQ

What is Deque?+

A double-ended queue that allows insertion and removal at both ends. It can mimic both a stack and a queue, making it useful for sliding windows, palindrome checks, and bidirectional search.

What is the time complexity of Deque?+

The time complexity of Deque is O(1) at both ends. Follow the step-by-step visualization to see exactly why.

Where is Deque used?+

Recently-used lists (drop old ones at the front, add new ones at the back), palindrome checks, sliding windows.

What's a simple analogy for Deque?+

Both ends accept insertion and removal, so it can serve as either a stack or a queue.

→ Data Structures — see allRelated