pushBack(10), pushBack(20), pushBack(30):
  front -> [10, 20, 30] <- back

pushFront(5):
  front -> [5, 10, 20, 30] <- back

popBack() -> 30:
  front -> [5, 10, 20] <- back

popFront() -> 5:
  front -> [10, 20] <- back

peekFront() -> 10  (no removal)
peekBack()  -> 20  (no removal)

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

class Deque {
  constructor() {
    this.head = null   // front node
    this.tail = null   // back node
    this.count = 0
  }

  // O(1) — prepend a new node before head
  pushFront(value) {
    const node = new Node(value)
    if (this.head === null) {
      this.head = node
      this.tail = node
    } else {
      node.next = this.head
      this.head.prev = node
      this.head = node
    }
    this.count++
  }

  // O(1) — append a new node after tail
  pushBack(value) {
    const node = new Node(value)
    if (this.tail === null) {
      this.head = node
      this.tail = node
    } else {
      node.prev = this.tail
      this.tail.next = node
      this.tail = node
    }
    this.count++
  }

  // O(1) — remove and return head
  popFront() {
    if (this.isEmpty()) throw new Error('Deque is empty')
    const value = this.head.value
    this.head = this.head.next
    if (this.head !== null) {
      this.head.prev = null
    } else {
      this.tail = null   // became empty
    }
    this.count--
    return value
  }

  // O(1) — remove and return tail
  popBack() {
    if (this.isEmpty()) throw new Error('Deque is empty')
    const value = this.tail.value
    this.tail = this.tail.prev
    if (this.tail !== null) {
      this.tail.next = null
    } else {
      this.head = null   // became empty
    }
    this.count--
    return value
  }

  peekFront() {
    if (this.isEmpty()) throw new Error('Deque is empty')
    return this.head.value
  }

  peekBack() {
    if (this.isEmpty()) throw new Error('Deque is empty')
    return this.tail.value
  }

  isEmpty() { return this.count === 0 }
  size()    { return this.count }

  // Print all elements front to back
  toArray() {
    const result = []
    let curr = this.head
    while (curr !== null) {
      result.push(curr.value)
      curr = curr.next
    }
    return result
  }
}

// Demo
const dq = new Deque()
dq.pushBack(10)
dq.pushBack(20)
dq.pushBack(30)
dq.pushFront(5)
dq.pushFront(1)
console.log(dq.toArray())     // [1, 5, 10, 20, 30]
console.log(dq.popFront())    // 1
console.log(dq.popBack())     // 30
console.log(dq.toArray())     // [5, 10, 20]
console.log(dq.peekFront())   // 5
console.log(dq.peekBack())    // 20

class CircularDeque {
  constructor(capacity) {
    this.capacity = capacity
    this.data = new Array(capacity)
    // front points ONE STEP ahead of the actual front element
    // so we can pushFront by decrementing front first.
    this.front = Math.floor(capacity / 2)
    this.back  = Math.floor(capacity / 2) - 1  // back is "behind" front initially
    this.count = 0
  }

  _mod(i) {
    // JavaScript's % can return negative values for negative i
    return ((i % this.capacity) + this.capacity) % this.capacity
  }

  // O(1)
  pushFront(value) {
    if (this.isFull()) throw new Error('Deque is full')
    this.front = this._mod(this.front - 1)
    this.data[this.front] = value
    this.count++
  }

  // O(1)
  pushBack(value) {
    if (this.isFull()) throw new Error('Deque is full')
    this.back = this._mod(this.back + 1)
    this.data[this.back] = value
    this.count++
  }

  // O(1)
  popFront() {
    if (this.isEmpty()) throw new Error('Deque is empty')
    const value = this.data[this.front]
    this.front = this._mod(this.front + 1)
    this.count--
    return value
  }

  // O(1)
  popBack() {
    if (this.isEmpty()) throw new Error('Deque is empty')
    const value = this.data[this.back]
    this.back = this._mod(this.back - 1)
    this.count--
    return value
  }

  peekFront() {
    if (this.isEmpty()) throw new Error('Deque is empty')
    return this.data[this.front]
  }

  peekBack() {
    if (this.isEmpty()) throw new Error('Deque is empty')
    return this.data[this.back]
  }

  isEmpty()  { return this.count === 0 }
  isFull()   { return this.count === this.capacity }
  size()     { return this.count }
}

