Skip to content
Welcome to contribute to Chinese-to-English translation! For more details, please refer to CONTRIBUTING.md.

# 5.3 Deque

In a queue, we can only remove elements from the front or add elements at the rear. As shown in Figure 5-7, a double-ended queue (deque) provides greater flexibility, allowing elements to be added or removed at both the front and the rear.

Figure 5-7 Operations of deque

## 5.3.1 Common Deque Operations

The common operations on a deque are shown in Table 5-3. The specific method names depend on the programming language used.

Table 5-3 Efficiency of Deque Operations

Method | Description | Time Complexity
--- | --- | ---
`push_first()` | Add element to front | \(O(1)\)
`push_last()` | Add element to rear | \(O(1)\)
`pop_first()` | Remove front element | \(O(1)\)
`pop_last()` | Remove rear element | \(O(1)\)
`peek_first()` | Access front element | \(O(1)\)
`peek_last()` | Access rear element | \(O(1)\)

Similarly, we can directly use the deque classes provided by the programming language:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
deque.py

    from collections import deque

    # Initialize deque
    deq: deque[int] = deque()

    # Enqueue elements
    deq.append(2)      # Add to rear
    deq.append(5)
    deq.append(4)
    deq.appendleft(3)  # Add to front
    deq.appendleft(1)

    # Access elements
    front: int = deq[0]  # Front element
    rear: int = deq[-1]  # Rear element

    # Dequeue elements
    pop_front: int = deq.popleft()  # Front element dequeue
    pop_rear: int = deq.pop()       # Rear element dequeue

    # Get deque length
    size: int = len(deq)

    # Check if deque is empty
    is_empty: bool = len(deq) == 0

deque.cpp

    /* Initialize deque */
    deque<int> deque;

    /* Enqueue elements */
    deque.push_back(2);   // Add to rear
    deque.push_back(5);
    deque.push_back(4);
    deque.push_front(3);  // Add to front
    deque.push_front(1);

    /* Access elements */
    int front = deque.front(); // Front element
    int back = deque.back();   // Rear element

    /* Dequeue elements */
    deque.pop_front();  // Front element dequeue
    deque.pop_back();   // Rear element dequeue

    /* Get deque length */
    int size = deque.size();

    /* Check if deque is empty */
    bool empty = deque.empty();

deque.java

    /* Initialize deque */
    Deque<Integer> deque = new LinkedList<>();

    /* Enqueue elements */
    deque.offerLast(2);   // Add to rear
    deque.offerLast(5);
    deque.offerLast(4);
    deque.offerFirst(3);  // Add to front
    deque.offerFirst(1);

    /* Access elements */
    int peekFirst = deque.peekFirst();  // Front element
    int peekLast = deque.peekLast();    // Rear element

    /* Dequeue elements */
    int popFirst = deque.pollFirst();  // Front element dequeue
    int popLast = deque.pollLast();    // Rear element dequeue

    /* Get deque length */
    int size = deque.size();

    /* Check if deque is empty */
    boolean isEmpty = deque.isEmpty();

deque.cs

    /* Initialize deque */
    // In C#, use LinkedList as a deque
    LinkedList<int> deque = new();

    /* Enqueue elements */
    deque.AddLast(2);   // Add to rear
    deque.AddLast(5);
    deque.AddLast(4);
    deque.AddFirst(3);  // Add to front
    deque.AddFirst(1);

    /* Access elements */
    int peekFirst = deque.First.Value;  // Front element
    int peekLast = deque.Last.Value;    // Rear element

    /* Dequeue elements */
    deque.RemoveFirst();  // Front element dequeue
    deque.RemoveLast();   // Rear element dequeue

    /* Get deque length */
    int size = deque.Count;

    /* Check if deque is empty */
    bool isEmpty = deque.Count == 0;

deque_test.go

    /* Initialize deque */
    // In Go, use list as a deque
    deque := list.New()

    /* Enqueue elements */
    deque.PushBack(2)      // Add to rear
    deque.PushBack(5)
    deque.PushBack(4)
    deque.PushFront(3)     // Add to front
    deque.PushFront(1)

    /* Access elements */
    front := deque.Front() // Front element
    rear := deque.Back()   // Rear element

    /* Dequeue elements */
    deque.Remove(front)    // Front element dequeue
    deque.Remove(rear)     // Rear element dequeue

    /* Get deque length */
    size := deque.Len()

    /* Check if deque is empty */
    isEmpty := deque.Len() == 0

deque.swift

    /* Initialize deque */
    // Swift does not have a built-in deque class, can use Array as a deque
    var deque: [Int] = []

    /* Enqueue elements */
    deque.append(2) // Add to rear
    deque.append(5)
    deque.append(4)
    deque.insert(3, at: 0) // Add to front
    deque.insert(1, at: 0)

    /* Access elements */
    let peekFirst = deque.first! // Front element
    let peekLast = deque.last! // Rear element

    /* Dequeue elements */
    // When using Array simulation, popFirst has O(n) complexity
    let popFirst = deque.removeFirst() // Front element dequeue
    let popLast = deque.removeLast() // Rear element dequeue

    /* Get deque length */
    let size = deque.count

    /* Check if deque is empty */
    let isEmpty = deque.isEmpty

deque.js

    /* Initialize deque */
    // JavaScript does not have a built-in deque, can only use Array as a deque
    const deque = [];

    /* Enqueue elements */
    deque.push(2);
    deque.push(5);
    deque.push(4);
    // Please note that since it's an array, unshift() has O(n) time complexity
    deque.unshift(3);
    deque.unshift(1);

    /* Access elements */
    const peekFirst = deque[0];
    const peekLast = deque[deque.length - 1];

    /* Dequeue elements */
    // Please note that since it's an array, shift() has O(n) time complexity
    const popFront = deque.shift();
    const popBack = deque.pop();

    /* Get deque length */
    const size = deque.length;

    /* Check if deque is empty */
    const isEmpty = size === 0;

deque.ts

    /* Initialize deque */
    // TypeScript does not have a built-in deque, can only use Array as a deque
    const deque: number[] = [];

    /* Enqueue elements */
    deque.push(2);
    deque.push(5);
    deque.push(4);
    // Please note that since it's an array, unshift() has O(n) time complexity
    deque.unshift(3);
    deque.unshift(1);

    /* Access elements */
    const peekFirst: number = deque[0];
    const peekLast: number = deque[deque.length - 1];

    /* Dequeue elements */
    // Please note that since it's an array, shift() has O(n) time complexity
    const popFront: number = deque.shift() as number;
    const popBack: number = deque.pop() as number;

    /* Get deque length */
    const size: number = deque.length;

    /* Check if deque is empty */
    const isEmpty: boolean = size === 0;

deque.dart

    /* Initialize deque */
    // In Dart, Queue is defined as a deque
    Queue<int> deque = Queue<int>();

    /* Enqueue elements */
    deque.addLast(2);  // Add to rear
    deque.addLast(5);
    deque.addLast(4);
    deque.addFirst(3); // Add to front
    deque.addFirst(1);

    /* Access elements */
    int peekFirst = deque.first; // Front element
    int peekLast = deque.last;   // Rear element

    /* Dequeue elements */
    int popFirst = deque.removeFirst(); // Front element dequeue
    int popLast = deque.removeLast();   // Rear element dequeue

    /* Get deque length */
    int size = deque.length;

    /* Check if deque is empty */
    bool isEmpty = deque.isEmpty;

deque.rs

    /* Initialize deque */
    let mut deque: VecDeque<u32> = VecDeque::new();

    /* Enqueue elements */
    deque.push_back(2);  // Add to rear
    deque.push_back(5);
    deque.push_back(4);
    deque.push_front(3); // Add to front
    deque.push_front(1);

    /* Access elements */
    if let Some(front) = deque.front() { // Front element
    }
    if let Some(rear) = deque.back() {   // Rear element
    }

    /* Dequeue elements */
    if let Some(pop_front) = deque.pop_front() { // Front element dequeue
    }
    if let Some(pop_rear) = deque.pop_back() {   // Rear element dequeue
    }

    /* Get deque length */
    let size = deque.len();

    /* Check if deque is empty */
    let is_empty = deque.is_empty();

deque.c

    // C does not provide a built-in deque

deque.kt

    /* Initialize deque */
    val deque = LinkedList<Int>()

    /* Enqueue elements */
    deque.offerLast(2)  // Add to rear
    deque.offerLast(5)
    deque.offerLast(4)
    deque.offerFirst(3) // Add to front
    deque.offerFirst(1)

    /* Access elements */
    val peekFirst = deque.peekFirst() // Front element
    val peekLast = deque.peekLast()   // Rear element

    /* Dequeue elements */
    val popFirst = deque.pollFirst() // Front element dequeue
    val popLast = deque.pollLast()   // Rear element dequeue

    /* Get deque length */
    val size = deque.size

    /* Check if deque is empty */
    val isEmpty = deque.isEmpty()

deque.rb

    # Initialize deque
    # Ruby does not have a built-in deque, can only use Array as a deque
    deque = []

    # Enqueue elements
    deque << 2
    deque << 5
    deque << 4
    # Please note that since it's an array, Array#unshift has O(n) time complexity
    deque.unshift(3)
    deque.unshift(1)

    # Access elements
    peek_first = deque.first
    peek_last = deque.last

    # Dequeue elements
    # Please note that since it's an array, Array#shift has O(n) time complexity
    pop_front = deque.shift
    pop_back = deque.pop

    # Get deque length
    size = deque.length

    # Check if deque is empty
    is_empty = size.zero?

Code Visualization

Full Screen >

## 5.3.2 Deque Implementation *

The implementation of a deque is similar to that of a queue. You can choose either a linked list or an array as the underlying data structure.

### 1. Doubly Linked List Implementation

Reviewing the previous section, we used a regular singly linked list to implement a queue because it conveniently allows deleting the head node (corresponding to dequeue) and adding new nodes after the tail node (corresponding to enqueue).

For a deque, both the front and rear can perform enqueue and dequeue operations. In other words, a deque needs to implement operations in the opposite direction as well. For this reason, we use a "doubly linked list" as the underlying data structure for the deque.

As shown in Figure 5-8, we treat the head and tail nodes of the doubly linked list as the front and rear of the deque, implementing functionality to add and remove nodes at both ends.

<1><2><3><4><5>

Figure 5-8 Enqueue and dequeue operations in linked list implementation of deque

