insertFront(x) ──▶  ┌────┬────┬────┬────┐  ◀── insertRear(x)
deleteFront()  ◀──  │ 10 │ 20 │ 30 │ 40 │  ──▶ deleteRear()
                    └────┴────┴────┴────┘
                      ↑              ↑
                    front           rear

use only the rear  →  a stack   (push = insertRear, pop = deleteRear)
rear in, front out →  a queue   (enqueue = insertRear, dequeue = deleteFront)

from collections import deque

def show(d):
    print(*d)

d = deque()
d.append(10)            # insert at the rear
d.append(20)
d.append(30)
show(d)
d.appendleft(100)       # insert at the front
show(d)
d.pop()                 # delete from the rear
show(d)
d.popleft()             # delete from the front
show(d)
print("front:", d[0], "rear:", d[-1])

#include <deque>
#include <iostream>
using namespace std;

void show(const deque<int>& d) {
    for (size_t i = 0; i < d.size(); i++) cout << (i ? " " : "") << d[i];   // deque allows d[i]
    cout << "\n";
}

int main() {
    deque<int> d;
    d.push_back(10);        // insert at the rear
    d.push_back(20);
    d.push_back(30);
    show(d);
    d.push_front(100);      // insert at the front
    show(d);
    d.pop_back();           // delete from the rear
    show(d);
    d.pop_front();          // delete from the front
    show(d);
    cout << "front: " << d.front() << " rear: " << d.back() << "\n";
}

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static void show(Deque<Integer> d) {
        StringBuilder sb = new StringBuilder();
        for (int v : d) sb.append(sb.length() == 0 ? "" : " ").append(v);
        System.out.println(sb);
    }

    public static void main(String[] args) {
        Deque<Integer> d = new ArrayDeque<>();   // preferred over LinkedList
        d.addLast(10);          // insert at the rear
        d.addLast(20);
        d.addLast(30);
        show(d);
        d.addFirst(100);        // insert at the front
        show(d);
        d.removeLast();         // delete from the rear
        show(d);
        d.removeFirst();        // delete from the front
        show(d);
        System.out.println("front: " + d.peekFirst() + " rear: " + d.peekLast());
    }
}

const show = (d) => console.log(d.join(" "));

const d = [];               // an array used as a deque
d.push(10);                 // insert at the rear
d.push(20);
d.push(30);
show(d);
d.unshift(100);             // insert at the front — O(n) on an array
show(d);
d.pop();                    // delete from the rear
show(d);
d.shift();                  // delete from the front — O(n) on an array
show(d);
console.log("front:", d[0], "rear:", d[d.length - 1]);

10 20 30
100 10 20 30
100 10 20
10 20
front: 10 rear: 20

from collections import deque

d = deque([10, 20, 30, 40])
d.insert(2, 15)
print(list(d))          # [10, 20, 15, 30, 40]
print(d.count(10))      # 1
d.remove(10)            # removes the first occurrence
print(list(d))          # [20, 15, 30, 40]
d.extend([50, 60])
print(list(d))          # [20, 15, 30, 40, 50, 60]
d.extendleft([10, 20])
print(list(d))          # [20, 10, 20, 15, 30, 40, 50, 60]   ← appendleft one by one, so the order flips
d.reverse()
print(list(d))          # [60, 50, 40, 30, 15, 20, 10, 20]

from collections import deque

d = deque([10, 20, 30, 40, 50])
d.rotate(2)             # positive: the last 2 elements move to the front
print(list(d))          # [40, 50, 10, 20, 30]
d.rotate(-2)            # negative: the first 2 elements move to the back
print(list(d))          # [10, 20, 30, 40, 50]
print(d[2])             # 30   ← indexing works, but the middle is O(n)
d[2] = 100
print(list(d))          # [10, 20, 100, 40, 50]
print(d[0], d[-1])      # 10 50

history = deque(maxlen=3)        # bounded: a full deque drops the opposite end
for x in (1, 2, 3, 4):
    history.append(x)
print(list(history))    # [2, 3, 4]   ← 1 fell off the front

