5.2   Очередь¶

from collections import deque

# Инициализация очереди
# В Python обычно используют двустороннюю очередь deque как обычную очередь
# Хотя queue.Queue() является "чистой" очередью, она не слишком удобна, поэтому ее не рекомендуют
que: deque[int] = deque()

# Поместить элементы в очередь
que.append(1)
que.append(3)
que.append(2)
que.append(5)
que.append(4)

# Просмотреть элемент в голове очереди
front: int = que[0]

# Извлечь элемент из очереди
pop: int = que.popleft()

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

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

/* Инициализация очереди */
queue<int> queue;

/* Поместить элементы в очередь */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);

/* Просмотреть элемент в голове очереди */
int front = queue.front();

/* Извлечь элемент из очереди */
queue.pop();

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

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

/* Инициализация очереди */
Queue<Integer> queue = new LinkedList<>();

/* Поместить элементы в очередь */
queue.offer(1);
queue.offer(3);
queue.offer(2);
queue.offer(5);
queue.offer(4);

/* Просмотреть элемент в голове очереди */
int peek = queue.peek();

/* Извлечь элемент из очереди */
int pop = queue.poll();

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

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

/* Инициализация очереди */
Queue<int> queue = new();

/* Поместить элементы в очередь */
queue.Enqueue(1);
queue.Enqueue(3);
queue.Enqueue(2);
queue.Enqueue(5);
queue.Enqueue(4);

/* Просмотреть элемент в голове очереди */
int peek = queue.Peek();

/* Извлечь элемент из очереди */
int pop = queue.Dequeue();

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

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

/* Инициализация очереди */
// В Go очередь обычно реализуют через list
queue := list.New()

/* Поместить элементы в очередь */
queue.PushBack(1)
queue.PushBack(3)
queue.PushBack(2)
queue.PushBack(5)
queue.PushBack(4)

/* Просмотреть элемент в голове очереди */
peek := queue.Front()

/* Извлечь элемент из очереди */
pop := queue.Front()
queue.Remove(pop)

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

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

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

/* Поместить элементы в очередь */
queue.append(1)
queue.append(3)
queue.append(2)
queue.append(5)
queue.append(4)

/* Просмотреть элемент в голове очереди */
let peek = queue.first!

/* Извлечь элемент из очереди */
// Поскольку в основе лежит массив, removeFirst имеет сложность O(n)
let pool = queue.removeFirst()

/* Получить длину очереди */
let size = queue.count

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

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

/* Поместить элементы в очередь */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);

/* Просмотреть элемент в голове очереди */
const peek = queue[0];

/* Извлечь элемент из очереди */
// В основе лежит массив, поэтому shift() имеет сложность O(n)
const pop = queue.shift();

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

/* Проверить, пуста ли очередь */
const empty = queue.length === 0;

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

/* Поместить элементы в очередь */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);

/* Просмотреть элемент в голове очереди */
const peek = queue[0];

/* Извлечь элемент из очереди */
// В основе лежит массив, поэтому shift() имеет сложность O(n)
const pop = queue.shift();

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

/* Проверить, пуста ли очередь */
const empty = queue.length === 0;

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

/* Поместить элементы в очередь */
queue.add(1);
queue.add(3);
queue.add(2);
queue.add(5);
queue.add(4);

/* Просмотреть элемент в голове очереди */
int peek = queue.first;

/* Извлечь элемент из очереди */
int pop = queue.removeFirst();

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

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

/* Инициализация двусторонней очереди */
// В Rust двусторонняя очередь может использоваться как обычная очередь
let mut deque: VecDeque<u32> = VecDeque::new();

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

/* Просмотреть элемент в голове очереди */
if let Some(front) = deque.front() {
}

/* Извлечь элемент из очереди */
if let Some(pop) = deque.pop_front() {
}

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

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

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

/* Инициализация очереди */
val queue = LinkedList<Int>()

/* Поместить элементы в очередь */
queue.offer(1)
queue.offer(3)
queue.offer(2)
queue.offer(5)
queue.offer(4)

/* Просмотреть элемент в голове очереди */
val peek = queue.peek()

/* Извлечь элемент из очереди */
val pop = queue.poll()

/* Получить длину очереди */
val size = queue.size

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

# Инициализация очереди
# Встроенная очередь в Ruby (Thread::Queue) не имеет методов peek и traverse, поэтому можно использовать Array как очередь
queue = []

# Поместить элементы в очередь
queue.push(1)
queue.push(3)
queue.push(2)
queue.push(5)
queue.push(4)

# Просмотреть элемент очереди
peek = queue.first

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

# Получить длину очереди
size = queue.length

# Проверить, пуста ли очередь
is_empty = queue.empty?

class LinkedListQueue:
    """Очередь на основе связного списка"""

    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):
        """Поместить в очередь"""
        # Добавить num после хвостового узла
        node = ListNode(num)
        # Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
        if self._front is None:
            self._front = node
            self._rear = node
        # Если очередь не пуста, добавить этот узел после хвостового узла
        else:
            self._rear.next = node
            self._rear = node
        self._size += 1

    def pop(self) -> int:
        """Извлечь из очереди"""
        num = self.peek()
        # Удалить головной узел
        self._front = self._front.next
        self._size -= 1
        return num

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

    def to_list(self) -> list[int]:
        """Преобразовать в список для вывода"""
        queue = []
        temp = self._front
        while temp:
            queue.append(temp.val)
            temp = temp.next
        return queue

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

  public:
    LinkedListQueue() {
        front = nullptr;
        rear = nullptr;
        queSize = 0;
    }

    ~LinkedListQueue() {
        // Обходить связный список, удалять узлы и освобождать память
        freeMemoryLinkedList(front);
    }

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

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

    /* Поместить в очередь */
    void push(int num) {
        // Добавить num после хвостового узла
        ListNode *node = new ListNode(num);
        // Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
        if (front == nullptr) {
            front = node;
            rear = node;
        }
        // Если очередь не пуста, добавить этот узел после хвостового узла
        else {
            rear->next = node;
            rear = node;
        }
        queSize++;
    }

    /* Извлечь из очереди */
    int pop() {
        int num = peek();
        // Удалить головной узел
        ListNode *tmp = front;
        front = front->next;
        // Освободить память
        delete tmp;
        queSize--;
        return num;
    }

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

    /* Преобразовать связный список в Vector и вернуть */
    vector<int> toVector() {
        ListNode *node = front;
        vector<int> res(size());
        for (int i = 0; i < res.size(); i++) {
            res[i] = node->val;
            node = node->next;
        }
        return res;
    }
};

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

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

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

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

    /* Поместить в очередь */
    public void push(int num) {
        // Добавить num после хвостового узла
        ListNode node = new ListNode(num);
        // Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
        if (front == null) {
            front = node;
            rear = node;
        // Если очередь не пуста, добавить этот узел после хвостового узла
        } else {
            rear.next = node;
            rear = node;
        }
        queSize++;
    }

    /* Извлечь из очереди */
    public int pop() {
        int num = peek();
        // Удалить головной узел
        front = front.next;
        queSize--;
        return num;
    }

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

    /* Преобразовать связный список в Array и вернуть */
    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 LinkedListQueue {
    ListNode? front, rear;  // Головной узел front, хвостовой узел rear
    int queSize = 0;

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

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

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

    /* Поместить в очередь */
    public void Push(int num) {
        // Добавить num после хвостового узла
        ListNode node = new(num);
        // Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
        if (front == null) {
            front = node;
            rear = node;
            // Если очередь не пуста, добавить этот узел после хвостового узла
        } else if (rear != null) {
            rear.next = node;
            rear = node;
        }
        queSize++;
    }

    /* Извлечь из очереди */
    public int Pop() {
        int num = Peek();
        // Удалить головной узел
        front = front?.next;
        queSize--;
        return num;
    }

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

    /* Преобразовать связный список в Array и вернуть */
    public int[] ToArray() {
        if (front == null)
            return [];

        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 linkedListQueue struct {
    // Использовать встроенный пакет list для реализации очереди
    data *list.List
}

/* Инициализация очереди */
func newLinkedListQueue() *linkedListQueue {
    return &linkedListQueue{
        data: list.New(),
    }
}

/* Поместить в очередь */
func (s *linkedListQueue) push(value any) {
    s.data.PushBack(value)
}

/* Извлечь из очереди */
func (s *linkedListQueue) pop() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Front()
    s.data.Remove(e)
    return e.Value
}

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

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

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

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

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

    init() {
        _size = 0
    }

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

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

    /* Поместить в очередь */
    func push(num: Int) {
        // Добавить num после хвостового узла
        let node = ListNode(x: num)
        // Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
        if front == nil {
            front = node
            rear = node
        }
        // Если очередь не пуста, добавить этот узел после хвостового узла
        else {
            rear?.next = node
            rear = node
        }
        _size += 1
    }

    /* Извлечь из очереди */
    @discardableResult
    func pop() -> Int {
        let num = peek()
        // Удалить головной узел
        front = front?.next
        _size -= 1
        return num
    }

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

    /* Преобразовать связный список в Array и вернуть */
    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 LinkedListQueue {
    #front; // Головной узел #front
    #rear; // Хвостовой узел #rear
    #queSize = 0;

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

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

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

    /* Поместить в очередь */
    push(num) {
        // Добавить num после хвостового узла
        const node = new ListNode(num);
        // Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
        if (!this.#front) {
            this.#front = node;
            this.#rear = node;
            // Если очередь не пуста, добавить этот узел после хвостового узла
        } else {
            this.#rear.next = node;
            this.#rear = node;
        }
        this.#queSize++;
    }

    /* Извлечь из очереди */
    pop() {
        const num = this.peek();
        // Удалить головной узел
        this.#front = this.#front.next;
        this.#queSize--;
        return num;
    }

    /* Доступ к элементу в начале очереди */
    peek() {
        if (this.size === 0) throw new Error('очередь пуста');
        return this.#front.val;
    }

    /* Преобразовать связный список в Array и вернуть */
    toArray() {
        let node = this.#front;
        const res = new Array(this.size);
        for (let i = 0; i < res.length; i++) {
            res[i] = node.val;
            node = node.next;
        }
        return res;
    }
}

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

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

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

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

    /* Поместить в очередь */
    push(num: number): void {
        // Добавить num после хвостового узла
        const node = new ListNode(num);
        // Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
        if (!this.front) {
            this.front = node;
            this.rear = node;
            // Если очередь не пуста, добавить этот узел после хвостового узла
        } else {
            this.rear!.next = node;
            this.rear = node;
        }
        this.queSize++;
    }

    /* Извлечь из очереди */
    pop(): number {
        const num = this.peek();
        if (!this.front) throw new Error('очередь пуста');
        // Удалить головной узел
        this.front = this.front.next;
        this.queSize--;
        return num;
    }

    /* Доступ к элементу в начале очереди */
    peek(): number {
        if (this.size === 0) throw new Error('очередь пуста');
        return this.front!.val;
    }

    /* Преобразовать связный список в Array и вернуть */
    toArray(): number[] {
        let node = this.front;
        const res = new Array<number>(this.size);
        for (let i = 0; i < res.length; i++) {
            res[i] = node!.val;
            node = node!.next;
        }
        return res;
    }
}

