5.3   Двусторонняя очередь¶

from collections import deque

# Инициализация двусторонней очереди
deq: deque[int] = deque()

# Поместить элементы в очередь
deq.append(2)      # Добавить в хвост
deq.append(5)
deq.append(4)
deq.appendleft(3)  # Добавить в голову
deq.appendleft(1)

# Просмотреть элементы
front: int = deq[0]  # Элемент в голове
rear: int = deq[-1]  # Элемент в хвосте

# Извлечь элементы из очереди
pop_front: int = deq.popleft()  # Извлечь элемент из головы
pop_rear: int = deq.pop()       # Извлечь элемент из хвоста

# Получить длину двусторонней очереди
size: int = len(deq)

# Проверить, пуста ли двусторонняя очередь
is_empty: bool = len(deq) == 0

/* Инициализация двусторонней очереди */
deque<int> deque;

/* Поместить элементы в очередь */
deque.push_back(2);   // Добавить в хвост
deque.push_back(5);
deque.push_back(4);
deque.push_front(3);  // Добавить в голову
deque.push_front(1);

/* Просмотреть элементы */
int front = deque.front(); // Элемент в голове
int back = deque.back();   // Элемент в хвосте

/* Извлечь элементы из очереди */
deque.pop_front();  // Извлечь элемент из головы
deque.pop_back();   // Извлечь элемент из хвоста

/* Получить длину двусторонней очереди */
int size = deque.size();

/* Проверить, пуста ли двусторонняя очередь */
bool empty = deque.empty();

/* Инициализация двусторонней очереди */
Deque<Integer> deque = new LinkedList<>();

/* Поместить элементы в очередь */
deque.offerLast(2);   // Добавить в хвост
deque.offerLast(5);
deque.offerLast(4);
deque.offerFirst(3);  // Добавить в голову
deque.offerFirst(1);

/* Просмотреть элементы */
int peekFirst = deque.peekFirst();  // Элемент в голове
int peekLast = deque.peekLast();    // Элемент в хвосте

/* Извлечь элементы из очереди */
int popFirst = deque.pollFirst();  // Извлечь элемент из головы
int popLast = deque.pollLast();    // Извлечь элемент из хвоста

/* Получить длину двусторонней очереди */
int size = deque.size();

/* Проверить, пуста ли двусторонняя очередь */
boolean isEmpty = deque.isEmpty();

/* Инициализация двусторонней очереди */
// В C# двустороннюю очередь обычно моделируют через связный список LinkedList
LinkedList<int> deque = new();

/* Поместить элементы в очередь */
deque.AddLast(2);   // Добавить в хвост
deque.AddLast(5);
deque.AddLast(4);
deque.AddFirst(3);  // Добавить в голову
deque.AddFirst(1);

/* Просмотреть элементы */
int peekFirst = deque.First.Value;  // Элемент в голове
int peekLast = deque.Last.Value;    // Элемент в хвосте

/* Извлечь элементы из очереди */
deque.RemoveFirst();  // Извлечь элемент из головы
deque.RemoveLast();   // Извлечь элемент из хвоста

/* Получить длину двусторонней очереди */
int size = deque.Count;

/* Проверить, пуста ли двусторонняя очередь */
bool isEmpty = deque.Count == 0;

/* Инициализация двусторонней очереди */
// В Go list обычно используется как двусторонняя очередь
deque := list.New()

/* Поместить элементы в очередь */
deque.PushBack(2)      // Добавить в хвост
deque.PushBack(5)
deque.PushBack(4)
deque.PushFront(3)     // Добавить в голову
deque.PushFront(1)

/* Просмотреть элементы */
front := deque.Front() // Элемент в голове
rear := deque.Back()   // Элемент в хвосте

/* Извлечь элементы из очереди */
deque.Remove(front)    // Извлечь элемент из головы
deque.Remove(rear)     // Извлечь элемент из хвоста

/* Получить длину двусторонней очереди */
size := deque.Len()

/* Проверить, пуста ли двусторонняя очередь */
isEmpty := deque.Len() == 0

/* Инициализация двусторонней очереди */
// В Swift нет встроенного класса двусторонней очереди, поэтому можно использовать Array как двустороннюю очередь
var deque: [Int] = []