collections.deque — a doubly linked list of 64-slot blocks

   leftblock               ...                 rightblock
  ┌───────────────┐    ┌───────────────┐    ┌───────────────┐
  │ · · · 10 20 30│◀──▶│ 40 50 … … 90  │◀──▶│ 100 110 · · · │
  └───────────────┘    └───────────────┘    └───────────────┘
         ↑ leftindex                             ↑ rightindex

  appendleft / popleft move leftindex   → O(1)
  append / pop move rightindex          → O(1)
  d[i] hops i // 64 blocks              → O(n) in the middle

head (front)                                        tail (rear)
 ↓                                                   ↓
┌───┬────┬───┐     ┌───┬────┬───┐     ┌───┬────┬───┐
│ ∅ │ 10 │ ●─┼────▶│ ● │ 20 │ ●─┼────▶│ ● │ 30 │ ∅ │
│   │    │   │◀────┼─● │    │   │◀────┼─● │    │   │
└───┴────┴───┘     └───┴────┴───┘     └───┴────┴───┘
prev value next

deleteRear(): tail = tail.prev; tail.next = ∅         ← O(1) thanks to prev
insertFront(x): node.next = head; head.prev = node; head = node

class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class Deque:
    def __init__(self):
        self.head = None       # front
        self.tail = None       # rear
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def insert_front(self, value):
        node = Node(value)
        if self.is_empty():
            self.head = self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node
        self.size += 1

    def insert_rear(self, value):
        node = Node(value)
        if self.is_empty():
            self.head = self.tail = node
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node
        self.size += 1

    def delete_front(self):
        if self.is_empty():
            raise IndexError("deque is empty")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:          # became empty
            self.tail = None
        else:
            self.head.prev = None
        self.size -= 1
        return value

    def delete_rear(self):
        if self.is_empty():
            raise IndexError("deque is empty")
        value = self.tail.value
        self.tail = self.tail.prev     # O(1) thanks to prev
        if self.tail is None:          # became empty
            self.head = None
        else:
            self.tail.next = None
        self.size -= 1
        return value

    def get_front(self):
        return None if self.is_empty() else self.head.value

    def get_rear(self):
        return None if self.is_empty() else self.tail.value

    def display(self):
        node, parts = self.head, []
        while node:
            parts.append(str(node.value))
            node = node.next
        print(" ".join(parts))

d = Deque()
for x in (10, 20, 30):
    d.insert_rear(x)
print("front:", d.get_front(), "rear:", d.get_rear())
d.delete_front()
print("deleteFront → front:", d.get_front(), "rear:", d.get_rear())
d.delete_rear()
print("deleteRear → front:", d.get_front(), "rear:", d.get_rear())
print("size:", d.size, "empty:", d.is_empty())
d.insert_front(100)
d.insert_front(1000)
d.display()

#include <iostream>
#include <stdexcept>
using namespace std;

struct Node {
    int value;
    Node* prev;
    Node* next;
    Node(int v) : value(v), prev(nullptr), next(nullptr) {}
};

class Deque {
    Node* head = nullptr;      // front
    Node* tail = nullptr;      // rear
    int count = 0;
public:
    ~Deque() { while (head) deleteFront(); }
    bool isEmpty() const { return count == 0; }
    int size() const { return count; }
    void insertFront(int v) {
        Node* node = new Node(v);
        if (isEmpty()) head = tail = node;
        else { node->next = head; head->prev = node; head = node; }
        count++;
    }
    void insertRear(int v) {
        Node* node = new Node(v);
        if (isEmpty()) head = tail = node;
        else { node->prev = tail; tail->next = node; tail = node; }
        count++;
    }
    int deleteFront() {
        if (isEmpty()) throw runtime_error("deque is empty");
        Node* node = head;
        int v = node->value;
        head = head->next;
        if (!head) tail = nullptr;             // became empty
        else head->prev = nullptr;
        delete node;
        count--;
        return v;
    }
    int deleteRear() {
        if (isEmpty()) throw runtime_error("deque is empty");
        Node* node = tail;
        int v = node->value;
        tail = tail->prev;                     // O(1) thanks to prev
        if (!tail) head = nullptr;             // became empty
        else tail->next = nullptr;
        delete node;
        count--;
        return v;
    }
    int getFront() const { return head->value; }
    int getRear() const { return tail->value; }
    void display() const {
        for (Node* n = head; n; n = n->next) cout << n->value << (n->next ? " " : "");
        cout << "\n";
    }
};