/* Очередь на основе связного списка */
class LinkedListQueue {
  ListNode? _front; // Головной узел _front
  ListNode? _rear; // Хвостовой узел _rear
  int _queSize = 0; // Длина очереди

  LinkedListQueue() {
    _front = null;
    _rear = null;
  }

  /* Получение длины очереди */
  int size() {
    return _queSize;
  }

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

  /* Поместить в очередь */
  void push(int _num) {
    // Добавить _num после хвостового узла
    final node = ListNode(_num);
    // Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
    if (_front == null) {
      _front = node;
      _rear = node;
    } else {
      // Если очередь не пуста, добавить этот узел после хвостового узла
      _rear!.next = node;
      _rear = node;
    }
    _queSize++;
  }

  /* Извлечь из очереди */
  int pop() {
    final int _num = peek();
    // Удалить головной узел
    _front = _front!.next;
    _queSize--;
    return _num;
  }

  /* Доступ к элементу в начале очереди */
  int peek() {
    if (_queSize == 0) {
      throw Exception('очередь пуста');
    }
    return _front!.val;
  }

  /* Преобразовать связный список в Array и вернуть */
  List<int> toArray() {
    ListNode? node = _front;
    final List<int> queue = [];
    while (node != null) {
      queue.add(node.val);
      node = node.next;
    }
    return queue;
  }
}