/* Поместить элементы в очередь */
deque.append(2) // Добавить в хвост
deque.append(5)
deque.append(4)
deque.insert(3, at: 0) // Добавить в голову
deque.insert(1, at: 0)

/* Просмотреть элементы */
let peekFirst = deque.first! // Элемент в голове
let peekLast = deque.last! // Элемент в хвосте

/* Извлечь элементы из очереди */
// При моделировании через Array сложность popFirst равна O(n)
let popFirst = deque.removeFirst() // Извлечь элемент из головы
let popLast = deque.removeLast() // Извлечь элемент из хвоста

/* Получить длину двусторонней очереди */
let size = deque.count

/* Проверить, пуста ли двусторонняя очередь */
let isEmpty = deque.isEmpty

/* Инициализация двусторонней очереди */
// В JavaScript нет встроенной двусторонней очереди, поэтому можно использовать Array как двустороннюю очередь
const deque = [];

/* Поместить элементы в очередь */
deque.push(2);
deque.push(5);
deque.push(4);
// Обрати внимание: поскольку это массив, метод unshift() имеет сложность O(n)
deque.unshift(3);
deque.unshift(1);

/* Просмотреть элементы */
const peekFirst = deque[0];
const peekLast = deque[deque.length - 1];

/* Извлечь элементы из очереди */
// Обрати внимание: поскольку это массив, метод shift() имеет сложность O(n)
const popFront = deque.shift();
const popBack = deque.pop();

/* Получить длину двусторонней очереди */
const size = deque.length;

/* Проверить, пуста ли двусторонняя очередь */
const isEmpty = size === 0;

/* Инициализация двусторонней очереди */
// В TypeScript нет встроенной двусторонней очереди, поэтому можно использовать Array как двустороннюю очередь
const deque: number[] = [];

/* Поместить элементы в очередь */
deque.push(2);
deque.push(5);
deque.push(4);
// Обрати внимание: поскольку это массив, метод unshift() имеет сложность O(n)
deque.unshift(3);
deque.unshift(1);

/* Просмотреть элементы */
const peekFirst: number = deque[0];
const peekLast: number = deque[deque.length - 1];

/* Извлечь элементы из очереди */
// Обрати внимание: поскольку это массив, метод shift() имеет сложность O(n)
const popFront: number = deque.shift() as number;
const popBack: number = deque.pop() as number;

/* Получить длину двусторонней очереди */
const size: number = deque.length;

/* Проверить, пуста ли двусторонняя очередь */
const isEmpty: boolean = size === 0;

/* Инициализация двусторонней очереди */
// В Dart Queue определена как двусторонняя очередь
Queue<int> deque = Queue<int>();

/* Поместить элементы в очередь */
deque.addLast(2);  // Добавить в хвост
deque.addLast(5);
deque.addLast(4);
deque.addFirst(3); // Добавить в голову
deque.addFirst(1);

/* Просмотреть элементы */
int peekFirst = deque.first; // Элемент в голове
int peekLast = deque.last;   // Элемент в хвосте

/* Извлечь элементы из очереди */
int popFirst = deque.removeFirst(); // Извлечь элемент из головы
int popLast = deque.removeLast();   // Извлечь элемент из хвоста

/* Получить длину двусторонней очереди */
int size = deque.length;

/* Проверить, пуста ли двусторонняя очередь */
bool isEmpty = deque.isEmpty;

/* Инициализация двусторонней очереди */
let mut deque: VecDeque<u32> = VecDeque::new();

/* Поместить элементы в очередь */
deque.push_back(2);  // Добавить в хвост
deque.push_back(5);
deque.push_back(4);
deque.push_front(3); // Добавить в голову
deque.push_front(1);

/* Просмотреть элементы */
if let Some(front) = deque.front() { // Элемент в голове
}
if let Some(rear) = deque.back() {   // Элемент в хвосте
}

/* Извлечь элементы из очереди */
if let Some(pop_front) = deque.pop_front() { // Извлечь элемент из головы
}
if let Some(pop_rear) = deque.pop_back() {   // Извлечь элемент из хвоста
}

/* Получить длину двусторонней очереди */
let size = deque.len();