int main() {
    Deque d;
    for (int x : {10, 20, 30}) d.insertRear(x);
    cout << "front: " << d.getFront() << " rear: " << d.getRear() << "\n";
    d.deleteFront();
    cout << "deleteFront → front: " << d.getFront() << " rear: " << d.getRear() << "\n";
    d.deleteRear();
    cout << "deleteRear → front: " << d.getFront() << " rear: " << d.getRear() << "\n";
    cout << "size: " << d.size() << " empty: " << (d.isEmpty() ? "True" : "False") << "\n";
    d.insertFront(100);
    d.insertFront(1000);
    d.display();
}

public class Main {
    static class Node {
        int value; Node prev, next;
        Node(int v) { value = v; }
    }

    static class Deque {
        Node head, tail;           // front, rear
        int size;
        boolean isEmpty() { return size == 0; }
        void insertFront(int v) {
            Node node = new Node(v);
            if (isEmpty()) head = tail = node;
            else { node.next = head; head.prev = node; head = node; }
            size++;
        }
        void insertRear(int v) {
            Node node = new Node(v);
            if (isEmpty()) head = tail = node;
            else { node.prev = tail; tail.next = node; tail = node; }
            size++;
        }
        int deleteFront() {
            if (isEmpty()) throw new RuntimeException("deque is empty");
            int v = head.value;
            head = head.next;
            if (head == null) tail = null;         // became empty
            else head.prev = null;
            size--;
            return v;
        }
        int deleteRear() {
            if (isEmpty()) throw new RuntimeException("deque is empty");
            int v = tail.value;
            tail = tail.prev;                      // O(1) thanks to prev
            if (tail == null) head = null;         // became empty
            else tail.next = null;
            size--;
            return v;
        }
        Integer getFront() { return isEmpty() ? null : head.value; }
        Integer getRear() { return isEmpty() ? null : tail.value; }
        void display() {
            StringBuilder sb = new StringBuilder();
            for (Node n = head; n != null; n = n.next) sb.append(n.value).append(n.next != null ? " " : "");
            System.out.println(sb);
        }
    }

    public static void main(String[] args) {
        Deque d = new Deque();
        for (int x : new int[]{10, 20, 30}) d.insertRear(x);
        System.out.println("front: " + d.getFront() + " rear: " + d.getRear());
        d.deleteFront();
        System.out.println("deleteFront → front: " + d.getFront() + " rear: " + d.getRear());
        d.deleteRear();
        System.out.println("deleteRear → front: " + d.getFront() + " rear: " + d.getRear());
        System.out.println("size: " + d.size + " empty: " + (d.isEmpty() ? "True" : "False"));
        d.insertFront(100);
        d.insertFront(1000);
        d.display();
    }
}

class Node {
    constructor(value) { this.value = value; this.prev = null; this.next = null; }
}

class Deque {
    constructor() { this.head = null; this.tail = null; this.size = 0; }   // front, rear
    isEmpty() { return this.size === 0; }
    insertFront(value) {
        const node = new Node(value);
        if (this.isEmpty()) this.head = this.tail = node;
        else { node.next = this.head; this.head.prev = node; this.head = node; }
        this.size++;
    }
    insertRear(value) {
        const node = new Node(value);
        if (this.isEmpty()) this.head = this.tail = node;
        else { node.prev = this.tail; this.tail.next = node; this.tail = node; }
        this.size++;
    }
    deleteFront() {
        if (this.isEmpty()) throw new Error("deque is empty");
        const value = this.head.value;
        this.head = this.head.next;
        if (this.head === null) this.tail = null;      // became empty
        else this.head.prev = null;
        this.size--;
        return value;
    }
    deleteRear() {
        if (this.isEmpty()) throw new Error("deque is empty");
        const value = this.tail.value;
        this.tail = this.tail.prev;                    // O(1) thanks to prev
        if (this.tail === null) this.head = null;      // became empty
        else this.tail.next = null;
        this.size--;
        return value;
    }
    getFront() { return this.isEmpty() ? null : this.head.value; }
    getRear() { return this.isEmpty() ? null : this.tail.value; }
    display() {
        const parts = [];
        for (let n = this.head; n; n = n.next) parts.push(n.value);
        console.log(parts.join(" "));
    }
}

const d = new Deque();
for (const x of [10, 20, 30]) d.insertRear(x);
console.log("front:", d.getFront(), "rear:", d.getRear());
d.deleteFront();
console.log("deleteFront → front:", d.getFront(), "rear:", d.getRear());
d.deleteRear();
console.log("deleteRear → front:", d.getFront(), "rear:", d.getRear());
console.log("size:", d.size, "empty:", d.isEmpty() ? "True" : "False");
d.insertFront(100);
d.insertFront(1000);
d.display();

front: 10 rear: 30
deleteFront → front: 20 rear: 30
deleteRear → front: 20 rear: 20
size: 1 empty: False
1000 100 20

capacity 5: insertFront(10), insertFront(20), insertFront(30), insertRear(40), insertRear(50)

  index:   0     1     2     3     4
        ┌─────┬─────┬─────┬─────┬─────┐
        │ 40  │ 50  │ 30  │ 20  │ 10  │
        └─────┴─────┴─────┴─────┴─────┘
                       ↑ front = 2        rear = (front + size − 1) % 5 = 1

  insertFront moves front backwards:  0 → 4 (10) → 3 (20) → 2 (30)   wraps to the end
  insertRear fills the slot after rear: 4 → 0 (40) → 1 (50)          wraps to the start
  logical order (front → rear):  30  20  10  40  50

class ArrayDeque:
    def __init__(self, capacity):
        self.slots = [None] * capacity
        self.cap = capacity
        self.front = 0        # index of the first element
        self.size = 0         # rear index is derived: (front + size - 1) % cap

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.cap

    def insert_front(self, value):
        if self.is_full():
            raise OverflowError("deque is full")
        self.front = (self.front - 1 + self.cap) % self.cap   # step back, wrapping to the end
        self.slots[self.front] = value
        self.size += 1

    def insert_rear(self, value):
        if self.is_full():
            raise OverflowError("deque is full")
        self.slots[(self.front + self.size) % self.cap] = value   # next free slot after rear
        self.size += 1

    def delete_front(self):
        if self.is_empty():
            raise IndexError("deque is empty")
        value = self.slots[self.front]
        self.front = (self.front + 1) % self.cap
        self.size -= 1
        return value

    def delete_rear(self):
        if self.is_empty():
            raise IndexError("deque is empty")
        value = self.slots[(self.front + self.size - 1) % self.cap]
        self.size -= 1                                # rear simply moves back by one
        return value

    def get_front(self):
        return self.slots[self.front]

    def get_rear(self):
        return self.slots[(self.front + self.size - 1) % self.cap]

    def in_order(self):
        return [self.slots[(self.front + i) % self.cap] for i in range(self.size)]

d = ArrayDeque(5)
for x in (10, 20, 30):
    d.insert_front(x)
for x in (40, 50):
    d.insert_rear(x)
print("in order:", *d.in_order())
print("slots:", *d.slots)
print("front =", d.front, "size =", d.size)
print("full:", d.is_full())
print("deleteFront →", d.delete_front())
print("deleteRear →", d.delete_rear())
print("in order:", *d.in_order())
print("front:", d.get_front(), "rear:", d.get_rear())

#include <iostream>
#include <stdexcept>
#include <vector>
using namespace std;

class ArrayDeque {
public:
    vector<int> slots;
    int cap, front = 0, size = 0;    // rear index is derived: (front + size - 1) % cap
    ArrayDeque(int capacity) : slots(capacity, 0), cap(capacity) {}
    bool isEmpty() const { return size == 0; }
    bool isFull() const { return size == cap; }
    void insertFront(int v) {
        if (isFull()) throw runtime_error("deque is full");
        front = (front - 1 + cap) % cap;              // step back, wrapping to the end
        slots[front] = v;
        size++;
    }
    void insertRear(int v) {
        if (isFull()) throw runtime_error("deque is full");
        slots[(front + size) % cap] = v;              // next free slot after rear
        size++;
    }
    int deleteFront() {
        if (isEmpty()) throw runtime_error("deque is empty");
        int v = slots[front];
        front = (front + 1) % cap;
        size--;
        return v;
    }
    int deleteRear() {
        if (isEmpty()) throw runtime_error("deque is empty");
        int v = slots[(front + size - 1) % cap];
        size--;                                       // rear simply moves back by one
        return v;
    }
    int getFront() const { return slots[front]; }
    int getRear() const { return slots[(front + size - 1) % cap]; }
    void printInOrder() const {
        cout << "in order:";
        for (int i = 0; i < size; i++) cout << " " << slots[(front + i) % cap];
        cout << "\n";
    }
};

int main() {
    ArrayDeque d(5);
    for (int x : {10, 20, 30}) d.insertFront(x);
    for (int x : {40, 50}) d.insertRear(x);
    d.printInOrder();
    cout << "slots:";
    for (int v : d.slots) cout << " " << v;
    cout << "\n";
    cout << "front = " << d.front << " size = " << d.size << "\n";
    cout << "full: " << (d.isFull() ? "True" : "False") << "\n";
    cout << "deleteFront → " << d.deleteFront() << "\n";
    cout << "deleteRear → " << d.deleteRear() << "\n";
    d.printInOrder();
    cout << "front: " << d.getFront() << " rear: " << d.getRear() << "\n";
}

public class Main {
    static class ArrayDeque {
        int[] slots;
        int cap, front = 0, size = 0;    // rear index is derived: (front + size - 1) % cap
        ArrayDeque(int capacity) { slots = new int[capacity]; cap = capacity; }
        boolean isEmpty() { return size == 0; }
        boolean isFull() { return size == cap; }
        void insertFront(int v) {
            if (isFull()) throw new RuntimeException("deque is full");
            front = (front - 1 + cap) % cap;          // step back, wrapping to the end
            slots[front] = v;
            size++;
        }
        void insertRear(int v) {
            if (isFull()) throw new RuntimeException("deque is full");
            slots[(front + size) % cap] = v;          // next free slot after rear
            size++;
        }
        int deleteFront() {
            if (isEmpty()) throw new RuntimeException("deque is empty");
            int v = slots[front];
            front = (front + 1) % cap;
            size--;
            return v;
        }
        int deleteRear() {
            if (isEmpty()) throw new RuntimeException("deque is empty");
            int v = slots[(front + size - 1) % cap];
            size--;                                   // rear simply moves back by one
            return v;
        }
        int getFront() { return slots[front]; }
        int getRear() { return slots[(front + size - 1) % cap]; }
        void printInOrder() {
            StringBuilder sb = new StringBuilder("in order:");
            for (int i = 0; i < size; i++) sb.append(' ').append(slots[(front + i) % cap]);
            System.out.println(sb);
        }
    }

    public static void main(String[] args) {
        ArrayDeque d = new ArrayDeque(5);
        for (int x : new int[]{10, 20, 30}) d.insertFront(x);
        for (int x : new int[]{40, 50}) d.insertRear(x);
        d.printInOrder();
        StringBuilder sb = new StringBuilder("slots:");
        for (int v : d.slots) sb.append(' ').append(v);
        System.out.println(sb);
        System.out.println("front = " + d.front + " size = " + d.size);
        System.out.println("full: " + (d.isFull() ? "True" : "False"));
        System.out.println("deleteFront → " + d.deleteFront());
        System.out.println("deleteRear → " + d.deleteRear());
        d.printInOrder();
        System.out.println("front: " + d.getFront() + " rear: " + d.getRear());
    }
}