The implementation code is shown below:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
linkedlist_deque.py

    class ListNode:
        """Doubly linked list node"""

        def __init__(self, val: int):
            """Constructor"""
            self.val: int = val
            self.next: ListNode | None = None  # Successor node reference
            self.prev: ListNode | None = None  # Predecessor node reference

    class LinkedListDeque:
        """Double-ended queue based on doubly linked list implementation"""

        def __init__(self):
            """Constructor"""
            self._front: ListNode | None = None  # Head node front
            self._rear: ListNode | None = None  # Tail node rear
            self._size: int = 0  # Length of the double-ended queue

        def size(self) -> int:
            """Get the length of the double-ended queue"""
            return self._size

        def is_empty(self) -> bool:
            """Check if the double-ended queue is empty"""
            return self._size == 0

        def push(self, num: int, is_front: bool):
            """Enqueue operation"""
            node = ListNode(num)
            # If the linked list is empty, make both front and rear point to node
            if self.is_empty():
                self._front = self._rear = node
            # Front of the queue enqueue operation
            elif is_front:
                # Add node to the head of the linked list
                self._front.prev = node
                node.next = self._front
                self._front = node  # Update head node
            # Rear of the queue enqueue operation
            else:
                # Add node to the tail of the linked list
                self._rear.next = node
                node.prev = self._rear
                self._rear = node  # Update tail node
            self._size += 1  # Update queue length

        def push_first(self, num: int):
            """Front of the queue enqueue"""
            self.push(num, True)

        def push_last(self, num: int):
            """Rear of the queue enqueue"""
            self.push(num, False)

        def pop(self, is_front: bool) -> int:
            """Dequeue operation"""
            if self.is_empty():
                raise IndexError("Double-ended queue is empty")
            # Front of the queue dequeue operation
            if is_front:
                val: int = self._front.val  # Temporarily store head node value
                # Delete head node
                fnext: ListNode | None = self._front.next
                if fnext is not None:
                    fnext.prev = None
                    self._front.next = None
                self._front = fnext  # Update head node
            # Rear of the queue dequeue operation
            else:
                val: int = self._rear.val  # Temporarily store tail node value
                # Delete tail node
                rprev: ListNode | None = self._rear.prev
                if rprev is not None:
                    rprev.next = None
                    self._rear.prev = None
                self._rear = rprev  # Update tail node
            self._size -= 1  # Update queue length
            return val

        def pop_first(self) -> int:
            """Front of the queue dequeue"""
            return self.pop(True)

        def pop_last(self) -> int:
            """Rear of the queue dequeue"""
            return self.pop(False)

        def peek_first(self) -> int:
            """Access front of the queue element"""
            if self.is_empty():
                raise IndexError("Double-ended queue is empty")
            return self._front.val

        def peek_last(self) -> int:
            """Access rear of the queue element"""
            if self.is_empty():
                raise IndexError("Double-ended queue is empty")
            return self._rear.val

        def to_array(self) -> list[int]:
            """Return array for printing"""
            node = self._front
            res = [0] * self.size()
            for i in range(self.size()):
                res[i] = node.val
                node = node.next
            return res

linkedlist_deque.cpp

    /* Doubly linked list node */
    struct DoublyListNode {
        int val;              // Node value
        DoublyListNode *next; // Successor node pointer
        DoublyListNode *prev; // Predecessor node pointer
        DoublyListNode(int val) : val(val), prev(nullptr), next(nullptr) {
        }
    };

    /* Double-ended queue based on doubly linked list implementation */
    class LinkedListDeque {
      private:
        DoublyListNode *front, *rear; // Head node front, tail node rear
        int queSize = 0;              // Length of the double-ended queue

      public:
        /* Constructor */
        LinkedListDeque() : front(nullptr), rear(nullptr) {
        }

        /* Destructor */
        ~LinkedListDeque() {
            // Traverse linked list to delete nodes and free memory
            DoublyListNode *pre, *cur = front;
            while (cur != nullptr) {
                pre = cur;
                cur = cur->next;
                delete pre;
            }
        }

        /* Get the length of the double-ended queue */
        int size() {
            return queSize;
        }

        /* Check if the double-ended queue is empty */
        bool isEmpty() {
            return size() == 0;
        }

        /* Enqueue operation */
        void push(int num, bool isFront) {
            DoublyListNode *node = new DoublyListNode(num);
            // If the linked list is empty, make both front and rear point to node
            if (isEmpty())
                front = rear = node;
            // Front of the queue enqueue operation
            else if (isFront) {
                // Add node to the head of the linked list
                front->prev = node;
                node->next = front;
                front = node; // Update head node
            // Rear of the queue enqueue operation
            } else {
                // Add node to the tail of the linked list
                rear->next = node;
                node->prev = rear;
                rear = node; // Update tail node
            }
            queSize++; // Update queue length
        }

        /* Front of the queue enqueue */
        void pushFirst(int num) {
            push(num, true);
        }

        /* Rear of the queue enqueue */
        void pushLast(int num) {
            push(num, false);
        }

        /* Dequeue operation */
        int pop(bool isFront) {
            if (isEmpty())
                throw out_of_range("Queue is empty");
            int val;
            // Temporarily store head node value
            if (isFront) {
                val = front->val; // Delete head node
                // Delete head node
                DoublyListNode *fNext = front->next;
                if (fNext != nullptr) {
                    fNext->prev = nullptr;
                    front->next = nullptr;
                }
                delete front;
                front = fNext; // Update head node
            // Temporarily store tail node value
            } else {
                val = rear->val; // Delete tail node
                // Update tail node
                DoublyListNode *rPrev = rear->prev;
                if (rPrev != nullptr) {
                    rPrev->next = nullptr;
                    rear->prev = nullptr;
                }
                delete rear;
                rear = rPrev; // Update tail node
            }
            queSize--; // Update queue length
            return val;
        }

        /* Rear of the queue dequeue */
        int popFirst() {
            return pop(true);
        }

        /* Access rear of the queue element */
        int popLast() {
            return pop(false);
        }

        /* Return list for printing */
        int peekFirst() {
            if (isEmpty())
                throw out_of_range("Deque is empty");
            return front->val;
        }

        /* Driver Code */
        int peekLast() {
            if (isEmpty())
                throw out_of_range("Deque is empty");
            return rear->val;
        }

        /* Return array for printing */
        vector<int> toVector() {
            DoublyListNode *node = front;
            vector<int> res(size());
            for (int i = 0; i < res.size(); i++) {
                res[i] = node->val;
                node = node->next;
            }
            return res;
        }
    };

linkedlist_deque.java

    /* Doubly linked list node */
    class ListNode {
        int val; // Node value
        ListNode next; // Successor node reference
        ListNode prev; // Predecessor node reference

        ListNode(int val) {
            this.val = val;
            prev = next = null;
        }
    }

    /* Double-ended queue based on doubly linked list implementation */
    class LinkedListDeque {
        private ListNode front, rear; // Head node front, tail node rear
        private int queSize = 0; // Length of the double-ended queue

        public LinkedListDeque() {
            front = rear = null;
        }

        /* Get the length of the double-ended queue */
        public int size() {
            return queSize;
        }

        /* Check if the double-ended queue is empty */
        public boolean isEmpty() {
            return size() == 0;
        }

        /* Enqueue operation */
        private void push(int num, boolean isFront) {
            ListNode node = new ListNode(num);
            // If the linked list is empty, make both front and rear point to node
            if (isEmpty())
                front = rear = node;
            // Front of the queue enqueue operation
            else if (isFront) {
                // Add node to the head of the linked list
                front.prev = node;
                node.next = front;
                front = node; // Update head node
            // Rear of the queue enqueue operation
            } else {
                // Add node to the tail of the linked list
                rear.next = node;
                node.prev = rear;
                rear = node; // Update tail node
            }
            queSize++; // Update queue length
        }

        /* Front of the queue enqueue */
        public void pushFirst(int num) {
            push(num, true);
        }

        /* Rear of the queue enqueue */
        public void pushLast(int num) {
            push(num, false);
        }

        /* Dequeue operation */
        private int pop(boolean isFront) {
            if (isEmpty())
                throw new IndexOutOfBoundsException();
            int val;
            // Temporarily store head node value
            if (isFront) {
                val = front.val; // Delete head node
                // Delete head node
                ListNode fNext = front.next;
                if (fNext != null) {
                    fNext.prev = null;
                    front.next = null;
                }
                front = fNext; // Update head node
            // Temporarily store tail node value
            } else {
                val = rear.val; // Delete tail node
                // Update tail node
                ListNode rPrev = rear.prev;
                if (rPrev != null) {
                    rPrev.next = null;
                    rear.prev = null;
                }
                rear = rPrev; // Update tail node
            }
            queSize--; // Update queue length
            return val;
        }

        /* Rear of the queue dequeue */
        public int popFirst() {
            return pop(true);
        }

        /* Access rear of the queue element */
        public int popLast() {
            return pop(false);
        }

        /* Return list for printing */
        public int peekFirst() {
            if (isEmpty())
                throw new IndexOutOfBoundsException();
            return front.val;
        }

        /* Driver Code */
        public int peekLast() {
            if (isEmpty())
                throw new IndexOutOfBoundsException();
            return rear.val;
        }

        /* Return array for printing */
        public int[] toArray() {
            ListNode node = front;
            int[] res = new int[size()];
            for (int i = 0; i < res.length; i++) {
                res[i] = node.val;
                node = node.next;
            }
            return res;
        }
    }

linkedlist_deque.cs

    /* Doubly linked list node */
    class ListNode(int val) {
        public int val = val;       // Node value
        public ListNode? next = null; // Successor node reference
        public ListNode? prev = null; // Predecessor node reference
    }

    /* Double-ended queue based on doubly linked list implementation */
    class LinkedListDeque {
        ListNode? front, rear; // Head node front, tail node rear
        int queSize = 0;      // Length of the double-ended queue

        public LinkedListDeque() {
            front = null;
            rear = null;
        }

        /* Get the length of the double-ended queue */
        public int Size() {
            return queSize;
        }

        /* Check if the double-ended queue is empty */
        public bool IsEmpty() {
            return Size() == 0;
        }

        /* Enqueue operation */
        void Push(int num, bool isFront) {
            ListNode node = new(num);
            // If the linked list is empty, make both front and rear point to node
            if (IsEmpty()) {
                front = node;
                rear = node;
            }
            // Front of the queue enqueue operation
            else if (isFront) {
                // Add node to the head of the linked list
                front!.prev = node;
                node.next = front;
                front = node; // Update head node
            }
            // Rear of the queue enqueue operation
            else {
                // Add node to the tail of the linked list
                rear!.next = node;
                node.prev = rear;
                rear = node;  // Update tail node
            }

            queSize++; // Update queue length
        }

        /* Front of the queue enqueue */
        public void PushFirst(int num) {
            Push(num, true);
        }

        /* Rear of the queue enqueue */
        public void PushLast(int num) {
            Push(num, false);
        }

        /* Dequeue operation */
        int? Pop(bool isFront) {
            if (IsEmpty())
                throw new Exception();
            int? val;
            // Temporarily store head node value
            if (isFront) {
                val = front?.val; // Delete head node
                // Delete head node
                ListNode? fNext = front?.next;
                if (fNext != null) {
                    fNext.prev = null;
                    front!.next = null;
                }
                front = fNext;   // Update head node
            }
            // Temporarily store tail node value
            else {
                val = rear?.val;  // Delete tail node
                // Update tail node
                ListNode? rPrev = rear?.prev;
                if (rPrev != null) {
                    rPrev.next = null;
                    rear!.prev = null;
                }
                rear = rPrev;    // Update tail node
            }

            queSize--; // Update queue length
            return val;
        }

        /* Rear of the queue dequeue */
        public int? PopFirst() {
            return Pop(true);
        }

        /* Access rear of the queue element */
        public int? PopLast() {
            return Pop(false);
        }

        /* Return list for printing */
        public int? PeekFirst() {
            if (IsEmpty())
                throw new Exception();
            return front?.val;
        }

        /* Driver Code */
        public int? PeekLast() {
            if (IsEmpty())
                throw new Exception();
            return rear?.val;
        }

        /* Return array for printing */
        public int?[] ToArray() {
            ListNode? node = front;
            int?[] res = new int?[Size()];
            for (int i = 0; i < res.Length; i++) {
                res[i] = node?.val;
                node = node?.next;
            }

            return res;
        }
    }