const dq = new Deque()

// Use as a STACK (LIFO) — push and pop from same end
dq.pushBack(1)
dq.pushBack(2)
dq.pushBack(3)
dq.popBack()    // 3   <- LIFO

// Use as a QUEUE (FIFO) — push to back, pop from front
dq.pushBack('a')
dq.pushBack('b')
dq.pushBack('c')
dq.popFront()   // 'a'  <- FIFO

function slidingWindowMax(arr, k) {
  const n = arr.length
  if (n === 0 || k === 0) return []

  const result = []
  // Deque stores array INDICES, not values.
  // Invariant: arr[deque[front]] >= arr[deque[back]]  (decreasing values)
  const deque = []  // using a plain array as deque for brevity

  for (let i = 0; i < n; i++) {
    // Step 1: remove indices that have fallen outside the window
    while (deque.length > 0 && deque[0] < i - k + 1) {
      deque.shift()   // pop from front
    }

    // Step 2: remove indices from back whose values are <= arr[i]
    // They are useless — arr[i] is both newer and at least as large.
    while (deque.length > 0 && arr[deque[deque.length - 1]] <= arr[i]) {
      deque.pop()   // pop from back
    }

    // Step 3: add current index to back
    deque.push(i)

    // Step 4: once window is full, record the maximum (front of deque)
    if (i >= k - 1) {
      result.push(arr[deque[0]])
    }
  }

  return result
}

// Example
const arr = [3, 1, 2, 5, 4, 6, 3, 7]
const k = 3

console.log(slidingWindowMax(arr, k))
// Windows: [3,1,2]=3  [1,2,5]=5  [2,5,4]=5  [5,4,6]=6  [4,6,3]=6  [6,3,7]=7

Array:  [3, 1, 2, 5, 4, 6, 3, 7],  k = 3
Indices: 0  1  2  3  4  5  6  7

i=0  arr[0]=3:  deque=[]     -> push 0         -> deque=[0]       window not full yet
i=1  arr[1]=1:  arr[0]=3 > 1 -> push 1         -> deque=[0,1]     window not full yet
i=2  arr[2]=2:  arr[1]=1 <=2 -> pop 1; push 2  -> deque=[0,2]     window=[0..2] max=arr[0]=3  -> result=[3]
i=3  arr[3]=5:  arr[2]=2 <=5 -> pop 2
                arr[0]=3 <=5 -> pop 0; push 3  -> deque=[3]       window=[1..3] max=arr[3]=5  -> result=[3,5]
i=4  arr[4]=4:  arr[3]=5 > 4 -> push 4         -> deque=[3,4]     window=[2..4] max=arr[3]=5  -> result=[3,5,5]
i=5  arr[5]=6:  arr[4]=4 <=6 -> pop 4
                arr[3]=5 <=6 -> pop 3; push 5  -> deque=[5]       window=[3..5] max=arr[5]=6  -> result=[3,5,5,6]
...

function isPalindrome(str) {
  // Normalize: lowercase, keep only alphanumeric characters
  const clean = str.toLowerCase().replace(/[^a-z0-9]/g, '')

  const dq = new Deque()
  for (const ch of clean) dq.pushBack(ch)

  while (dq.size() > 1) {
    const front = dq.popFront()
    const back  = dq.popBack()
    if (front !== back) return false
  }

  return true
}

console.log(isPalindrome('racecar'))                   // true
console.log(isPalindrome('A man a plan a canal Panama')) // true
console.log(isPalindrome('hello'))                     // false
console.log(isPalindrome('Was it a car or a cat I saw'))  // true

function bfs01(graph, source, n) {
  // graph[u] = [ { to: v, weight: 0 or 1 }, ... ]
  const dist = new Array(n).fill(Infinity)
  dist[source] = 0
  const dq = new Deque()
  dq.pushFront(source)

  while (!dq.isEmpty()) {
    const u = dq.popFront()

    for (const { to: v, weight: w } of graph[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w
        if (w === 0) {
          dq.pushFront(v)   // free edge — goes to front
        } else {
          dq.pushBack(v)    // cost-1 edge — goes to back
        }
      }
    }
  }

  return dist
}

// Grid maze: 0 = free passage (cost 0), 1 = door that costs 1 to open
// Use 0-1 BFS to find minimum doors to open from top-left to bottom-right.