/* Проверить, пуста ли двусторонняя очередь */
let is_empty = deque.is_empty();

// В C нет встроенной двусторонней очереди

/* Инициализация двусторонней очереди */
val deque = LinkedList<Int>()

/* Поместить элементы в очередь */
deque.offerLast(2)  // Добавить в хвост
deque.offerLast(5)
deque.offerLast(4)
deque.offerFirst(3) // Добавить в голову
deque.offerFirst(1)

/* Просмотреть элементы */
val peekFirst = deque.peekFirst() // Элемент в голове
val peekLast = deque.peekLast()   // Элемент в хвосте

/* Извлечь элементы из очереди */
val popFirst = deque.pollFirst() // Извлечь элемент из головы
val popLast = deque.pollLast()   // Извлечь элемент из хвоста

/* Получить длину двусторонней очереди */
val size = deque.size

/* Проверить, пуста ли двусторонняя очередь */
val isEmpty = deque.isEmpty()

# Инициализация двусторонней очереди
# В Ruby нет встроенной двусторонней очереди, поэтому можно использовать Array как двустороннюю очередь
deque = []

# Поместить элементы в очередь
deque << 2
deque << 5
deque << 4
# Обрати внимание: поскольку это массив, метод Array#unshift имеет сложность O(n)
deque.unshift(3)
deque.unshift(1)

# Просмотреть элементы
peek_first = deque.first
peek_last = deque.last

# Извлечь элементы из очереди
# Обрати внимание: поскольку это массив, метод Array#shift имеет сложность O(n)
pop_front = deque.shift
pop_back = deque.pop

# Получить длину двусторонней очереди
size = deque.length

# Проверить, пуста ли двусторонняя очередь
is_empty = size.zero?

class ListNode:
    """Узел двусвязного списка"""

    def __init__(self, val: int):
        """Конструктор"""
        self.val: int = val
        self.next: ListNode | None = None  # Ссылка на узел-преемник
        self.prev: ListNode | None = None  # Ссылка на узел-предшественник

class LinkedListDeque:
    """Двусторонняя очередь на основе двусвязного списка"""

    def __init__(self):
        """Конструктор"""
        self._front: ListNode | None = None  # Головной узел front
        self._rear: ListNode | None = None  # Хвостовой узел rear
        self._size: int = 0  # Длина двусторонней очереди

    def size(self) -> int:
        """Получение длины двусторонней очереди"""
        return self._size

    def is_empty(self) -> bool:
        """Проверка, пуста ли двусторонняя очередь"""
        return self._size == 0

    def push(self, num: int, is_front: bool):
        """Операция добавления в очередь"""
        node = ListNode(num)
        # Если связный список пуст, сделать так, чтобы и front, и rear указывали на node
        if self.is_empty():
            self._front = self._rear = node
        # Операция добавления в голову очереди
        elif is_front:
            # Добавить node в голову списка
            self._front.prev = node
            node.next = self._front
            self._front = node  # Обновить головной узел
        # Операция добавления в хвост очереди
        else:
            # Добавить node в хвост списка
            self._rear.next = node
            node.prev = self._rear
            self._rear = node  # Обновить хвостовой узел
        self._size += 1  # Обновить длину очереди

    def push_first(self, num: int):
        """Добавление в голову очереди"""
        self.push(num, True)

    def push_last(self, num: int):
        """Добавление в хвост очереди"""
        self.push(num, False)

    def pop(self, is_front: bool) -> int:
        """Операция извлечения из очереди"""
        if self.is_empty():
            raise IndexError("двусторонняя очередь пуста")
        # Операция извлечения из головы очереди
        if is_front:
            val: int = self._front.val  # Временно сохранить значение головного узла
            # Удалить головной узел
            fnext: ListNode | None = self._front.next
            if fnext is not None:
                fnext.prev = None
                self._front.next = None
            self._front = fnext  # Обновить головной узел
        # Операция извлечения из хвоста очереди
        else:
            val: int = self._rear.val  # Временно сохранить значение хвостового узла
            # Удалить хвостовой узел
            rprev: ListNode | None = self._rear.prev
            if rprev is not None:
                rprev.next = None
                self._rear.prev = None
            self._rear = rprev  # Обновить хвостовой узел
        self._size -= 1  # Обновить длину очереди
        return val

    def pop_first(self) -> int:
        """Извлечение из головы очереди"""
        return self.pop(True)

    def pop_last(self) -> int:
        """Извлечение из хвоста очереди"""
        return self.pop(False)

    def peek_first(self) -> int:
        """Доступ к элементу в начале очереди"""
        if self.is_empty():
            raise IndexError("двусторонняя очередь пуста")
        return self._front.val

    def peek_last(self) -> int:
        """Доступ к элементу в конце очереди"""
        if self.is_empty():
            raise IndexError("двусторонняя очередь пуста")
        return self._rear.val

    def to_array(self) -> list[int]:
        """Вернуть массив для вывода"""
        node = self._front
        res = [0] * self.size()
        for i in range(self.size()):
            res[i] = node.val
            node = node.next
        return res