linkedlist_deque.go

    /* Double-ended queue based on doubly linked list implementation */
    type linkedListDeque struct {
        // Use built-in package list
        data *list.List
    }

    /* Initialize deque */
    func newLinkedListDeque() *linkedListDeque {
        return &linkedListDeque{
            data: list.New(),
        }
    }

    /* Front element enqueue */
    func (s *linkedListDeque) pushFirst(value any) {
        s.data.PushFront(value)
    }

    /* Rear element enqueue */
    func (s *linkedListDeque) pushLast(value any) {
        s.data.PushBack(value)
    }

    /* Check if the double-ended queue is empty */
    func (s *linkedListDeque) popFirst() any {
        if s.isEmpty() {
            return nil
        }
        e := s.data.Front()
        s.data.Remove(e)
        return e.Value
    }

    /* Rear element dequeue */
    func (s *linkedListDeque) popLast() any {
        if s.isEmpty() {
            return nil
        }
        e := s.data.Back()
        s.data.Remove(e)
        return e.Value
    }

    /* Return list for printing */
    func (s *linkedListDeque) peekFirst() any {
        if s.isEmpty() {
            return nil
        }
        e := s.data.Front()
        return e.Value
    }

    /* Driver Code */
    func (s *linkedListDeque) peekLast() any {
        if s.isEmpty() {
            return nil
        }
        e := s.data.Back()
        return e.Value
    }

    /* Get the length of the queue */
    func (s *linkedListDeque) size() int {
        return s.data.Len()
    }

    /* Check if the queue is empty */
    func (s *linkedListDeque) isEmpty() bool {
        return s.data.Len() == 0
    }

    /* Get List for printing */
    func (s *linkedListDeque) toList() *list.List {
        return s.data
    }

linkedlist_deque.swift

    /* Doubly linked list node */
    class ListNode {
        var val: Int // Node value
        var next: ListNode? // Successor node reference
        weak var prev: ListNode? // Predecessor node reference

        init(val: Int) {
            self.val = val
        }
    }

    /* Double-ended queue based on doubly linked list implementation */
    class LinkedListDeque {
        private var front: ListNode? // Head node front
        private var rear: ListNode? // Tail node rear
        private var _size: Int // Length of the double-ended queue

        init() {
            _size = 0
        }

        /* Get the length of the double-ended queue */
        func size() -> Int {
            _size
        }

        /* Check if the double-ended queue is empty */
        func isEmpty() -> Bool {
            size() == 0
        }

        /* Enqueue operation */
        private func push(num: Int, isFront: Bool) {
            let node = ListNode(val: num)
            // If the linked list is empty, make both front and rear point to node
            if isEmpty() {
                front = node
                rear = node
            }
            // Front of the queue enqueue operation
            else if isFront {
                // Add node to the head of the linked list
                front?.prev = node
                node.next = front
                front = node // Update head node
            }
            // Rear of the queue enqueue operation
            else {
                // Add node to the tail of the linked list
                rear?.next = node
                node.prev = rear
                rear = node // Update tail node
            }
            _size += 1 // Update queue length
        }

        /* Front of the queue enqueue */
        func pushFirst(num: Int) {
            push(num: num, isFront: true)
        }

        /* Rear of the queue enqueue */
        func pushLast(num: Int) {
            push(num: num, isFront: false)
        }

        /* Dequeue operation */
        private func pop(isFront: Bool) -> Int {
            if isEmpty() {
                fatalError("Deque is empty")
            }
            let val: Int
            // Temporarily store head node value
            if isFront {
                val = front!.val // Delete head node
                // Delete head node
                let fNext = front?.next
                if fNext != nil {
                    fNext?.prev = nil
                    front?.next = nil
                }
                front = fNext // Update head node
            }
            // Temporarily store tail node value
            else {
                val = rear!.val // Delete tail node
                // Update tail node
                let rPrev = rear?.prev
                if rPrev != nil {
                    rPrev?.next = nil
                    rear?.prev = nil
                }
                rear = rPrev // Update tail node
            }
            _size -= 1 // Update queue length
            return val
        }

        /* Rear of the queue dequeue */
        func popFirst() -> Int {
            pop(isFront: true)
        }

        /* Access rear of the queue element */
        func popLast() -> Int {
            pop(isFront: false)
        }

        /* Return list for printing */
        func peekFirst() -> Int {
            if isEmpty() {
                fatalError("Deque is empty")
            }
            return front!.val
        }

        /* Driver Code */
        func peekLast() -> Int {
            if isEmpty() {
                fatalError("Deque is empty")
            }
            return rear!.val
        }

        /* Return array for printing */
        func toArray() -> [Int] {
            var node = front
            var res = Array(repeating: 0, count: size())
            for i in res.indices {
                res[i] = node!.val
                node = node?.next
            }
            return res
        }
    }

linkedlist_deque.js

    /* Doubly linked list node */
    class ListNode {
        prev; // Predecessor node reference (pointer)
        next; // Successor node reference (pointer)
        val; // Node value

        constructor(val) {
            this.val = val;
            this.next = null;
            this.prev = null;
        }
    }

    /* Double-ended queue based on doubly linked list implementation */
    class LinkedListDeque {
        #front; // Head node front
        #rear; // Tail node rear
        #queSize; // Length of the double-ended queue

        constructor() {
            this.#front = null;
            this.#rear = null;
            this.#queSize = 0;
        }

        /* Rear of the queue enqueue operation */
        pushLast(val) {
            const node = new ListNode(val);
            // If the linked list is empty, make both front and rear point to node
            if (this.#queSize === 0) {
                this.#front = node;
                this.#rear = node;
            } else {
                // Add node to the tail of the linked list
                this.#rear.next = node;
                node.prev = this.#rear;
                this.#rear = node; // Update tail node
            }
            this.#queSize++;
        }

        /* Front of the queue enqueue operation */
        pushFirst(val) {
            const node = new ListNode(val);
            // If the linked list is empty, make both front and rear point to node
            if (this.#queSize === 0) {
                this.#front = node;
                this.#rear = node;
            } else {
                // Add node to the head of the linked list
                this.#front.prev = node;
                node.next = this.#front;
                this.#front = node; // Update head node
            }
            this.#queSize++;
        }

        /* Temporarily store tail node value */
        popLast() {
            if (this.#queSize === 0) {
                return null;
            }
            const value = this.#rear.val; // Store tail node value
            // Update tail node
            let temp = this.#rear.prev;
            if (temp !== null) {
                temp.next = null;
                this.#rear.prev = null;
            }
            this.#rear = temp; // Update tail node
            this.#queSize--;
            return value;
        }

        /* Temporarily store head node value */
        popFirst() {
            if (this.#queSize === 0) {
                return null;
            }
            const value = this.#front.val; // Store tail node value
            // Delete head node
            let temp = this.#front.next;
            if (temp !== null) {
                temp.prev = null;
                this.#front.next = null;
            }
            this.#front = temp; // Update head node
            this.#queSize--;
            return value;
        }

        /* Driver Code */
        peekLast() {
            return this.#queSize === 0 ? null : this.#rear.val;
        }

        /* Return list for printing */
        peekFirst() {
            return this.#queSize === 0 ? null : this.#front.val;
        }

        /* Get the length of the double-ended queue */
        size() {
            return this.#queSize;
        }

        /* Check if the double-ended queue is empty */
        isEmpty() {
            return this.#queSize === 0;
        }

        /* Print deque */
        print() {
            const arr = [];
            let temp = this.#front;
            while (temp !== null) {
                arr.push(temp.val);
                temp = temp.next;
            }
            console.log('[' + arr.join(', ') + ']');
        }
    }

linkedlist_deque.ts

    /* Doubly linked list node */
    class ListNode {
        prev: ListNode; // Predecessor node reference (pointer)
        next: ListNode; // Successor node reference (pointer)
        val: number; // Node value

        constructor(val: number) {
            this.val = val;
            this.next = null;
            this.prev = null;
        }
    }

    /* Double-ended queue based on doubly linked list implementation */
    class LinkedListDeque {
        private front: ListNode; // Head node front
        private rear: ListNode; // Tail node rear
        private queSize: number; // Length of the double-ended queue

        constructor() {
            this.front = null;
            this.rear = null;
            this.queSize = 0;
        }

        /* Rear of the queue enqueue operation */
        pushLast(val: number): void {
            const node: ListNode = new ListNode(val);
            // If the linked list is empty, make both front and rear point to node
            if (this.queSize === 0) {
                this.front = node;
                this.rear = node;
            } else {
                // Add node to the tail of the linked list
                this.rear.next = node;
                node.prev = this.rear;
                this.rear = node; // Update tail node
            }
            this.queSize++;
        }

        /* Front of the queue enqueue operation */
        pushFirst(val: number): void {
            const node: ListNode = new ListNode(val);
            // If the linked list is empty, make both front and rear point to node
            if (this.queSize === 0) {
                this.front = node;
                this.rear = node;
            } else {
                // Add node to the head of the linked list
                this.front.prev = node;
                node.next = this.front;
                this.front = node; // Update head node
            }
            this.queSize++;
        }

        /* Temporarily store tail node value */
        popLast(): number {
            if (this.queSize === 0) {
                return null;
            }
            const value: number = this.rear.val; // Store tail node value
            // Update tail node
            let temp: ListNode = this.rear.prev;
            if (temp !== null) {
                temp.next = null;
                this.rear.prev = null;
            }
            this.rear = temp; // Update tail node
            this.queSize--;
            return value;
        }

        /* Temporarily store head node value */
        popFirst(): number {
            if (this.queSize === 0) {
                return null;
            }
            const value: number = this.front.val; // Store tail node value
            // Delete head node
            let temp: ListNode = this.front.next;
            if (temp !== null) {
                temp.prev = null;
                this.front.next = null;
            }
            this.front = temp; // Update head node
            this.queSize--;
            return value;
        }

        /* Driver Code */
        peekLast(): number {
            return this.queSize === 0 ? null : this.rear.val;
        }

        /* Return list for printing */
        peekFirst(): number {
            return this.queSize === 0 ? null : this.front.val;
        }

        /* Get the length of the double-ended queue */
        size(): number {
            return this.queSize;
        }

        /* Check if the double-ended queue is empty */
        isEmpty(): boolean {
            return this.queSize === 0;
        }

        /* Print deque */
        print(): void {
            const arr: number[] = [];
            let temp: ListNode = this.front;
            while (temp !== null) {
                arr.push(temp.val);
                temp = temp.next;
            }
            console.log('[' + arr.join(', ') + ']');
        }
    }

