concept · INFO-CS-ADS-062Double-Ended Queues (Deque)
A double-ended queue, commonly called a deque, is a linear data structure that allows insertion and deletion at both the front and rear. It supports more flexible operations than a standard FIFO queue.
Explanation
Overview
A deque is an abstract data type in which elements can be added to or removed from either end. Its name comes from double-ended queue.
Purpose
Deques are useful when an application needs flexible processing from both ends of a collection, such as maintaining sliding windows, implementing stacks and queues, or managing task sequences.
Key concepts
name: Core idea; description: The central focus of double-ended queues (deque) is the capability described here: A double-ended queue, commonly called a deque, is a linear data structure that allows insertion and deletion at both the front and rear. It supports more flexible operations than a standard FIFO queue.; name: Problem context; description: Double-Ended Queues (Deque) is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using double-ended queues (deque), check its assumptions, input requirements, expected output, and resource constraints.
Time complexity
insertFront: O(1) in a suitable circular-array or doubly linked-list implementation; insertRear: O(1) in a suitable implementation; deleteFront: O(1) in a suitable implementation; deleteRear: O(1) in a suitable implementation; getFront: O(1); getRear: O(1)
Space complexity
O(n) for n elements. Actual storage depends on the chosen implementation and its capacity or reference overhead.
Example
initialDeque: [20, 30]; operations: INSERT_FRONT(10); INSERT_REAR(40); results: [10, 20, 30]; [10, 20, 30, 40]
Advantages
Supports operations at both ends.; Can function as both a stack and a queue.; Useful for algorithms that maintain a moving range of elements.; Circular-array and doubly linked-list implementations can provide constant-time end operations.
Example or application
Operations
INSERT_FRONT(10)
INSERT_REAR(40)
DELETE_FRONT()
DELETE_REAR()
Results
[10, 20, 30]
[10, 20, 30, 40]
Removes 10; remaining deque is [20, 30, 40]
Removes 40; remaining deque is [20, 30]
Definition
A deque is an abstract data type in which elements can be added to or removed from either end. Its name comes from double-ended queue.
Purpose
Deques are useful when an application needs flexible processing from both ends of a collection, such as maintaining sliding windows, implementing stacks and queues, or managing task sequences.
Core Principle
Unlike a standard queue, which inserts at the rear and removes from the front, a deque supports insertion and deletion at both ends.
Main Operations
InsertFront: Adds an element at the front.
InsertRear: Adds an element at the rear.
DeleteFront: Removes an element from the front.
DeleteRear: Removes an element from the rear.
GetFront: Returns the front element without removing it.
GetRear: Returns the rear element without removing it.
IsEmpty: Checks whether the deque contains no elements.
IsFull: Checks whether a fixed-capacity deque has reached its capacity.
Major Types
| Name | Description |
|---|
Input-Restricted Deque | Insertion is permitted at only one end, while deletion is permitted at both ends. |
Output-Restricted Deque | Deletion is permitted at only one end, while insertion is permitted at both ends. |
Implementation Methods
Circular array: Uses front and rear indices with wraparound to support operations at both ends.
Doubly linked list: Uses previous and next references so that both ends can be modified efficiently.
Dynamic array: Can support deque operations, although insertion or deletion at the front may require shifting elements unless the implementation uses circular storage.
Array Implementation
A circular array deque adjusts front and rear positions using modular arithmetic. It can insert or remove elements at either end without shifting the entire collection.
Linked List Implementation
A doubly linked list with head and tail references supports insertion and deletion at both ends by updating a small number of node references.
Advantages
Supports operations at both ends.
Can function as both a stack and a queue.
Useful for algorithms that maintain a moving range of elements.
Circular-array and doubly linked-list implementations can provide constant-time end operations.
Limitations
More operations must be implemented and maintained than in a simple queue.
Circular array implementations require careful index management.
Linked-list implementations use additional memory for references.
Not designed for efficient arbitrary indexed access.
Time Complexity
Insert Front
O(1) in a suitable circular-array or doubly linked-list implementation
Insert Rear
O(1) in a suitable implementation
Delete Front
O(1) in a suitable implementation
Delete Rear
O(1) in a suitable implementation
Space Complexity
O(n) for n elements. Actual storage depends on the chosen implementation and its capacity or reference overhead.
Common Applications
Sliding-window algorithms
Palindrome checking
Task scheduling
Undo and redo systems
Implementing stacks and queues
Maintaining recently used elements
Work-stealing schedulers
Implementation Considerations
Handle insertion and deletion on an empty deque.
Handle removal of the only element.
Maintain front and rear consistently.
Use wraparound correctly in circular-array implementations.
Update both previous and next references in doubly linked implementations.
Check capacity before insertion in fixed-size implementations.
Learning Objectives
Define a deque.
Identify the four main end operations.
Distinguish input-restricted and output-restricted deques.
Compare array and linked-list implementations.
Recognize practical applications of double-ended queues.
Key Takeaways
A deque supports insertion and deletion at both ends.
It can implement stack-like and queue-like behavior.
Circular arrays and doubly linked lists are common implementations.
End operations can take O(1) time in suitable implementations.
A deque does not automatically provide efficient arbitrary indexed access.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of double-ended queues (deque) is the capability described here: A double-ended queue, commonly called a deque, is a linear data structure that allows insertion and deletion at both the front and rear. It supports more flexible operations than a standard FIFO queue. |
Problem context | Double-Ended Queues (Deque) is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using double-ended queues (deque), check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of double-ended queues (deque)? | A double-ended queue, commonly called a deque, is a linear data structure that allows insertion and deletion at both the front and rear. It supports more flexible operations than a standard FIFO queue. |
What should be checked before applying double-ended queues (deque)? | For double-ended queues (deque), verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of double-ended queues (deque) be validated? | Trace a representative double-ended queues (deque) case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures