کالکشن ها در جاوا: معرفی و استفاده از صف دوطرفه (Deque) + مثال

معرفی صف دوطرفه

در مورد صف (Queue) گفتیم یک ساختار داده یک طرفه است، اولین عنصری که به صف اضافه می کنیم، اولین عنصری هست که میتونیم صدا یا حذف کنیم.

در صف دو طرفه شرایط از هر دو طرف برقراره یعنی میتونیم یک عنصر رو به ابتدا یا انتهای صف اضافه کنیم یا از ابتدا یا انتهای صف حذف کنیم.

استفاده از صف دوطرفه (Deque)

اینترفیس Deque برای حذف و اضافه کردن عناصر در دو طرف صف طراحی شده و مخفف double ended queue است؛ اینترفیس Deque از اینترفیس Queue ارث بری می کنه و کلاس های LinkedList و ArrayDeque اینترفیس Deque رو پیاده سازی میکنن.

از Deque علاوه بر امکان حذف و اضافه کردن دوطرفه عنصر ها، میتونیم به عنوان Queue و به عنوان Stack استفاده کنیم.

در نمودار UML زیر متد های تعریف شده برای Deque با توضیحاتشون آورده شده است.

در مطلب LinkedList از addFirst, addLast, removeFirst و removeLast صحبت کردیم در واقع این متد ها از Deque بازنویسی شده اند اما برای اینکه بتونیم ويژگی های LinkedList رو بررسی کنیم اونجا معرفیشون کردیم.

در این بخش میخوایم از Deque استفاده کنیم، دوتا از پیاده‌سازی های اینترفیس Deque کلاس های LinkedList و ArrayDeque هستند در قبل به کلاس LinkedList پرداختیم و در مطلب بعدی به ArrayDeque خواهیم پرداخت.

در مثال زیر میخوایم با استفاده از Deque بررسی کنیم ببینیم یک کلمه Palindrome است یا خیر.

public static void main(String[] args) {

    System.out.println("Is moon palindrome? " + isPalindrome("moon"));
    System.out.println("Is noon palindrome? " + isPalindrome("noon"));
    System.out.println("Is keep palindrome? " + isPalindrome("keep"));
    System.out.println("Is peep palindrome? " + isPalindrome("peep"));
    System.out.println("Is pip palindrome? " + isPalindrome("pip"));

}

private static boolean isPalindrome(String s){

    Deque<Character> deque = new LinkedList<>();
    for (int i=0; i < s.length(); i++)
        deque.add(s.charAt(i));

    while (!deque.isEmpty() && deque.size() != 1) {

        if (!deque.getFirst().equals(deque.getLast())) return false;

        deque.removeFirst();
        deque.removeLast();
    }

    return true; 
}
        

Queue<String> queue = new LinkedList<>();

queue.offer("Tehran");
queue.offer("Arak");
queue.offer("Isfahan");
queue.offer("Tabriz");
queue.offer("Mashhad");

System.out.println("Displaying cities in queue: ");

while(!queue.isEmpty())
   System.out.print(queue.poll() + " ");

System.out.println();
        
        

Deque<String> stack = new LinkedList<>();

stack.push("Tehran");
stack.push("Arak");
stack.push("Isfahan");
stack.push("Tabriz");
stack.push("Mashhad");

System.out.println("Displaying queue: ");

while(!stack.isEmpty())
   System.out.print(queue.pop() + " ");

System.out.println();
        

بررسی پیچیدگی زمان صف دوطرفه (Deque)

در جدول زیر پیچیدگی زمان (Time Complexity) متد های صف دوطرفه (Deque) آورده شده است.

خلاصه

• از Deque برای حذف و اضافه کردن عناصر در هر دو طرف صف استفاده میکنم.
• پیچیدگی زمان حذف، اضافه و صدا زدن عناصر در دو طرف صف O(1) است.
• کلاس های LinkedList و ArrayDeque اینترفیس Deque رو پیاده سازی میکنن.
• از Deque میتونیم به عنوان Queue یا Stack استفاده کنیم.