/* Очередь на основе связного списка */
#[allow(dead_code)]
pub struct LinkedListQueue<T> {
    front: Option<Rc<RefCell<ListNode<T>>>>, // Головной узел front
    rear: Option<Rc<RefCell<ListNode<T>>>>,  // Хвостовой узел rear
    que_size: usize,                         // Длина очереди
}

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

    /* Получение длины очереди */
    pub fn size(&self) -> usize {
        return self.que_size;
    }

    /* Проверка, пуста ли очередь */
    pub fn is_empty(&self) -> bool {
        return self.que_size == 0;
    }

    /* Поместить в очередь */
    pub fn push(&mut self, num: T) {
        // Добавить num после хвостового узла
        let new_rear = ListNode::new(num);
        match self.rear.take() {
            // Если очередь не пуста, добавить этот узел после хвостового узла
            Some(old_rear) => {
                old_rear.borrow_mut().next = Some(new_rear.clone());
                self.rear = Some(new_rear);
            }
            // Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
            None => {
                self.front = Some(new_rear.clone());
                self.rear = Some(new_rear);
            }
        }
        self.que_size += 1;
    }

    /* Извлечь из очереди */
    pub fn pop(&mut self) -> Option<T> {
        self.front.take().map(|old_front| {
            match old_front.borrow_mut().next.take() {
                Some(new_front) => {
                    self.front = Some(new_front);
                }
                None => {
                    self.rear.take();
                }
            }
            self.que_size -= 1;
            old_front.borrow().val
        })
    }

    /* Доступ к элементу в начале очереди */
    pub fn peek(&self) -> Option<&Rc<RefCell<ListNode<T>>>> {
        self.front.as_ref()
    }

    /* Преобразовать связный список в Array и вернуть */
    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
    }
}

/* Очередь на основе связного списка */
typedef struct {
    ListNode *front, *rear;
    int queSize;
} LinkedListQueue;

/* Конструктор */
LinkedListQueue *newLinkedListQueue() {
    LinkedListQueue *queue = (LinkedListQueue *)malloc(sizeof(LinkedListQueue));
    queue->front = NULL;
    queue->rear = NULL;
    queue->queSize = 0;
    return queue;
}

/* Деструктор */
void delLinkedListQueue(LinkedListQueue *queue) {
    // Освободить все узлы
    while (queue->front != NULL) {
        ListNode *tmp = queue->front;
        queue->front = queue->front->next;
        free(tmp);
    }
    // Освободить структуру queue
    free(queue);
}

/* Получение длины очереди */
int size(LinkedListQueue *queue) {
    return queue->queSize;
}

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

/* Поместить в очередь */
void push(LinkedListQueue *queue, int num) {
    // Добавить node в хвост
    ListNode *node = newListNode(num);
    // Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
    if (queue->front == NULL) {
        queue->front = node;
        queue->rear = node;
    }
    // Если очередь не пуста, добавить этот узел после хвостового узла
    else {
        queue->rear->next = node;
        queue->rear = node;
    }
    queue->queSize++;
}

/* Доступ к элементу в начале очереди */
int peek(LinkedListQueue *queue) {
    assert(size(queue) && queue->front);
    return queue->front->val;
}

/* Извлечь из очереди */
int pop(LinkedListQueue *queue) {
    int num = peek(queue);
    ListNode *tmp = queue->front;
    queue->front = queue->front->next;
    free(tmp);
    queue->queSize--;
    return num;
}

/* Вывести очередь */
void printLinkedListQueue(LinkedListQueue *queue) {
    int *arr = malloc(sizeof(int) * queue->queSize);
    // Скопировать данные связного списка в массив
    int i;
    ListNode *node;
    for (i = 0, node = queue->front; i < queue->queSize; i++) {
        arr[i] = node->val;
        node = node->next;
    }
    printArray(arr, queue->queSize);
    free(arr);
}

/* Очередь на основе связного списка */
class LinkedListQueue(
    // Головной узел front, хвостовой узел rear
    private var front: ListNode? = null,
    private var rear: ListNode? = null,
    private var queSize: Int = 0
) {

    /* Получение длины очереди */
    fun size(): Int {
        return queSize
    }

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

    /* Поместить в очередь */
    fun push(num: Int) {
        // Добавить num после хвостового узла
        val node = ListNode(num)
        // Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
        if (front == null) {
            front = node
            rear = node
            // Если очередь не пуста, добавить этот узел после хвостового узла
        } else {
            rear?.next = node
            rear = node
        }
        queSize++
    }

    /* Извлечь из очереди */
    fun pop(): Int {
        val num = peek()
        // Удалить головной узел
        front = front?.next
        queSize--
        return num
    }

    /* Доступ к элементу в начале очереди */
    fun peek(): Int {
        if (isEmpty()) throw IndexOutOfBoundsException()
        return front!!._val
    }

    /* Преобразовать связный список в Array и вернуть */
    fun toArray(): IntArray {
        var node = front
        val res = IntArray(size())
        for (i in res.indices) {
            res[i] = node!!._val
            node = node.next
        }
        return res
    }
}

### Очередь на основе связного списка ###
class LinkedListQueue
  ### Получение длины очереди ###
  attr_reader :size

  ### Конструктор ###
  def initialize
    @front = nil  # Головной узел front
    @rear = nil   # Хвостовой узел rear
    @size = 0
  end

  ### Проверка, пуста ли очередь ###
  def is_empty?
    @front.nil?
  end

  ### Добавление в очередь ###
  def push(num)
    # Добавить num после хвостового узла
    node = ListNode.new(num)

    # Если очередь пуста, сделать так, чтобы и head, и tail указывали на этот узел
    if @front.nil?
      @front = node
      @rear = node
    # Если очередь не пуста, добавить этот узел после хвостового узла
    else
      @rear.next = node
      @rear = node
    end

    @size += 1
  end

  ### Извлечение из очереди ###
  def pop
    num = peek
    # Удалить головной узел
    @front = @front.next
    @size -= 1
    num
  end

  ### Доступ к элементу в начале очереди ###
  def peek
    raise IndexError, 'очередь пуста' if is_empty?

    @front.val
  end

  ### Преобразовать связный список в Array и вернуть ###
  def to_array
    queue = []
    temp = @front
    while temp
      queue << temp.val
      temp = temp.next
    end
    queue
  end
end

class ArrayQueue:
    """Очередь на основе кольцевого массива"""

    def __init__(self, size: int):
        """Конструктор"""
        self._nums: list[int] = [0] * size  # Массив для хранения элементов очереди
        self._front: int = 0  # Указатель head, указывающий на первый элемент очереди
        self._size: int = 0  # Длина очереди

    def capacity(self) -> int:
        """Получить вместимость очереди"""
        return len(self._nums)

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

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

    def push(self, num: int):
        """Поместить в очередь"""
        if self._size == self.capacity():
            raise IndexError("очередь заполнена")
        # Вычислить указатель хвоста, указывающий на индекс хвоста + 1
        # С помощью операции взятия по модулю вернуть rear к началу после выхода за конец массива
        rear: int = (self._front + self._size) % self.capacity()
        # Добавить num в хвост очереди
        self._nums[rear] = num
        self._size += 1

    def pop(self) -> int:
        """Извлечь из очереди"""
        num: int = self.peek()
        # Указатель head сдвигается на одну позицию назад; если он выходит за конец, то возвращается в начало массива
        self._front = (self._front + 1) % self.capacity()
        self._size -= 1
        return num

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

    def to_list(self) -> list[int]:
        """Вернуть список для вывода"""
        res = [0] * self.size()
        j: int = self._front
        for i in range(self.size()):
            res[i] = self._nums[(j % self.capacity())]
            j += 1
        return res

/* Очередь на основе кольцевого массива */
class ArrayQueue {
  private:
    int *nums;       // Массив для хранения элементов очереди
    int front;       // Указатель head, указывающий на первый элемент очереди
    int queSize;     // Длина очереди
    int queCapacity; // Вместимость очереди

  public:
    ArrayQueue(int capacity) {
        // Инициализация массива
        nums = new int[capacity];
        queCapacity = capacity;
        front = queSize = 0;
    }

    ~ArrayQueue() {
        delete[] nums;
    }

    /* Получить вместимость очереди */
    int capacity() {
        return queCapacity;
    }

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

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

    /* Поместить в очередь */
    void push(int num) {
        if (queSize == queCapacity) {
            cout << "Очередь заполнена" << endl;
            return;
        }
        // Вычислить указатель хвоста, указывающий на индекс хвоста + 1
        // С помощью операции взятия по модулю вернуть rear к началу после выхода за конец массива
        int rear = (front + queSize) % queCapacity;
        // Добавить num в хвост очереди
        nums[rear] = num;
        queSize++;
    }

    /* Извлечь из очереди */
    int pop() {
        int num = peek();
        // Указатель head сдвигается на одну позицию назад; если он выходит за конец, то возвращается в начало массива
        front = (front + 1) % queCapacity;
        queSize--;
        return num;
    }

    /* Доступ к элементу в начале очереди */
    int peek() {
        if (isEmpty())
            throw out_of_range("очередь пуста");
        return nums[front];
    }

    /* Преобразовать массив в Vector и вернуть */
    vector<int> toVector() {
        // Преобразовывать только элементы списка в пределах фактической длины
        vector<int> arr(queSize);
        for (int i = 0, j = front; i < queSize; i++, j++) {
            arr[i] = nums[j % queCapacity];
        }
        return arr;
    }
};