/* Узел двусвязного списка */
struct DoublyListNode {
    int val;              // Значение узла
    DoublyListNode *next; // Указатель на узел-преемник
    DoublyListNode *prev; // Указатель на узел-предшественник
    DoublyListNode(int val) : val(val), prev(nullptr), next(nullptr) {
    }
};

/* Двусторонняя очередь на основе двусвязного списка */
class LinkedListDeque {
  private:
    DoublyListNode *front, *rear; // Головной узел front, хвостовой узел rear
    int queSize = 0;              // Длина двусторонней очереди

  public:
    /* Конструктор */
    LinkedListDeque() : front(nullptr), rear(nullptr) {
    }

    /* Метод-деструктор */
    ~LinkedListDeque() {
        // Обходить связный список, удалять узлы и освобождать память
        DoublyListNode *pre, *cur = front;
        while (cur != nullptr) {
            pre = cur;
            cur = cur->next;
            delete pre;
        }
    }

    /* Получение длины двусторонней очереди */
    int size() {
        return queSize;
    }

    /* Проверка, пуста ли двусторонняя очередь */
    bool isEmpty() {
        return size() == 0;
    }

    /* Операция добавления в очередь */
    void push(int num, bool isFront) {
        DoublyListNode *node = new DoublyListNode(num);
        // Если связный список пуст, сделать так, чтобы и front, и rear указывали на node
        if (isEmpty())
            front = rear = node;
        // Операция добавления в голову очереди
        else if (isFront) {
            // Добавить node в голову списка
            front->prev = node;
            node->next = front;
            front = node; // Обновить головной узел
        // Операция добавления в хвост очереди
        } else {
            // Добавить node в хвост списка
            rear->next = node;
            node->prev = rear;
            rear = node; // Обновить хвостовой узел
        }
        queSize++; // Обновить длину очереди
    }

    /* Добавление в голову очереди */
    void pushFirst(int num) {
        push(num, true);
    }

    /* Добавление в хвост очереди */
    void pushLast(int num) {
        push(num, false);
    }

    /* Операция извлечения из очереди */
    int pop(bool isFront) {
        if (isEmpty())
            throw out_of_range("очередь пуста");
        int val;
        // Операция извлечения из головы очереди
        if (isFront) {
            val = front->val; // Временно сохранить значение головного узла
            // Удалить головной узел
            DoublyListNode *fNext = front->next;
            if (fNext != nullptr) {
                fNext->prev = nullptr;
                front->next = nullptr;
            }
            delete front;
            front = fNext; // Обновить головной узел
        // Операция извлечения из хвоста очереди
        } else {
            val = rear->val; // Временно сохранить значение хвостового узла
            // Удалить хвостовой узел
            DoublyListNode *rPrev = rear->prev;
            if (rPrev != nullptr) {
                rPrev->next = nullptr;
                rear->prev = nullptr;
            }
            delete rear;
            rear = rPrev; // Обновить хвостовой узел
        }
        queSize--; // Обновить длину очереди
        return val;
    }

    /* Извлечение из головы очереди */
    int popFirst() {
        return pop(true);
    }

    /* Извлечение из хвоста очереди */
    int popLast() {
        return pop(false);
    }

    /* Доступ к элементу в начале очереди */
    int peekFirst() {
        if (isEmpty())
            throw out_of_range("двусторонняя очередь пуста");
        return front->val;
    }

    /* Доступ к элементу в конце очереди */
    int peekLast() {
        if (isEmpty())
            throw out_of_range("двусторонняя очередь пуста");
        return rear->val;
    }

    /* Вернуть массив для вывода */
    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;
    }
};

/* Узел двусвязного списка */
class ListNode {
    int val; // Значение узла
    ListNode next; // Ссылка на узел-преемник
    ListNode prev; // Ссылка на узел-предшественник

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

/* Двусторонняя очередь на основе двусвязного списка */
class LinkedListDeque {
    private ListNode front, rear; // Головной узел front, хвостовой узел rear
    private int queSize = 0; // Длина двусторонней очереди

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

    /* Получение длины двусторонней очереди */
    public int size() {
        return queSize;
    }

    /* Проверка, пуста ли двусторонняя очередь */
    public boolean isEmpty() {
        return size() == 0;
    }

    /* Операция добавления в очередь */
    private void push(int num, boolean isFront) {
        ListNode node = new ListNode(num);
        // Если связный список пуст, сделать так, чтобы и front, и rear указывали на node
        if (isEmpty())
            front = rear = node;
        // Операция добавления в голову очереди
        else if (isFront) {
            // Добавить node в голову списка
            front.prev = node;
            node.next = front;
            front = node; // Обновить головной узел
        // Операция добавления в хвост очереди
        } else {
            // Добавить node в хвост списка
            rear.next = node;
            node.prev = rear;
            rear = node; // Обновить хвостовой узел
        }
        queSize++; // Обновить длину очереди
    }

    /* Добавление в голову очереди */
    public void pushFirst(int num) {
        push(num, true);
    }

    /* Добавление в хвост очереди */
    public void pushLast(int num) {
        push(num, false);
    }

    /* Операция извлечения из очереди */
    private int pop(boolean isFront) {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        int val;
        // Операция извлечения из головы очереди
        if (isFront) {
            val = front.val; // Временно сохранить значение головного узла
            // Удалить головной узел
            ListNode fNext = front.next;
            if (fNext != null) {
                fNext.prev = null;
                front.next = null;
            }
            front = fNext; // Обновить головной узел
        // Операция извлечения из хвоста очереди
        } else {
            val = rear.val; // Временно сохранить значение хвостового узла
            // Удалить хвостовой узел
            ListNode rPrev = rear.prev;
            if (rPrev != null) {
                rPrev.next = null;
                rear.prev = null;
            }
            rear = rPrev; // Обновить хвостовой узел
        }
        queSize--; // Обновить длину очереди
        return val;
    }

    /* Извлечение из головы очереди */
    public int popFirst() {
        return pop(true);
    }

    /* Извлечение из хвоста очереди */
    public int popLast() {
        return pop(false);
    }

    /* Доступ к элементу в начале очереди */
    public int peekFirst() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return front.val;
    }

    /* Доступ к элементу в конце очереди */
    public int peekLast() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return rear.val;
    }

    /* Вернуть массив для вывода */
    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;
    }
}

/* Узел двусвязного списка */
class ListNode(int val) {
    public int val = val;       // Значение узла
    public ListNode? next = null; // Ссылка на узел-преемник
    public ListNode? prev = null; // Ссылка на узел-предшественник
}

/* Двусторонняя очередь на основе двусвязного списка */
class LinkedListDeque {
    ListNode? front, rear; // Головной узел front, хвостовой узел rear
    int queSize = 0;      // Длина двусторонней очереди

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

    /* Получение длины двусторонней очереди */
    public int Size() {
        return queSize;
    }

    /* Проверка, пуста ли двусторонняя очередь */
    public bool IsEmpty() {
        return Size() == 0;
    }

    /* Операция добавления в очередь */
    void Push(int num, bool isFront) {
        ListNode node = new(num);
        // Если связный список пуст, сделать так, чтобы и front, и rear указывали на node
        if (IsEmpty()) {
            front = node;
            rear = node;
        }
        // Операция добавления в голову очереди
        else if (isFront) {
            // Добавить node в голову списка
            front!.prev = node;
            node.next = front;
            front = node; // Обновить головной узел
        }
        // Операция добавления в хвост очереди
        else {
            // Добавить node в хвост списка
            rear!.next = node;
            node.prev = rear;
            rear = node;  // Обновить хвостовой узел
        }

        queSize++; // Обновить длину очереди
    }