linkedlist_deque.dart

    /* Doubly linked list node */
    class ListNode {
      int val; // Node value
      ListNode? next; // Successor node reference
      ListNode? prev; // Predecessor node reference

      ListNode(this.val, {this.next, this.prev});
    }

    /* Deque implemented based on doubly linked list */
    class LinkedListDeque {
      late ListNode? _front; // Head node _front
      late ListNode? _rear; // Tail node _rear
      int _queSize = 0; // Length of the double-ended queue

      LinkedListDeque() {
        this._front = null;
        this._rear = null;
      }

      /* Get deque length */
      int size() {
        return this._queSize;
      }

      /* Check if the double-ended queue is empty */
      bool isEmpty() {
        return size() == 0;
      }

      /* Enqueue operation */
      void push(int _num, bool isFront) {
        final ListNode node = ListNode(_num);
        if (isEmpty()) {
          // If list is empty, let both _front and _rear point to node
          _front = _rear = node;
        } else if (isFront) {
          // Front of the queue enqueue operation
          // Add node to the head of the linked list
          _front!.prev = node;
          node.next = _front;
          _front = node; // Update head node
        } else {
          // Rear of the queue enqueue operation
          // Add node to the tail of the linked list
          _rear!.next = node;
          node.prev = _rear;
          _rear = node; // Update tail node
        }
        _queSize++; // Update queue length
      }

      /* Front of the queue enqueue */
      void pushFirst(int _num) {
        push(_num, true);
      }

      /* Rear of the queue enqueue */
      void pushLast(int _num) {
        push(_num, false);
      }

      /* Dequeue operation */
      int? pop(bool isFront) {
        // If queue is empty, return null directly
        if (isEmpty()) {
          return null;
        }
        final int val;
        if (isFront) {
          // Temporarily store head node value
          val = _front!.val; // Delete head node
          // Delete head node
          ListNode? fNext = _front!.next;
          if (fNext != null) {
            fNext.prev = null;
            _front!.next = null;
          }
          _front = fNext; // Update head node
        } else {
          // Temporarily store tail node value
          val = _rear!.val; // Delete tail node
          // Update tail node
          ListNode? rPrev = _rear!.prev;
          if (rPrev != null) {
            rPrev.next = null;
            _rear!.prev = null;
          }
          _rear = rPrev; // Update tail node
        }
        _queSize--; // Update queue length
        return val;
      }

      /* Rear of the queue dequeue */
      int? popFirst() {
        return pop(true);
      }

      /* Access rear of the queue element */
      int? popLast() {
        return pop(false);
      }

      /* Return list for printing */
      int? peekFirst() {
        return _front?.val;
      }

      /* Driver Code */
      int? peekLast() {
        return _rear?.val;
      }

      /* Return array for printing */
      List<int> toArray() {
        ListNode? node = _front;
        final List<int> res = [];
        for (int i = 0; i < _queSize; i++) {
          res.add(node!.val);
          node = node.next;
        }
        return res;
      }
    }

linkedlist_deque.rs

    /* Doubly linked list node */
    pub struct ListNode<T> {
        pub val: T,                                 // Node value
        pub next: Option<Rc<RefCell<ListNode<T>>>>, // Successor node pointer
        pub prev: Option<Rc<RefCell<ListNode<T>>>>, // Predecessor node pointer
    }

    impl<T> ListNode<T> {
        pub fn new(val: T) -> Rc<RefCell<ListNode<T>>> {
            Rc::new(RefCell::new(ListNode {
                val,
                next: None,
                prev: None,
            }))
        }
    }

    /* Double-ended queue based on doubly linked list implementation */
    #[allow(dead_code)]
    pub struct LinkedListDeque<T> {
        front: Option<Rc<RefCell<ListNode<T>>>>, // Head node front
        rear: Option<Rc<RefCell<ListNode<T>>>>,  // Tail node rear
        que_size: usize,                         // Length of the double-ended queue
    }

    impl<T: Copy> LinkedListDeque<T> {
        pub fn new() -> Self {
            Self {
                front: None,
                rear: None,
                que_size: 0,
            }
        }

        /* Get the length of the double-ended queue */
        pub fn size(&self) -> usize {
            return self.que_size;
        }

        /* Check if the double-ended queue is empty */
        pub fn is_empty(&self) -> bool {
            return self.que_size == 0;
        }

        /* Enqueue operation */
        fn push(&mut self, num: T, is_front: bool) {
            let node = ListNode::new(num);
            // Front of the queue enqueue operation
            if is_front {
                match self.front.take() {
                    // If the linked list is empty, make both front and rear point to node
                    None => {
                        self.rear = Some(node.clone());
                        self.front = Some(node);
                    }
                    // Add node to the head of the linked list
                    Some(old_front) => {
                        old_front.borrow_mut().prev = Some(node.clone());
                        node.borrow_mut().next = Some(old_front);
                        self.front = Some(node); // Update head node
                    }
                }
            }
            // Rear of the queue enqueue operation
            else {
                match self.rear.take() {
                    // If the linked list is empty, make both front and rear point to node
                    None => {
                        self.front = Some(node.clone());
                        self.rear = Some(node);
                    }
                    // Add node to the tail of the linked list
                    Some(old_rear) => {
                        old_rear.borrow_mut().next = Some(node.clone());
                        node.borrow_mut().prev = Some(old_rear);
                        self.rear = Some(node); // Update tail node
                    }
                }
            }
            self.que_size += 1; // Update queue length
        }

        /* Front of the queue enqueue */
        pub fn push_first(&mut self, num: T) {
            self.push(num, true);
        }

        /* Rear of the queue enqueue */
        pub fn push_last(&mut self, num: T) {
            self.push(num, false);
        }

        /* Dequeue operation */
        fn pop(&mut self, is_front: bool) -> Option<T> {
            // If queue is empty, return None directly
            if self.is_empty() {
                return None;
            };
            // Temporarily store head node value
            if is_front {
                self.front.take().map(|old_front| {
                    match old_front.borrow_mut().next.take() {
                        Some(new_front) => {
                            new_front.borrow_mut().prev.take();
                            self.front = Some(new_front); // Update head node
                        }
                        None => {
                            self.rear.take();
                        }
                    }
                    self.que_size -= 1; // Update queue length
                    old_front.borrow().val
                })
            }
            // Temporarily store tail node value
            else {
                self.rear.take().map(|old_rear| {
                    match old_rear.borrow_mut().prev.take() {
                        Some(new_rear) => {
                            new_rear.borrow_mut().next.take();
                            self.rear = Some(new_rear); // Update tail node
                        }
                        None => {
                            self.front.take();
                        }
                    }
                    self.que_size -= 1; // Update queue length
                    old_rear.borrow().val
                })
            }
        }

        /* Rear of the queue dequeue */
        pub fn pop_first(&mut self) -> Option<T> {
            return self.pop(true);
        }

        /* Access rear of the queue element */
        pub fn pop_last(&mut self) -> Option<T> {
            return self.pop(false);
        }

        /* Return list for printing */
        pub fn peek_first(&self) -> Option<&Rc<RefCell<ListNode<T>>>> {
            self.front.as_ref()
        }

        /* Driver Code */
        pub fn peek_last(&self) -> Option<&Rc<RefCell<ListNode<T>>>> {
            self.rear.as_ref()
        }

        /* Return array for printing */
        pub fn to_array(&self, head: Option<&Rc<RefCell<ListNode<T>>>>) -> Vec<T> {
            let mut res: Vec<T> = Vec::new();
            fn recur<T: Copy>(cur: Option<&Rc<RefCell<ListNode<T>>>>, res: &mut Vec<T>) {
                if let Some(cur) = cur {
                    res.push(cur.borrow().val);
                    recur(cur.borrow().next.as_ref(), res);
                }
            }

            recur(head, &mut res);
            res
        }
    }

linkedlist_deque.c

    /* Doubly linked list node */
    typedef struct DoublyListNode {
        int val;                     // Node value
        struct DoublyListNode *next; // Successor node
        struct DoublyListNode *prev; // Predecessor node
    } DoublyListNode;

    /* Constructor */
    DoublyListNode *newDoublyListNode(int num) {
        DoublyListNode *new = (DoublyListNode *)malloc(sizeof(DoublyListNode));
        new->val = num;
        new->next = NULL;
        new->prev = NULL;
        return new;
    }

    /* Destructor */
    void delDoublyListNode(DoublyListNode *node) {
        free(node);
    }

    /* Double-ended queue based on doubly linked list implementation */
    typedef struct {
        DoublyListNode *front, *rear; // Head node front, tail node rear
        int queSize;                  // Length of the double-ended queue
    } LinkedListDeque;

    /* Constructor */
    LinkedListDeque *newLinkedListDeque() {
        LinkedListDeque *deque = (LinkedListDeque *)malloc(sizeof(LinkedListDeque));
        deque->front = NULL;
        deque->rear = NULL;
        deque->queSize = 0;
        return deque;
    }

    /* Destructor */
    void delLinkedListdeque(LinkedListDeque *deque) {
        // Free all nodes
        for (int i = 0; i < deque->queSize && deque->front != NULL; i++) {
            DoublyListNode *tmp = deque->front;
            deque->front = deque->front->next;
            free(tmp);
        }
        // Free deque structure
        free(deque);
    }

    /* Get the length of the queue */
    int size(LinkedListDeque *deque) {
        return deque->queSize;
    }

    /* Check if the queue is empty */
    bool empty(LinkedListDeque *deque) {
        return (size(deque) == 0);
    }

    /* Enqueue */
    void push(LinkedListDeque *deque, int num, bool isFront) {
        DoublyListNode *node = newDoublyListNode(num);
        // If list is empty, set both front and rear to node
        if (empty(deque)) {
            deque->front = deque->rear = node;
        }
        // Front of the queue enqueue operation
        else if (isFront) {
            // Add node to the head of the linked list
            deque->front->prev = node;
            node->next = deque->front;
            deque->front = node; // Update head node
        }
        // Rear of the queue enqueue operation
        else {
            // Add node to the tail of the linked list
            deque->rear->next = node;
            node->prev = deque->rear;
            deque->rear = node;
        }
        deque->queSize++; // Update queue length
    }

    /* Front of the queue enqueue */
    void pushFirst(LinkedListDeque *deque, int num) {
        push(deque, num, true);
    }

    /* Rear of the queue enqueue */
    void pushLast(LinkedListDeque *deque, int num) {
        push(deque, num, false);
    }

    /* Return list for printing */
    int peekFirst(LinkedListDeque *deque) {
        assert(size(deque) && deque->front);
        return deque->front->val;
    }

    /* Driver Code */
    int peekLast(LinkedListDeque *deque) {
        assert(size(deque) && deque->rear);
        return deque->rear->val;
    }

    /* Dequeue */
    int pop(LinkedListDeque *deque, bool isFront) {
        if (empty(deque))
            return -1;
        int val;
        // Temporarily store head node value
        if (isFront) {
            val = peekFirst(deque); // Delete head node
            DoublyListNode *fNext = deque->front->next;
            if (fNext) {
                fNext->prev = NULL;
                deque->front->next = NULL;
            }
            delDoublyListNode(deque->front);
            deque->front = fNext; // Update head node
        }
        // Temporarily store tail node value
        else {
            val = peekLast(deque); // Delete tail node
            DoublyListNode *rPrev = deque->rear->prev;
            if (rPrev) {
                rPrev->next = NULL;
                deque->rear->prev = NULL;
            }
            delDoublyListNode(deque->rear);
            deque->rear = rPrev; // Update tail node
        }
        deque->queSize--; // Update queue length
        return val;
    }

    /* Rear of the queue dequeue */
    int popFirst(LinkedListDeque *deque) {
        return pop(deque, true);
    }

    /* Access rear of the queue element */
    int popLast(LinkedListDeque *deque) {
        return pop(deque, false);
    }

    /* Print queue */
    void printLinkedListDeque(LinkedListDeque *deque) {
        int *arr = malloc(sizeof(int) * deque->queSize);
        // Copy data from list to array
        int i;
        DoublyListNode *node;
        for (i = 0, node = deque->front; i < deque->queSize; i++) {
            arr[i] = node->val;
            node = node->next;
        }
        printArray(arr, deque->queSize);
        free(arr);
    }

