Deque Class ใน C# - คิวสองด้าน (Double-Ended Queue)

ใน .NET Framework ไม่มีคลาส Deque<T> ตัวจริง (จนถึง .NET 8) แต่สามารถใช้ LinkedList<T> ซึ่งเป็น Doubly-Linked List ทำหน้าที่เป็น Deque ได้เต็มที่

ทำไม LinkedList<T> จึงเป็น Deque?

• เป็น Doubly-Linked List มีโหนดชี้ไปข้างหน้าและข้างหลัง
• มี First (Front) และ Last (Back) nodes
• เพิ่ม/ลบที่ทั้งสองปลายได้ O(1)

เมธอดหลักของ LinkedList<T> (ทำหน้าที่ Deque)

ตัวอย่างการใช้งาน LinkedList<T> เป็น Deque

using System;
using System.Collections.Generic;

public class DequeDemo
{
    public static void Main()
    {
        // ใช้ LinkedList เป็น Deque
        var deque = new LinkedList();
        
        // เพิ่มที่ด้านหลัง (Back) - เช่น Queue
        deque.AddLast(10);
        deque.AddLast(20);
        deque.AddLast(30);
        Console.WriteLine("หลัง AddLast 10,20,30: " + string.Join(", ", deque));
        // 10, 20, 30
        
        // เพิ่มที่ด้านหน้า (Front) - เช่น Stack
        deque.AddFirst(5);
        deque.AddFirst(1);
        Console.WriteLine("หลัง AddFirst 5,1: " + string.Join(", ", deque));
        // 1, 5, 10, 20, 30
        
        // ดูค่าที่ปลายทั้งสอง (ไม่ลบ)
        Console.WriteLine("Front (First): " + deque.First.Value);  // 1
        Console.WriteLine("Back (Last): " + deque.Last.Value);    // 30
        
        // ลบจากด้านหน้า
        int front = deque.First.Value;
        deque.RemoveFirst();
        Console.WriteLine("RemoveFirst: " + front); // 1
        Console.WriteLine("ตอนนี้: " + string.Join(", ", deque));
        // 5, 10, 20, 30
        
        // ลบจากด้านหลัง
        int back = deque.Last.Value;
        deque.RemoveLast();
        Console.WriteLine("RemoveLast: " + back); // 30
        Console.WriteLine("ตอนนี้: " + string.Join(", ", deque));
        // 5, 10, 20
        
        // ตรวจสอบค่า
        Console.WriteLine("Contains 10: " + deque.Contains(10)); // True
        Console.WriteLine("Contains 99: " + deque.Contains(99)); // False
        
        // แปลงเป็น Array
        int[] array = deque.ToArray();
        Console.WriteLine("ToArray: " + string.Join(", ", array));
    }
}

ผลลัพธ์

หลัง AddLast 10,20,30: 10, 20, 30
หลัง AddFirst 5,1: 1, 5, 10, 20, 30
Front (First): 1
Back (Last): 30
RemoveFirst: 1
ตอนนี้: 5, 10, 20, 30
RemoveLast: 30
ตอนนี้: 5, 10, 20
Contains 10: True
Contains 99: False
ToArray: 5, 10, 20

การ Implement Deque เอง (Custom Deque)

หากต้องการ Deque แบบ Array-based (Circular Buffer) สำหรับประสิทธิภาพหน่วยความจำดีกว่า:

public class ArrayDeque
{
    private T[] _array;
    private int _head = 0;
    private int _tail = 0;
    private int _count = 0;
    
    public ArrayDeque(int capacity = 8)
    {
        _array = new T[capacity];
    }
    
    public void AddFirst(T item)
    {
        if (_count == _array.Length) Resize();
        _head = (_head - 1 + _array.Length) % _array.Length;
        _array[_head] = item;
        _count++;
    }
    
    public void AddLast(T item)
    {
        if (_count == _array.Length) Resize();
        _array[_tail] = item;
        _tail = (_tail + 1) % _array.Length;
        _count++;
    }
    
    public T RemoveFirst()
    {
        if (_count == 0) throw new InvalidOperationException("Deque is empty");
        T item = _array[_head];
        _array[_head] = default;
        _head = (_head + 1) % _array.Length;
        _count--;
        return item;
    }
    
    public T RemoveLast()
    {
        if (_count == 0) throw new InvalidOperationException("Deque is empty");
        _tail = (_tail - 1 + _array.Length) % _array.Length;
        T item = _array[_tail];
        _array[_tail] = default;
        _count--;
        return item;
    }
    
    private void Resize()
    {
        var newArray = new T[_array.Length * 2];
        // คัดลอกข้อมูล...
    }
    
    public int Count => _count;
}

กรณีการใช้งาน (Use Cases)

• Sliding Window algorithms - เพิ่ม/ลบปลายทั้งสอง
• Palindrome checking - เปรียบเทียบหน้า-หลัง
• Browser History - Back/Forward navigation
• Undo/Redo - เพิ่มท้าย ลบหัว/ท้าย
• Work Stealing Queue - ใน Parallel Programming

สรุป

• Deque = Double-Ended Queue (เพิ่ม/ลบ ทั้งหน้าและหลังได้)
• ใน .NET ใช้ LinkedList<T> แทน (มี First/Last, AddFirst/Last, RemoveFirst/Last)
• Time Complexity: O(1) สำหรับการเพิ่ม/ลบที่ปลาย
• มีเมธอด: Clear, Contains, ToArray, Synchronized
• เหมาะสำหรับ Sliding Window, Undo/Redo, Browser History