    /* Добавление в голову очереди */
    public void PushFirst(int num) {
        Push(num, true);
    }

    /* Добавление в хвост очереди */
    public void PushLast(int num) {
        Push(num, false);
    }

    /* Операция извлечения из очереди */
    int? Pop(bool isFront) {
        if (IsEmpty())
            throw new Exception();
        int? val;
        // Операция извлечения из головы очереди
        if (isFront) {
            val = front?.val; // Временно сохранить значение головного узла
            // Удалить головной узел
            ListNode? fNext = front?.next;
            if (fNext != null) {
                fNext.prev = null;
                front!.next = null;
            }
            front = fNext;   // Обновить головной узел
        }
        // Операция извлечения из хвоста очереди
        else {
            val = rear?.val;  // Временно сохранить значение хвостового узла
            // Удалить хвостовой узел
            ListNode? rPrev = rear?.prev;
            if (rPrev != null) {
                rPrev.next = null;
                rear!.prev = null;
            }
            rear = rPrev;    // Обновить хвостовой узел
        }

        queSize--; // Обновить длину очереди
        return val;
    }

    /* Извлечение из головы очереди */
    public int? PopFirst() {
        return Pop(true);
    }

    /* Извлечение из хвоста очереди */
    public int? PopLast() {
        return Pop(false);
    }

    /* Доступ к элементу в начале очереди */
    public int? PeekFirst() {
        if (IsEmpty())
            throw new Exception();
        return front?.val;
    }

    /* Доступ к элементу в конце очереди */
    public int? PeekLast() {
        if (IsEmpty())
            throw new Exception();
        return rear?.val;
    }

    /* Вернуть массив для вывода */
    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;
    }
}

/* Двусторонняя очередь на основе двусвязного списка */
type linkedListDeque struct {
    // Использовать встроенный пакет list
    data *list.List
}

/* Инициализировать двустороннюю очередь */
func newLinkedListDeque() *linkedListDeque {
    return &linkedListDeque{
        data: list.New(),
    }
}

/* Поместить элемент в голову очереди */
func (s *linkedListDeque) pushFirst(value any) {
    s.data.PushFront(value)
}

/* Поместить элемент в хвост очереди */
func (s *linkedListDeque) pushLast(value any) {
    s.data.PushBack(value)
}

/* Извлечь элемент из головы очереди */
func (s *linkedListDeque) popFirst() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Front()
    s.data.Remove(e)
    return e.Value
}

/* Извлечь элемент из хвоста очереди */
func (s *linkedListDeque) popLast() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Back()
    s.data.Remove(e)
    return e.Value
}

/* Доступ к элементу в начале очереди */
func (s *linkedListDeque) peekFirst() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Front()
    return e.Value
}

/* Доступ к элементу в конце очереди */
func (s *linkedListDeque) peekLast() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Back()
    return e.Value
}

/* Получение длины очереди */
func (s *linkedListDeque) size() int {
    return s.data.Len()
}

/* Проверка, пуста ли очередь */
func (s *linkedListDeque) isEmpty() bool {
    return s.data.Len() == 0
}

/* Получить List для вывода */
func (s *linkedListDeque) toList() *list.List {
    return s.data
}

/* Узел двусвязного списка */
class ListNode {
    var val: Int // Значение узла
    var next: ListNode? // Ссылка на узел-преемник
    weak var prev: ListNode? // Ссылка на узел-предшественник

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

/* Двусторонняя очередь на основе двусвязного списка */
class LinkedListDeque {
    private var front: ListNode? // Головной узел front
    private var rear: ListNode? // Хвостовой узел rear
    private var _size: Int // Длина двусторонней очереди

    init() {
        _size = 0
    }

    /* Получение длины двусторонней очереди */
    func size() -> Int {
        _size
    }

    /* Проверка, пуста ли двусторонняя очередь */
    func isEmpty() -> Bool {
        size() == 0
    }