linkedlist_deque.kt

    /* Doubly linked list node */
    class ListNode(var _val: Int) {
        // Node value
        var next: ListNode? = null // Successor node reference
        var prev: ListNode? = null // Predecessor node reference
    }

    /* Double-ended queue based on doubly linked list implementation */
    class LinkedListDeque {
        private var front: ListNode? = null // Head node front
        private var rear: ListNode? = null // Tail node rear
        private var queSize: Int = 0 // Length of the double-ended queue

        /* Get the length of the double-ended queue */
        fun size(): Int {
            return queSize
        }

        /* Check if the double-ended queue is empty */
        fun isEmpty(): Boolean {
            return size() == 0
        }

        /* Enqueue operation */
        fun push(num: Int, isFront: Boolean) {
            val node = ListNode(num)
            // If the linked list is empty, make both front and rear point to node
            if (isEmpty()) {
                rear = node
                front = rear
                // Front of the queue enqueue operation
            } else if (isFront) {
                // Add node to the head of the linked list
                front?.prev = node
                node.next = front
                front = node // Update head node
                // Rear of the queue enqueue operation
            } else {
                // Add node to the tail of the linked list
                rear?.next = node
                node.prev = rear
                rear = node // Update tail node
            }
            queSize++ // Update queue length
        }

        /* Front of the queue enqueue */
        fun pushFirst(num: Int) {
            push(num, true)
        }

        /* Rear of the queue enqueue */
        fun pushLast(num: Int) {
            push(num, false)
        }

        /* Dequeue operation */
        fun pop(isFront: Boolean): Int {
            if (isEmpty())
                throw IndexOutOfBoundsException()
            val _val: Int
            // Temporarily store head node value
            if (isFront) {
                _val = front!!._val // Delete head node
                // Delete head node
                val fNext = front!!.next
                if (fNext != null) {
                    fNext.prev = null
                    front!!.next = null
                }
                front = fNext // Update head node
                // Temporarily store tail node value
            } else {
                _val = rear!!._val // Delete tail node
                // Update tail node
                val rPrev = rear!!.prev
                if (rPrev != null) {
                    rPrev.next = null
                    rear!!.prev = null
                }
                rear = rPrev // Update tail node
            }
            queSize-- // Update queue length
            return _val
        }

        /* Rear of the queue dequeue */
        fun popFirst(): Int {
            return pop(true)
        }

        /* Access rear of the queue element */
        fun popLast(): Int {
            return pop(false)
        }

        /* Return list for printing */
        fun peekFirst(): Int {
            if (isEmpty()) throw IndexOutOfBoundsException()
            return front!!._val
        }

        /* Driver Code */
        fun peekLast(): Int {
            if (isEmpty()) throw IndexOutOfBoundsException()
            return rear!!._val
        }

        /* Return array for printing */
        fun toArray(): IntArray {
            var node = front
            val res = IntArray(size())
            for (i in res.indices) {
                res[i] = node!!._val
                node = node.next
            }
            return res
        }
    }

linkedlist_deque.rb

    =begin
    File: linkedlist_deque.rb
    Created Time: 2024-04-06
    Author: Xuan Khoa Tu Nguyen (ngxktuzkai2000@gmail.com)
    =end

    ### Doubly linked list node
    class ListNode
      attr_accessor :val
      attr_accessor :next # Successor node reference
      attr_accessor :prev # Predecessor node reference

      ### Constructor ###
      def initialize(val)
        @val = val
      end
    end

    ### Deque based on doubly linked list ###
    class LinkedListDeque
      ### Get deque length ###
      attr_reader :size

      ### Constructor ###
      def initialize
        @front = nil  # Head node front
        @rear = nil   # Tail node rear
        @size = 0     # Length of the double-ended queue
      end

      ### Check if deque is empty ###
      def is_empty?
        size.zero?
      end

      ### Enqueue operation ###
      def push(num, is_front)
        node = ListNode.new(num)
        # If list is empty, set both front and rear to node
        if is_empty?
          @front = @rear = node
        # Front of the queue enqueue operation
        elsif is_front
          # Add node to the head of the linked list
          @front.prev = node
          node.next = @front
          @front = node # Update head node
        # Rear of the queue enqueue operation
        else
          # Add node to the tail of the linked list
          @rear.next = node
          node.prev = @rear
          @rear = node # Update tail node
        end
        @size += 1 # Update queue length
      end

      ### Enqueue at front ###
      def push_first(num)
        push(num, true)
      end

      ### Enqueue at rear ###
      def push_last(num)
        push(num, false)
      end

      ### Dequeue operation ###
      def pop(is_front)
        raise IndexError, 'Deque is empty' if is_empty?

        # Temporarily store head node value
        if is_front
          val = @front.val # Delete head node
          # Delete head node
          fnext = @front.next
          unless fnext.nil?
            fnext.prev = nil
            @front.next = nil
          end
          @front = fnext # Update head node
        # Temporarily store tail node value
        else
          val = @rear.val # Delete tail node
          # Update tail node
          rprev = @rear.prev
          unless rprev.nil?
            rprev.next = nil
            @rear.prev = nil
          end
          @rear = rprev # Update tail node
        end
        @size -= 1 # Update queue length

        val
      end

      ### Dequeue from front ###
      def pop_first
        pop(true)
      end

      ### Dequeue from front ###
      def pop_last
        pop(false)
      end

      ### Access front element ###
      def peek_first
        raise IndexError, 'Deque is empty' if is_empty?

        @front.val
      end

      ### Access rear element ###
      def peek_last
        raise IndexError, 'Deque is empty' if is_empty?

        @rear.val
      end

      ### Return array for printing ###
      def to_array
        node = @front
        res = Array.new(size, 0)
        for i in 0...size
          res[i] = node.val
          node = node.next
        end
        res
      end
    end

### 2. Array Implementation

As shown in Figure 5-9, similar to implementing a queue based on an array, we can also use a circular array to implement a deque.

<1><2><3><4><5>

Figure 5-9 Enqueue and dequeue operations in array implementation of deque

Based on the queue implementation, we only need to add methods for "enqueue at front" and "dequeue from rear":

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
array_deque.py

    class ArrayDeque:
        """Double-ended queue based on circular array implementation"""

        def __init__(self, capacity: int):
            """Constructor"""
            self._nums: list[int] = [0] * capacity
            self._front: int = 0
            self._size: int = 0

        def capacity(self) -> int:
            """Get the capacity of the double-ended queue"""
            return len(self._nums)

        def size(self) -> int:
            """Get the length of the double-ended queue"""
            return self._size

        def is_empty(self) -> bool:
            """Check if the double-ended queue is empty"""
            return self._size == 0

        def index(self, i: int) -> int:
            """Calculate circular array index"""
            # Use modulo operation to wrap the array head and tail together
            # When i passes the tail of the array, return to the head
            # When i passes the head of the array, return to the tail
            return (i + self.capacity()) % self.capacity()

        def push_first(self, num: int):
            """Front of the queue enqueue"""
            if self._size == self.capacity():
                print("Double-ended queue is full")
                return
            # Front pointer moves one position to the left
            # Use modulo operation to wrap front around to the tail after passing the head of the array
            self._front = self.index(self._front - 1)
            # Add num to the front of the queue
            self._nums[self._front] = num
            self._size += 1

        def push_last(self, num: int):
            """Rear of the queue enqueue"""
            if self._size == self.capacity():
                print("Double-ended queue is full")
                return
            # Calculate rear pointer, points to rear index + 1
            rear = self.index(self._front + self._size)
            # Add num to the rear of the queue
            self._nums[rear] = num
            self._size += 1

        def pop_first(self) -> int:
            """Front of the queue dequeue"""
            num = self.peek_first()
            # Front pointer moves one position backward
            self._front = self.index(self._front + 1)
            self._size -= 1
            return num

        def pop_last(self) -> int:
            """Rear of the queue dequeue"""
            num = self.peek_last()
            self._size -= 1
            return num

        def peek_first(self) -> int:
            """Access front of the queue element"""
            if self.is_empty():
                raise IndexError("Double-ended queue is empty")
            return self._nums[self._front]

        def peek_last(self) -> int:
            """Access rear of the queue element"""
            if self.is_empty():
                raise IndexError("Double-ended queue is empty")
            # Calculate tail element index
            last = self.index(self._front + self._size - 1)
            return self._nums[last]

        def to_array(self) -> list[int]:
            """Return array for printing"""
            # Only convert list elements within the valid length range
            res = []
            for i in range(self._size):
                res.append(self._nums[self.index(self._front + i)])
            return res

