Deque (double-ended queue) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Deque (double-ended queue)?

A Deque is a data structure where elements can be added or removed from both the front and the back. It combines features of both stacks and queues.

beginner

Name two main operations you can perform on a Deque.

You can add elements to the front or back (called 'push front' and 'push back') and remove elements from the front or back (called 'pop front' and 'pop back').

beginner

How is a Deque different from a regular queue?

A regular queue only allows adding at the back and removing from the front. A Deque allows adding and removing from both ends.

intermediate

Give a real-life example where a Deque might be useful.

A Deque can be used in a browser's history feature, where you can go back (pop from the back) or forward (pop from the front) through pages.

intermediate

What is the time complexity of adding or removing elements from a Deque?

Adding or removing elements from either end of a Deque usually takes constant time, meaning it is very fast and does not depend on the number of elements.

Which ends of a Deque can you add elements to?

A Only front

B Both front and back

C Only back

D Neither end

A Deque allows adding elements at both the front and the back.

What does 'pop front' mean in a Deque?

A Add an element to the back

B Add an element to the front

C Remove an element from the back

D Remove an element from the front

'Pop front' means removing an element from the front of the Deque.

Which data structure is a Deque most similar to?

A Graph

B Tree

C Stack and Queue combined

D Hash Table

A Deque combines features of both stacks (LIFO) and queues (FIFO).

If you can only add elements at the back and remove from the front, what data structure do you have?

A Queue

B Deque

C Stack

D Array

A queue allows adding at the back and removing from the front only.

What is the typical time complexity for adding or removing elements at either end of a Deque?

A Constant time (O(1))

B Linear time (O(n))

C Logarithmic time (O(log n))

D Quadratic time (O(n²))

Operations at either end of a Deque usually take constant time, meaning they are very fast.

Explain what a Deque is and how it differs from a regular queue.

Think about where you can add or remove elements.

Describe a real-life situation where using a Deque would be helpful.

Consider situations where you might go forward and backward.