    /* Операция добавления в очередь */
    private func push(num: Int, isFront: Bool) {
        let node = ListNode(val: num)
        // Если связный список пуст, сделать так, чтобы и front, и rear указывали на node
        if isEmpty() {
            front = node
            rear = node
        }
        // Операция добавления в голову очереди
        else if isFront {
            // Добавить node в голову списка
            front?.prev = node
            node.next = front
            front = node // Обновить головной узел
        }
        // Операция добавления в хвост очереди
        else {
            // Добавить node в хвост списка
            rear?.next = node
            node.prev = rear
            rear = node // Обновить хвостовой узел
        }
        _size += 1 // Обновить длину очереди
    }

    /* Добавление в голову очереди */
    func pushFirst(num: Int) {
        push(num: num, isFront: true)
    }

    /* Добавление в хвост очереди */
    func pushLast(num: Int) {
        push(num: num, isFront: false)
    }

    /* Операция извлечения из очереди */
    private func pop(isFront: Bool) -> Int {
        if isEmpty() {
            fatalError("двусторонняя очередь пуста")
        }
        let val: Int
        // Операция извлечения из головы очереди
        if isFront {
            val = front!.val // Временно сохранить значение головного узла
            // Удалить головной узел
            let fNext = front?.next
            if fNext != nil {
                fNext?.prev = nil
                front?.next = nil
            }
            front = fNext // Обновить головной узел
        }
        // Операция извлечения из хвоста очереди
        else {
            val = rear!.val // Временно сохранить значение хвостового узла
            // Удалить хвостовой узел
            let rPrev = rear?.prev
            if rPrev != nil {
                rPrev?.next = nil
                rear?.prev = nil
            }
            rear = rPrev // Обновить хвостовой узел
        }
        _size -= 1 // Обновить длину очереди
        return val
    }

    /* Извлечение из головы очереди */
    func popFirst() -> Int {
        pop(isFront: true)
    }

    /* Извлечение из хвоста очереди */
    func popLast() -> Int {
        pop(isFront: false)
    }

    /* Доступ к элементу в начале очереди */
    func peekFirst() -> Int {
        if isEmpty() {
            fatalError("двусторонняя очередь пуста")
        }
        return front!.val
    }

    /* Доступ к элементу в конце очереди */
    func peekLast() -> Int {
        if isEmpty() {
            fatalError("двусторонняя очередь пуста")
        }
        return rear!.val
    }

    /* Вернуть массив для вывода */
    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
    }
}

/* Узел двусвязного списка */
class ListNode {
    prev; // Ссылка на узел-предшественник (указатель)
    next; // Ссылка на узел-преемник (указатель)
    val; // Значение узла

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

/* Двусторонняя очередь на основе двусвязного списка */
class LinkedListDeque {
    #front; // Головной узел front
    #rear; // Хвостовой узел rear
    #queSize; // Длина двусторонней очереди

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

    /* Операция добавления в хвост очереди */
    pushLast(val) {
        const node = new ListNode(val);
        // Если связный список пуст, сделать так, чтобы и front, и rear указывали на node
        if (this.#queSize === 0) {
            this.#front = node;
            this.#rear = node;
        } else {
            // Добавить node в хвост списка
            this.#rear.next = node;
            node.prev = this.#rear;
            this.#rear = node; // Обновить хвостовой узел
        }
        this.#queSize++;
    }

    /* Операция добавления в голову очереди */
    pushFirst(val) {
        const node = new ListNode(val);
        // Если связный список пуст, сделать так, чтобы и front, и rear указывали на node
        if (this.#queSize === 0) {
            this.#front = node;
            this.#rear = node;
        } else {
            // Добавить node в голову списка
            this.#front.prev = node;
            node.next = this.#front;
            this.#front = node; // Обновить головной узел
        }
        this.#queSize++;
    }

    /* Операция извлечения из хвоста очереди */
    popLast() {
        if (this.#queSize === 0) {
            return null;
        }
        const value = this.#rear.val; // Сохранить значение хвостового узла
        // Удалить хвостовой узел
        let temp = this.#rear.prev;
        if (temp !== null) {
            temp.next = null;
            this.#rear.prev = null;
        }
        this.#rear = temp; // Обновить хвостовой узел
        this.#queSize--;
        return value;
    }