array_deque.cpp

    /* Double-ended queue based on circular array implementation */
    class ArrayDeque {
      private:
        vector<int> nums; // Array for storing double-ended queue elements
        int front;        // Front pointer, points to the front of the queue element
        int queSize;      // Double-ended queue length

      public:
        /* Constructor */
        ArrayDeque(int capacity) {
            nums.resize(capacity);
            front = queSize = 0;
        }

        /* Get the capacity of the double-ended queue */
        int capacity() {
            return nums.size();
        }

        /* Get the length of the double-ended queue */
        int size() {
            return queSize;
        }

        /* Check if the double-ended queue is empty */
        bool isEmpty() {
            return queSize == 0;
        }

        /* Calculate circular array index */
        int index(int i) {
            // Use modulo operation to wrap the array head and tail together
            // When i passes the tail of the array, return to the head
            // When i passes the head of the array, return to the tail
            return (i + capacity()) % capacity();
        }

        /* Front of the queue enqueue */
        void pushFirst(int num) {
            if (queSize == capacity()) {
                cout << "Double-ended queue is full" << endl;
                return;
            }
            // Use modulo operation to wrap front around to the tail after passing the head of the array
            // Add num to the front of the queue
            front = index(front - 1);
            // Add num to front of queue
            nums[front] = num;
            queSize++;
        }

        /* Rear of the queue enqueue */
        void pushLast(int num) {
            if (queSize == capacity()) {
                cout << "Double-ended queue is full" << endl;
                return;
            }
            // Use modulo operation to wrap rear around to the head after passing the tail of the array
            int rear = index(front + queSize);
            // Front pointer moves one position backward
            nums[rear] = num;
            queSize++;
        }

        /* Rear of the queue dequeue */
        int popFirst() {
            int num = peekFirst();
            // Move front pointer backward by one position
            front = index(front + 1);
            queSize--;
            return num;
        }

        /* Access rear of the queue element */
        int popLast() {
            int num = peekLast();
            queSize--;
            return num;
        }

        /* Return list for printing */
        int peekFirst() {
            if (isEmpty())
                throw out_of_range("Deque is empty");
            return nums[front];
        }

        /* Driver Code */
        int peekLast() {
            if (isEmpty())
                throw out_of_range("Deque is empty");
            // Initialize double-ended queue
            int last = index(front + queSize - 1);
            return nums[last];
        }

        /* Return array for printing */
        vector<int> toVector() {
            // Elements enqueue
            vector<int> res(queSize);
            for (int i = 0, j = front; i < queSize; i++, j++) {
                res[i] = nums[index(j)];
            }
            return res;
        }
    };

array_deque.java

    /* Double-ended queue based on circular array implementation */
    class ArrayDeque {
        private int[] nums; // Array for storing double-ended queue elements
        private int front; // Front pointer, points to the front of the queue element
        private int queSize; // Double-ended queue length

        /* Constructor */
        public ArrayDeque(int capacity) {
            this.nums = new int[capacity];
            front = queSize = 0;
        }

        /* Get the capacity of the double-ended queue */
        public int capacity() {
            return nums.length;
        }

        /* Get the length of the double-ended queue */
        public int size() {
            return queSize;
        }

        /* Check if the double-ended queue is empty */
        public boolean isEmpty() {
            return queSize == 0;
        }

        /* Calculate circular array index */
        private int index(int i) {
            // Use modulo operation to wrap the array head and tail together
            // When i passes the tail of the array, return to the head
            // When i passes the head of the array, return to the tail
            return (i + capacity()) % capacity();
        }

        /* Front of the queue enqueue */
        public void pushFirst(int num) {
            if (queSize == capacity()) {
                System.out.println("Double-ended queue is full");
                return;
            }
            // Use modulo operation to wrap front around to the tail after passing the head of the array
            // Add num to the front of the queue
            front = index(front - 1);
            // Add num to front of queue
            nums[front] = num;
            queSize++;
        }

        /* Rear of the queue enqueue */
        public void pushLast(int num) {
            if (queSize == capacity()) {
                System.out.println("Double-ended queue is full");
                return;
            }
            // Use modulo operation to wrap rear around to the head after passing the tail of the array
            int rear = index(front + queSize);
            // Front pointer moves one position backward
            nums[rear] = num;
            queSize++;
        }

        /* Rear of the queue dequeue */
        public int popFirst() {
            int num = peekFirst();
            // Move front pointer backward by one position
            front = index(front + 1);
            queSize--;
            return num;
        }

        /* Access rear of the queue element */
        public int popLast() {
            int num = peekLast();
            queSize--;
            return num;
        }

        /* Return list for printing */
        public int peekFirst() {
            if (isEmpty())
                throw new IndexOutOfBoundsException();
            return nums[front];
        }

        /* Driver Code */
        public int peekLast() {
            if (isEmpty())
                throw new IndexOutOfBoundsException();
            // Initialize double-ended queue
            int last = index(front + queSize - 1);
            return nums[last];
        }

        /* Return array for printing */
        public int[] toArray() {
            // Elements enqueue
            int[] res = new int[queSize];
            for (int i = 0, j = front; i < queSize; i++, j++) {
                res[i] = nums[index(j)];
            }
            return res;
        }
    }

array_deque.cs

    /* Double-ended queue based on circular array implementation */
    class ArrayDeque {
        int[] nums;  // Array for storing double-ended queue elements
        int front;   // Front pointer, points to the front of the queue element
        int queSize; // Double-ended queue length

        /* Constructor */
        public ArrayDeque(int capacity) {
            nums = new int[capacity];
            front = queSize = 0;
        }

        /* Get the capacity of the double-ended queue */
        int Capacity() {
            return nums.Length;
        }

        /* Get the length of the double-ended queue */
        public int Size() {
            return queSize;
        }

        /* Check if the double-ended queue is empty */
        public bool IsEmpty() {
            return queSize == 0;
        }

        /* Calculate circular array index */
        int Index(int i) {
            // Use modulo operation to wrap the array head and tail together
            // When i passes the tail of the array, return to the head
            // When i passes the head of the array, return to the tail
            return (i + Capacity()) % Capacity();
        }

        /* Front of the queue enqueue */
        public void PushFirst(int num) {
            if (queSize == Capacity()) {
                Console.WriteLine("Double-ended queue is full");
                return;
            }
            // Use modulo operation to wrap front around to the tail after passing the head of the array
            // Add num to the front of the queue
            front = Index(front - 1);
            // Add num to front of queue
            nums[front] = num;
            queSize++;
        }

        /* Rear of the queue enqueue */
        public void PushLast(int num) {
            if (queSize == Capacity()) {
                Console.WriteLine("Double-ended queue is full");
                return;
            }
            // Use modulo operation to wrap rear around to the head after passing the tail of the array
            int rear = Index(front + queSize);
            // Front pointer moves one position backward
            nums[rear] = num;
            queSize++;
        }

        /* Rear of the queue dequeue */
        public int PopFirst() {
            int num = PeekFirst();
            // Move front pointer backward by one position
            front = Index(front + 1);
            queSize--;
            return num;
        }

        /* Access rear of the queue element */
        public int PopLast() {
            int num = PeekLast();
            queSize--;
            return num;
        }

        /* Return list for printing */
        public int PeekFirst() {
            if (IsEmpty()) {
                throw new InvalidOperationException();
            }
            return nums[front];
        }

        /* Driver Code */
        public int PeekLast() {
            if (IsEmpty()) {
                throw new InvalidOperationException();
            }
            // Initialize double-ended queue
            int last = Index(front + queSize - 1);
            return nums[last];
        }

        /* Return array for printing */
        public int[] ToArray() {
            // Elements enqueue
            int[] res = new int[queSize];
            for (int i = 0, j = front; i < queSize; i++, j++) {
                res[i] = nums[Index(j)];
            }
            return res;
        }
    }

array_deque.go

    /* Double-ended queue based on circular array implementation */
    type arrayDeque struct {
        nums        []int // Array for storing double-ended queue elements
        front       int   // Front pointer, points to the front of the queue element
        queSize     int   // Double-ended queue length
        queCapacity int   // Queue capacity (maximum number of elements)
    }

    /* Access front of the queue element */
    func newArrayDeque(queCapacity int) *arrayDeque {
        return &arrayDeque{
            nums:        make([]int, queCapacity),
            queCapacity: queCapacity,
            front:       0,
            queSize:     0,
        }
    }

    /* Get the length of the double-ended queue */
    func (q *arrayDeque) size() int {
        return q.queSize
    }

    /* Check if the double-ended queue is empty */
    func (q *arrayDeque) isEmpty() bool {
        return q.queSize == 0
    }

    /* Calculate circular array index */
    func (q *arrayDeque) index(i int) int {
        // Use modulo operation to wrap the array head and tail together
        // When i passes the tail of the array, return to the head
        // When i passes the head of the array, return to the tail
        return (i + q.queCapacity) % q.queCapacity
    }

    /* Front of the queue enqueue */
    func (q *arrayDeque) pushFirst(num int) {
        if q.queSize == q.queCapacity {
            fmt.Println("Double-ended queue is full")
            return
        }
        // Use modulo operation to wrap front around to the tail after passing the head of the array
        // Add num to the front of the queue
        q.front = q.index(q.front - 1)
        // Add num to front of queue
        q.nums[q.front] = num
        q.queSize++
    }

    /* Rear of the queue enqueue */
    func (q *arrayDeque) pushLast(num int) {
        if q.queSize == q.queCapacity {
            fmt.Println("Double-ended queue is full")
            return
        }
        // Use modulo operation to wrap rear around to the head after passing the tail of the array
        rear := q.index(q.front + q.queSize)
        // Front pointer moves one position backward
        q.nums[rear] = num
        q.queSize++
    }

    /* Rear of the queue dequeue */
    func (q *arrayDeque) popFirst() any {
        num := q.peekFirst()
        if num == nil {
            return nil
        }
        // Move front pointer backward by one position
        q.front = q.index(q.front + 1)
        q.queSize--
        return num
    }

    /* Access rear of the queue element */
    func (q *arrayDeque) popLast() any {
        num := q.peekLast()
        if num == nil {
            return nil
        }
        q.queSize--
        return num
    }

    /* Return list for printing */
    func (q *arrayDeque) peekFirst() any {
        if q.isEmpty() {
            return nil
        }
        return q.nums[q.front]
    }

    /* Driver Code */
    func (q *arrayDeque) peekLast() any {
        if q.isEmpty() {
            return nil
        }
        // Initialize double-ended queue
        last := q.index(q.front + q.queSize - 1)
        return q.nums[last]
    }

    /* Get Slice for printing */
    func (q *arrayDeque) toSlice() []int {
        // Elements enqueue
        res := make([]int, q.queSize)
        for i, j := 0, q.front; i < q.queSize; i++ {
            res[i] = q.nums[q.index(j)]
            j++
        }
        return res
    }

