Deque (Double-ended Queue) Data Structure

How Deque Works

A deque (double-ended queue) is a linear data structure that allows insertion and deletion at both ends. It combines the features of both stack and queue.

Key operations:

• Add Front: Adds an element to the front of the deque
• Add Rear: Adds an element to the rear of the deque
• Remove Front: Removes and returns the element from the front of the deque
• Remove Rear: Removes and returns the element from the rear of the deque
• Peek Front: Returns the front element without removing it
• Peek Rear: Returns the rear element without removing it

Time complexities:

• All operations: O(1)

Deques are used in scenarios where elements need to be added or removed from either end efficiently, such as in certain types of scheduling algorithms, palindrome checkers, and implementing other data structures like queues and stacks.

class Deque:
    items

    function addFront(element):
        items.prepend(element)
        visualize()

    function addRear(element):
        items.append(element)
        visualize()

    function removeFront():
        if isEmpty():
            return null
        element = items.removeFirst()
        visualize()
        return element

    function removeRear():
        if isEmpty():
            return null
        element = items.removeLast()
        visualize()
        return element

    function isEmpty():
        return items.length == 0