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 pop = 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 や走査のメソッドがないため、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)
        # キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
        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);
        // キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
        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);
        // キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
        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);
        // キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
        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)
        // キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
        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);
        // キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
        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);
        // キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
        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);
    // キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
    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);
            }
            // キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
            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);
    // キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
    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)
        // キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
        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)

    # キューが空の場合、先頭と末尾の両方がこのノードを指すようにする
    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  # キューの先頭要素を指す先頭ポインタ
        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()
        # 先頭ポインタを後ろに 1 つ移動し、末尾を越えたら配列の先頭に戻す
        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;       // キューの先頭要素を指す先頭ポインタ
    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();
        // 先頭ポインタを後ろに 1 つ移動し、末尾を越えたら配列の先頭に戻す
        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;
    }
};