array_deque.swift

    /* Double-ended queue based on circular array implementation */
    class ArrayDeque {
        private var nums: [Int] // Array for storing double-ended queue elements
        private var front: Int // Front pointer, points to the front of the queue element
        private var _size: Int // Double-ended queue length

        /* Constructor */
        init(capacity: Int) {
            nums = Array(repeating: 0, count: capacity)
            front = 0
            _size = 0
        }

        /* Get the capacity of the double-ended queue */
        func capacity() -> Int {
            nums.count
        }

        /* Get the length of the double-ended queue */
        func size() -> Int {
            _size
        }

        /* Check if the double-ended queue is empty */
        func isEmpty() -> Bool {
            size() == 0
        }

        /* Calculate circular array index */
        private func index(i: Int) -> Int {
            // Use modulo operation to wrap the array head and tail together
            // When i passes the tail of the array, return to the head
            // When i passes the head of the array, return to the tail
            (i + capacity()) % capacity()
        }

        /* Front of the queue enqueue */
        func pushFirst(num: Int) {
            if size() == capacity() {
                print("Double-ended queue is full")
                return
            }
            // Use modulo operation to wrap front around to the tail after passing the head of the array
            // Add num to the front of the queue
            front = index(i: front - 1)
            // Add num to front of queue
            nums[front] = num
            _size += 1
        }

        /* Rear of the queue enqueue */
        func pushLast(num: Int) {
            if size() == capacity() {
                print("Double-ended queue is full")
                return
            }
            // Use modulo operation to wrap rear around to the head after passing the tail of the array
            let rear = index(i: front + size())
            // Front pointer moves one position backward
            nums[rear] = num
            _size += 1
        }

        /* Rear of the queue dequeue */
        func popFirst() -> Int {
            let num = peekFirst()
            // Move front pointer backward by one position
            front = index(i: front + 1)
            _size -= 1
            return num
        }

        /* Access rear of the queue element */
        func popLast() -> Int {
            let num = peekLast()
            _size -= 1
            return num
        }

        /* Return list for printing */
        func peekFirst() -> Int {
            if isEmpty() {
                fatalError("Deque is empty")
            }
            return nums[front]
        }

        /* Driver Code */
        func peekLast() -> Int {
            if isEmpty() {
                fatalError("Deque is empty")
            }
            // Initialize double-ended queue
            let last = index(i: front + size() - 1)
            return nums[last]
        }

        /* Return array for printing */
        func toArray() -> [Int] {
            // Elements enqueue
            (front ..< front + size()).map { nums[index(i: $0)] }
        }
    }