class ArrayDeque {
    constructor(capacity) {
        this.slots = new Array(capacity).fill(null);
        this.cap = capacity;
        this.front = 0;       // index of the first element
        this.size = 0;        // rear index is derived: (front + size - 1) % cap
    }
    isEmpty() { return this.size === 0; }
    isFull() { return this.size === this.cap; }
    insertFront(value) {
        if (this.isFull()) throw new Error("deque is full");
        this.front = (this.front - 1 + this.cap) % this.cap;   // step back, wrapping to the end
        this.slots[this.front] = value;
        this.size++;
    }
    insertRear(value) {
        if (this.isFull()) throw new Error("deque is full");
        this.slots[(this.front + this.size) % this.cap] = value;   // next free slot after rear
        this.size++;
    }
    deleteFront() {
        if (this.isEmpty()) throw new Error("deque is empty");
        const value = this.slots[this.front];
        this.front = (this.front + 1) % this.cap;
        this.size--;
        return value;
    }
    deleteRear() {
        if (this.isEmpty()) throw new Error("deque is empty");
        const value = this.slots[(this.front + this.size - 1) % this.cap];
        this.size--;                                  // rear simply moves back by one
        return value;
    }
    getFront() { return this.slots[this.front]; }
    getRear() { return this.slots[(this.front + this.size - 1) % this.cap]; }
    inOrder() {
        const out = [];
        for (let i = 0; i < this.size; i++) out.push(this.slots[(this.front + i) % this.cap]);
        return out;
    }
}

const d = new ArrayDeque(5);
for (const x of [10, 20, 30]) d.insertFront(x);
for (const x of [40, 50]) d.insertRear(x);
console.log("in order:", d.inOrder().join(" "));
console.log("slots:", d.slots.join(" "));
console.log("front =", d.front, "size =", d.size);
console.log("full:", d.isFull() ? "True" : "False");
console.log("deleteFront →", d.deleteFront());
console.log("deleteRear →", d.deleteRear());
console.log("in order:", d.inOrder().join(" "));
console.log("front:", d.getFront(), "rear:", d.getRear());

in order: 30 20 10 40 50
slots: 40 50 30 20 10
front = 2 size = 5
full: True
deleteFront → 30
deleteRear → 50
in order: 20 10 40
front: 20 rear: 40

from collections import deque

def is_palindrome(s):
    d = deque(ch.lower() for ch in s if ch.isalnum())   # ignore spaces, case, punctuation
    while len(d) > 1:
        if d.popleft() != d.pop():                        # compare both ends, O(1) each
            return False
    return True

for s in ["racecar", "Nurses run", "hello", "No lemon, no melon"]:
    print(s, "→", "Yes" if is_palindrome(s) else "No")

#include <cctype>
#include <deque>
#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(const string& s) {
    deque<char> d;
    for (char ch : s)                                         // ignore spaces, case, punctuation
        if (isalnum((unsigned char)ch)) d.push_back((char)tolower((unsigned char)ch));
    while (d.size() > 1) {
        if (d.front() != d.back()) return false;              // compare both ends, O(1) each
        d.pop_front();
        d.pop_back();
    }
    return true;
}

int main() {
    for (string s : {"racecar", "Nurses run", "hello", "No lemon, no melon"})
        cout << s << " → " << (isPalindrome(s) ? "Yes" : "No") << "\n";
}

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static boolean isPalindrome(String s) {
        Deque<Character> d = new ArrayDeque<>();
        for (char ch : s.toCharArray())                       // ignore spaces, case, punctuation
            if (Character.isLetterOrDigit(ch)) d.addLast(Character.toLowerCase(ch));
        while (d.size() > 1) {
            char a = d.pollFirst(), b = d.pollLast();         // unbox before comparing!
            if (a != b) return false;                         // compare both ends, O(1) each
        }
        return true;
    }

    public static void main(String[] args) {
        for (String s : new String[]{"racecar", "Nurses run", "hello", "No lemon, no melon"})
            System.out.println(s + " → " + (isPalindrome(s) ? "Yes" : "No"));
    }
}

function isPalindrome(s) {
    const d = [];
    for (const ch of s.toLowerCase())                         // ignore spaces, case, punctuation
        if (/[a-z0-9]/.test(ch)) d.push(ch);
    while (d.length > 1) {
        if (d.shift() !== d.pop()) return false;              // compare both ends (shift is O(n) on arrays)
    }
    return true;
}

for (const s of ["racecar", "Nurses run", "hello", "No lemon, no melon"])
    console.log(s, "→", isPalindrome(s) ? "Yes" : "No");

racecar → Yes
Nurses run → Yes
hello → No
No lemon, no melon → Yes