✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-062

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.

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

Initial Deque

[20, 30]

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

NameDescription

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

Get Front

O(1)

Get Rear

O(1)

Search

O(n)

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.

Related Topics

  • Introduction to Stacks

  • Introduction to Queues

  • Circular Queues

  • Doubly Linked Lists

  • Priority Queues

  • Sliding-Window Algorithms

Key Concepts

NameDescription

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

QuestionAnswer

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