    /* Операция извлечения из головы очереди */
    popFirst() {
        if (this.#queSize === 0) {
            return null;
        }
        const value = this.#front.val; // Сохранить значение хвостового узла
        // Удалить головной узел
        let temp = this.#front.next;
        if (temp !== null) {
            temp.prev = null;
            this.#front.next = null;
        }
        this.#front = temp; // Обновить головной узел
        this.#queSize--;
        return value;
    }

    /* Доступ к элементу в конце очереди */
    peekLast() {
        return this.#queSize === 0 ? null : this.#rear.val;
    }

    /* Доступ к элементу в начале очереди */
    peekFirst() {
        return this.#queSize === 0 ? null : this.#front.val;
    }

    /* Получение длины двусторонней очереди */
    size() {
        return this.#queSize;
    }

    /* Проверка, пуста ли двусторонняя очередь */
    isEmpty() {
        return this.#queSize === 0;
    }

    /* Вывести двустороннюю очередь */
    print() {
        const arr = [];
        let temp = this.#front;
        while (temp !== null) {
            arr.push(temp.val);
            temp = temp.next;
        }
        console.log('[' + arr.join(', ') + ']');
    }
}

/* Узел двусвязного списка */
class ListNode {
    prev: ListNode; // Ссылка на узел-предшественник (указатель)
    next: ListNode; // Ссылка на узел-преемник (указатель)
    val: number; // Значение узла

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

/* Двусторонняя очередь на основе двусвязного списка */
class LinkedListDeque {
    private front: ListNode; // Головной узел front
    private rear: ListNode; // Хвостовой узел rear
    private queSize: number; // Длина двусторонней очереди

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

    /* Операция добавления в хвост очереди */
    pushLast(val: number): void {
        const node: ListNode = new ListNode(val);
        // Если связный список пуст, сделать так, чтобы и front, и rear указывали на node
        if (this.queSize === 0) {
            this.front = node;
            this.rear = node;
        } else {
            // Добавить node в хвост списка
            this.rear.next = node;
            node.prev = this.rear;
            this.rear = node; // Обновить хвостовой узел
        }
        this.queSize++;
    }

    /* Операция добавления в голову очереди */
    pushFirst(val: number): void {
        const node: ListNode = new ListNode(val);
        // Если связный список пуст, сделать так, чтобы и front, и rear указывали на node
        if (this.queSize === 0) {
            this.front = node;
            this.rear = node;
        } else {
            // Добавить node в голову списка
            this.front.prev = node;
            node.next = this.front;
            this.front = node; // Обновить головной узел
        }
        this.queSize++;
    }

    /* Операция извлечения из хвоста очереди */
    popLast(): number {
        if (this.queSize === 0) {
            return null;
        }
        const value: number = this.rear.val; // Сохранить значение хвостового узла
        // Удалить хвостовой узел
        let temp: ListNode = this.rear.prev;
        if (temp !== null) {
            temp.next = null;
            this.rear.prev = null;
        }
        this.rear = temp; // Обновить хвостовой узел
        this.queSize--;
        return value;
    }

    /* Операция извлечения из головы очереди */
    popFirst(): number {
        if (this.queSize === 0) {
            return null;
        }
        const value: number = this.front.val; // Сохранить значение хвостового узла
        // Удалить головной узел
        let temp: ListNode = this.front.next;
        if (temp !== null) {
            temp.prev = null;
            this.front.next = null;
        }
        this.front = temp; // Обновить головной узел
        this.queSize--;
        return value;
    }

    /* Доступ к элементу в конце очереди */
    peekLast(): number {
        return this.queSize === 0 ? null : this.rear.val;
    }

    /* Доступ к элементу в начале очереди */
    peekFirst(): number {
        return this.queSize === 0 ? null : this.front.val;
    }

    /* Получение длины двусторонней очереди */
    size(): number {
        return this.queSize;
    }

    /* Проверка, пуста ли двусторонняя очередь */
    isEmpty(): boolean {
        return this.queSize === 0;
    }

    /* Вывести двустороннюю очередь */
    print(): void {
        const arr: number[] = [];
        let temp: ListNode = this.front;
        while (temp !== null) {
            arr.push(temp.val);
            temp = temp.next;
        }
        console.log('[' + arr.join(', ') + ']');
    }
}