array_deque.js

    /* Double-ended queue based on circular array implementation */
    class ArrayDeque {
        #nums; // Array for storing double-ended queue elements
        #front; // Front pointer, points to the front of the queue element
        #queSize; // Double-ended queue length

        /* Constructor */
        constructor(capacity) {
            this.#nums = new Array(capacity);
            this.#front = 0;
            this.#queSize = 0;
        }

        /* Get the capacity of the double-ended queue */
        capacity() {
            return this.#nums.length;
        }

        /* Get the length of the double-ended queue */
        size() {
            return this.#queSize;
        }

        /* Check if the double-ended queue is empty */
        isEmpty() {
            return this.#queSize === 0;
        }

        /* Calculate circular array index */
        index(i) {
            // Use modulo operation to wrap the array head and tail together
            // When i passes the tail of the array, return to the head
            // When i passes the head of the array, return to the tail
            return (i + this.capacity()) % this.capacity();
        }

        /* Front of the queue enqueue */
        pushFirst(num) {
            if (this.#queSize === this.capacity()) {
                console.log('Double-ended queue is full');
                return;
            }
            // Use modulo operation to wrap front around to the tail after passing the head of the array
            // Add num to the front of the queue
            this.#front = this.index(this.#front - 1);
            // Add num to front of queue
            this.#nums[this.#front] = num;
            this.#queSize++;
        }

        /* Rear of the queue enqueue */
        pushLast(num) {
            if (this.#queSize === this.capacity()) {
                console.log('Double-ended queue is full');
                return;
            }
            // Use modulo operation to wrap rear around to the head after passing the tail of the array
            const rear = this.index(this.#front + this.#queSize);
            // Front pointer moves one position backward
            this.#nums[rear] = num;
            this.#queSize++;
        }

        /* Rear of the queue dequeue */
        popFirst() {
            const num = this.peekFirst();
            // Move front pointer backward by one position
            this.#front = this.index(this.#front + 1);
            this.#queSize--;
            return num;
        }

        /* Access rear of the queue element */
        popLast() {
            const num = this.peekLast();
            this.#queSize--;
            return num;
        }

        /* Return list for printing */
        peekFirst() {
            if (this.isEmpty()) throw new Error('The Deque Is Empty.');
            return this.#nums[this.#front];
        }

        /* Driver Code */
        peekLast() {
            if (this.isEmpty()) throw new Error('The Deque Is Empty.');
            // Initialize double-ended queue
            const last = this.index(this.#front + this.#queSize - 1);
            return this.#nums[last];
        }

        /* Return array for printing */
        toArray() {
            // Elements enqueue
            const res = [];
            for (let i = 0, j = this.#front; i < this.#queSize; i++, j++) {
                res[i] = this.#nums[this.index(j)];
            }
            return res;
        }
    }

array_deque.ts

    /* Double-ended queue based on circular array implementation */
    class ArrayDeque {
        private nums: number[]; // Array for storing double-ended queue elements
        private front: number; // Front pointer, points to the front of the queue element
        private queSize: number; // Double-ended queue length

        /* Constructor */
        constructor(capacity: number) {
            this.nums = new Array(capacity);
            this.front = 0;
            this.queSize = 0;
        }

        /* Get the capacity of the double-ended queue */
        capacity(): number {
            return this.nums.length;
        }

        /* Get the length of the double-ended queue */
        size(): number {
            return this.queSize;
        }

        /* Check if the double-ended queue is empty */
        isEmpty(): boolean {
            return this.queSize === 0;
        }

        /* Calculate circular array index */
        index(i: number): number {
            // Use modulo operation to wrap the array head and tail together
            // When i passes the tail of the array, return to the head
            // When i passes the head of the array, return to the tail
            return (i + this.capacity()) % this.capacity();
        }

        /* Front of the queue enqueue */
        pushFirst(num: number): void {
            if (this.queSize === this.capacity()) {
                console.log('Double-ended queue is full');
                return;
            }
            // Use modulo operation to wrap front around to the tail after passing the head of the array
            // Add num to the front of the queue
            this.front = this.index(this.front - 1);
            // Add num to front of queue
            this.nums[this.front] = num;
            this.queSize++;
        }

        /* Rear of the queue enqueue */
        pushLast(num: number): void {
            if (this.queSize === this.capacity()) {
                console.log('Double-ended queue is full');
                return;
            }
            // Use modulo operation to wrap rear around to the head after passing the tail of the array
            const rear: number = this.index(this.front + this.queSize);
            // Front pointer moves one position backward
            this.nums[rear] = num;
            this.queSize++;
        }

        /* Rear of the queue dequeue */
        popFirst(): number {
            const num: number = this.peekFirst();
            // Move front pointer backward by one position
            this.front = this.index(this.front + 1);
            this.queSize--;
            return num;
        }

        /* Access rear of the queue element */
        popLast(): number {
            const num: number = this.peekLast();
            this.queSize--;
            return num;
        }

        /* Return list for printing */
        peekFirst(): number {
            if (this.isEmpty()) throw new Error('The Deque Is Empty.');
            return this.nums[this.front];
        }

        /* Driver Code */
        peekLast(): number {
            if (this.isEmpty()) throw new Error('The Deque Is Empty.');
            // Initialize double-ended queue
            const last = this.index(this.front + this.queSize - 1);
            return this.nums[last];
        }

        /* Return array for printing */
        toArray(): number[] {
            // Elements enqueue
            const res: number[] = [];
            for (let i = 0, j = this.front; i < this.queSize; i++, j++) {
                res[i] = this.nums[this.index(j)];
            }
            return res;
        }
    }

array_deque.dart

    /* Double-ended queue based on circular array implementation */
    class ArrayDeque {
      late List<int> _nums; // Array for storing double-ended queue elements
      late int _front; // Front pointer, points to the front of the queue element
      late int _queSize; // Double-ended queue length

      /* Constructor */
      ArrayDeque(int capacity) {
        this._nums = List.filled(capacity, 0);
        this._front = this._queSize = 0;
      }

      /* Get the capacity of the double-ended queue */
      int capacity() {
        return _nums.length;
      }

      /* Get the length of the double-ended queue */
      int size() {
        return _queSize;
      }

      /* Check if the double-ended queue is empty */
      bool isEmpty() {
        return _queSize == 0;
      }

      /* Calculate circular array index */
      int index(int i) {
        // Use modulo operation to wrap the array head and tail together
        // When i passes the tail of the array, return to the head
        // When i passes the head of the array, return to the tail
        return (i + capacity()) % capacity();
      }

      /* Front of the queue enqueue */
      void pushFirst(int _num) {
        if (_queSize == capacity()) {
          throw Exception("Double-ended queue is full");
        }
        // Use modulo operation to wrap front around to the tail after passing the head of the array
        // Use modulo operation to wrap _front from array head back to tail
        _front = index(_front - 1);
        // Add _num to queue front
        _nums[_front] = _num;
        _queSize++;
      }

      /* Rear of the queue enqueue */
      void pushLast(int _num) {
        if (_queSize == capacity()) {
          throw Exception("Double-ended queue is full");
        }
        // Use modulo operation to wrap rear around to the head after passing the tail of the array
        int rear = index(_front + _queSize);
        // Add _num to queue rear
        _nums[rear] = _num;
        _queSize++;
      }

      /* Rear of the queue dequeue */
      int popFirst() {
        int _num = peekFirst();
        // Move front pointer right by one
        _front = index(_front + 1);
        _queSize--;
        return _num;
      }

      /* Access rear of the queue element */
      int popLast() {
        int _num = peekLast();
        _queSize--;
        return _num;
      }

      /* Return list for printing */
      int peekFirst() {
        if (isEmpty()) {
          throw Exception("Deque is empty");
        }
        return _nums[_front];
      }

      /* Driver Code */
      int peekLast() {
        if (isEmpty()) {
          throw Exception("Deque is empty");
        }
        // Initialize double-ended queue
        int last = index(_front + _queSize - 1);
        return _nums[last];
      }

      /* Return array for printing */
      List<int> toArray() {
        // Elements enqueue
        List<int> res = List.filled(_queSize, 0);
        for (int i = 0, j = _front; i < _queSize; i++, j++) {
          res[i] = _nums[index(j)];
        }
        return res;
      }
    }

array_deque.rs

    /* Double-ended queue based on circular array implementation */
    struct ArrayDeque<T> {
        nums: Vec<T>,    // Array for storing double-ended queue elements
        front: usize,    // Front pointer, points to the front of the queue element
        que_size: usize, // Double-ended queue length
    }

    impl<T: Copy + Default> ArrayDeque<T> {
        /* Constructor */
        pub fn new(capacity: usize) -> Self {
            Self {
                nums: vec![T::default(); capacity],
                front: 0,
                que_size: 0,
            }
        }

        /* Get the capacity of the double-ended queue */
        pub fn capacity(&self) -> usize {
            self.nums.len()
        }

        /* Get the length of the double-ended queue */
        pub fn size(&self) -> usize {
            self.que_size
        }

        /* Check if the double-ended queue is empty */
        pub fn is_empty(&self) -> bool {
            self.que_size == 0
        }

        /* Calculate circular array index */
        fn index(&self, i: i32) -> usize {
            // Use modulo operation to wrap the array head and tail together
            // When i passes the tail of the array, return to the head
            // When i passes the head of the array, return to the tail
            ((i + self.capacity() as i32) % self.capacity() as i32) as usize
        }

        /* Front of the queue enqueue */
        pub fn push_first(&mut self, num: T) {
            if self.que_size == self.capacity() {
                println!("Double-ended queue is full");
                return;
            }
            // Use modulo operation to wrap front around to the tail after passing the head of the array
            // Add num to the front of the queue
            self.front = self.index(self.front as i32 - 1);
            // Add num to front of queue
            self.nums[self.front] = num;
            self.que_size += 1;
        }

        /* Rear of the queue enqueue */
        pub fn push_last(&mut self, num: T) {
            if self.que_size == self.capacity() {
                println!("Double-ended queue is full");
                return;
            }
            // Use modulo operation to wrap rear around to the head after passing the tail of the array
            let rear = self.index(self.front as i32 + self.que_size as i32);
            // Front pointer moves one position backward
            self.nums[rear] = num;
            self.que_size += 1;
        }

        /* Rear of the queue dequeue */
        fn pop_first(&mut self) -> T {
            let num = self.peek_first();
            // Move front pointer backward by one position
            self.front = self.index(self.front as i32 + 1);
            self.que_size -= 1;
            num
        }

        /* Access rear of the queue element */
        fn pop_last(&mut self) -> T {
            let num = self.peek_last();
            self.que_size -= 1;
            num
        }

        /* Return list for printing */
        fn peek_first(&self) -> T {
            if self.is_empty() {
                panic!("Deque is empty")
            };
            self.nums[self.front]
        }

        /* Driver Code */
        fn peek_last(&self) -> T {
            if self.is_empty() {
                panic!("Deque is empty")
            };
            // Initialize double-ended queue
            let last = self.index(self.front as i32 + self.que_size as i32 - 1);
            self.nums[last]
        }

        /* Return array for printing */
        fn to_array(&self) -> Vec<T> {
            // Elements enqueue
            let mut res = vec![T::default(); self.que_size];
            let mut j = self.front;
            for i in 0..self.que_size {
                res[i] = self.nums[self.index(j as i32)];
                j += 1;
            }
            res
        }
    }

array_deque.c

    /* Double-ended queue based on circular array implementation */
    typedef struct {
        int *nums;       // Array for storing queue elements
        int front;       // Front pointer, points to the front of the queue element
        int queSize;     // Rear pointer, points to rear + 1
        int queCapacity; // Queue capacity
    } ArrayDeque;

    /* Constructor */
    ArrayDeque *newArrayDeque(int capacity) {
        ArrayDeque *deque = (ArrayDeque *)malloc(sizeof(ArrayDeque));
        // Initialize array
        deque->queCapacity = capacity;
        deque->nums = (int *)malloc(sizeof(int) * deque->queCapacity);
        deque->front = deque->queSize = 0;
        return deque;
    }

    /* Destructor */
    void delArrayDeque(ArrayDeque *deque) {
        free(deque->nums);
        free(deque);
    }

    /* Get the capacity of the double-ended queue */
    int capacity(ArrayDeque *deque) {
        return deque->queCapacity;
    }

    /* Get the length of the double-ended queue */
    int size(ArrayDeque *deque) {
        return deque->queSize;
    }

    /* Check if the double-ended queue is empty */
    bool empty(ArrayDeque *deque) {
        return deque->queSize == 0;
    }

    /* Calculate circular array index */
    int dequeIndex(ArrayDeque *deque, int i) {
        // Use modulo operation to wrap the array head and tail together
        // When i exceeds array end, wrap to head
        // When i passes the head of the array, return to the tail
        return ((i + capacity(deque)) % capacity(deque));
    }

    /* Front of the queue enqueue */
    void pushFirst(ArrayDeque *deque, int num) {
        if (deque->queSize == capacity(deque)) {
            printf("Deque is full\r\n");
            return;
        }
        // Use modulo operation to wrap front around to the tail after passing the head of the array
        // Use modulo to wrap front from array head to rear
        deque->front = dequeIndex(deque, deque->front - 1);
        // Add num to queue front
        deque->nums[deque->front] = num;
        deque->queSize++;
    }

    /* Rear of the queue enqueue */
    void pushLast(ArrayDeque *deque, int num) {
        if (deque->queSize == capacity(deque)) {
            printf("Deque is full\r\n");
            return;
        }
        // Use modulo operation to wrap rear around to the head after passing the tail of the array
        int rear = dequeIndex(deque, deque->front + deque->queSize);
        // Front pointer moves one position backward
        deque->nums[rear] = num;
        deque->queSize++;
    }

    /* Return list for printing */
    int peekFirst(ArrayDeque *deque) {
        // Access error: Deque is empty
        assert(empty(deque) == 0);
        return deque->nums[deque->front];
    }

    /* Driver Code */
    int peekLast(ArrayDeque *deque) {
        // Access error: Deque is empty
        assert(empty(deque) == 0);
        int last = dequeIndex(deque, deque->front + deque->queSize - 1);
        return deque->nums[last];
    }

    /* Rear of the queue dequeue */
    int popFirst(ArrayDeque *deque) {
        int num = peekFirst(deque);
        // Move front pointer backward by one position
        deque->front = dequeIndex(deque, deque->front + 1);
        deque->queSize--;
        return num;
    }

    /* Access rear of the queue element */
    int popLast(ArrayDeque *deque) {
        int num = peekLast(deque);
        deque->queSize--;
        return num;
    }

    /* Return array for printing */
    int *toArray(ArrayDeque *deque, int *queSize) {
        *queSize = deque->queSize;
        int *res = (int *)calloc(deque->queSize, sizeof(int));
        int j = deque->front;
        for (int i = 0; i < deque->queSize; i++) {
            res[i] = deque->nums[j % deque->queCapacity];
            j++;
        }
        return res;
    }

array_deque.kt

    /* Constructor */
    class ArrayDeque(capacity: Int) {
        private var nums: IntArray = IntArray(capacity) // Array for storing double-ended queue elements
        private var front: Int = 0 // Front pointer, points to the front of the queue element
        private var queSize: Int = 0 // Double-ended queue length

        /* Get the capacity of the double-ended queue */
        fun capacity(): Int {
            return nums.size
        }

        /* Get the length of the double-ended queue */
        fun size(): Int {
            return queSize
        }

        /* Check if the double-ended queue is empty */
        fun isEmpty(): Boolean {
            return queSize == 0
        }

        /* Calculate circular array index */
        private fun index(i: Int): Int {
            // Use modulo operation to wrap the array head and tail together
            // When i passes the tail of the array, return to the head
            // When i passes the head of the array, return to the tail
            return (i + capacity()) % capacity()
        }

        /* Front of the queue enqueue */
        fun pushFirst(num: Int) {
            if (queSize == capacity()) {
                println("Double-ended queue is full")
                return
            }
            // Use modulo operation to wrap front around to the tail after passing the head of the array
            // Add num to the front of the queue
            front = index(front - 1)
            // Add num to front of queue
            nums[front] = num
            queSize++
        }

        /* Rear of the queue enqueue */
        fun pushLast(num: Int) {
            if (queSize == capacity()) {
                println("Double-ended queue is full")
                return
            }
            // Use modulo operation to wrap rear around to the head after passing the tail of the array
            val rear = index(front + queSize)
            // Front pointer moves one position backward
            nums[rear] = num
            queSize++
        }

        /* Rear of the queue dequeue */
        fun popFirst(): Int {
            val num = peekFirst()
            // Move front pointer backward by one position
            front = index(front + 1)
            queSize--
            return num
        }

        /* Access rear of the queue element */
        fun popLast(): Int {
            val num = peekLast()
            queSize--
            return num
        }

        /* Return list for printing */
        fun peekFirst(): Int {
            if (isEmpty()) throw IndexOutOfBoundsException()
            return nums[front]
        }

        /* Driver Code */
        fun peekLast(): Int {
            if (isEmpty()) throw IndexOutOfBoundsException()
            // Initialize double-ended queue
            val last = index(front + queSize - 1)
            return nums[last]
        }

        /* Return array for printing */
        fun toArray(): IntArray {
            // Elements enqueue
            val res = IntArray(queSize)
            var i = 0
            var j = front
            while (i < queSize) {
                res[i] = nums[index(j)]
                i++
                j++
            }
            return res
        }
    }

array_deque.rb

    ### Deque based on circular array ###
    class ArrayDeque
      ### Get deque length ###
      attr_reader :size

      ### Constructor ###
      def initialize(capacity)
        @nums = Array.new(capacity, 0)
        @front = 0
        @size = 0
      end

      ### Get deque capacity ###
      def capacity
        @nums.length
      end

      ### Check if deque is empty ###
      def is_empty?
        size.zero?
      end

      ### Enqueue at front ###
      def push_first(num)
        if size == capacity
          puts 'Double-ended queue is full'
          return
        end

        # Use modulo operation to wrap front around to the tail after passing the head of the array
        # Add num to the front of the queue
        @front = index(@front - 1)
        # Add num to front of queue
        @nums[@front] = num
        @size += 1
      end

      ### Enqueue at rear ###
      def push_last(num)
        if size == capacity
          puts 'Double-ended queue is full'
          return
        end

        # Use modulo operation to wrap rear around to the head after passing the tail of the array
        rear = index(@front + size)
        # Front pointer moves one position backward
        @nums[rear] = num
        @size += 1
      end

      ### Dequeue from front ###
      def pop_first
        num = peek_first
        # Move front pointer backward by one position
        @front = index(@front + 1)
        @size -= 1
        num
      end

      ### Dequeue from rear ###
      def pop_last
        num = peek_last
        @size -= 1
        num
      end

      ### Access front element ###
      def peek_first
        raise IndexError, 'Deque is empty' if is_empty?

        @nums[@front]
      end

      ### Access rear element ###
      def peek_last
        raise IndexError, 'Deque is empty' if is_empty?

        # Initialize double-ended queue
        last = index(@front + size - 1)
        @nums[last]
      end

      ### Return array for printing ###
      def to_array
        # Elements enqueue
        res = []
        for i in 0...size
          res << @nums[index(@front + i)]
        end
        res
      end

      private

      ### Calculate circular array index ###
      def index(i)
        # Use modulo operation to wrap the array head and tail together
        # When i passes the tail of the array, return to the head
        # When i passes the head of the array, return to the tail
        (i + capacity) % capacity
      end
    end

## 5.3.3 Deque Applications

A deque combines the logic of both stacks and queues. Therefore, it can implement all application scenarios of both, while providing greater flexibility.

We know that the "undo" function in software is typically implemented using a stack: the system pushes each change operation onto the stack and then implements undo through pop. However, considering system resource limitations, software usually limits the number of undo steps (for example, only allowing 50 steps to be saved). When the stack length exceeds 50, the software needs to perform a deletion operation at the bottom of the stack (front of the queue). But a stack cannot implement this functionality, so a deque is needed to replace the stack. Note that the core logic of "undo" still follows the LIFO principle of a stack; it's just that the deque can more flexibly implement some additional logic.

##### Feel free to drop your insights, questions or suggestions