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(', ') + ']');
    }
}