სტრუკტურული მონაცემები - (რიგი - Queue)

Queue-რიგი. მასზე საუბარს იმით დავიწყებთ რო მსგავსად List ინტერფეისისა ისიც Linear Data Structur-ის სიაში შედის, სტრუკტურულად ძალიან გავს სიას ერთი დიდი განსხვავებით ის არის ბაზირებული FIFO(first in first out) პრინციპზე. რიგში ალბათ სხვანაირად დგომაც შეუძლებელია. წარმოიდგინეთ დგახართ სუპერმარკეტის რიგში და კასაზე გასვლა LIFO(last in first out) პრინციპით რომ ხდებოდეს. ალოგიკურია ხო? კომპიუტერულ მეცნიერებაშიც ალოგიკურია მსგავსი რამ, მაგალითად წარმოიდგინეთ პრინტერი, სადაც აგზავნით 50 ფაილს ამოსაბეჭდად და ამობეჭდვა ბოლო დამატებული ფაილიდან რო დაიწყოს, არც ისე კომფორტული იქნება. დანამდვილებით ვერ ვიტყვი პრინტერი რომელ სტრუკტურას იყენებს, მაგრამ დიდი ვარაუდით ნებისმიერ სტრუკტურას რომელიც FIFO პრინციპებზეა აგებული.  ზოგადად Queue ყველაზე გამოყენებადი სტრუკტურაა პროგრამირებაში, რადგან არ აქვს მნიშვნელობა პროეკტს ბანკისთვის, მაღაზიისთვის, სახელმწიფოსთვის თუ უბრალოდ სოფთისთვის წერთ, ყველგან დაგჭირდებათ. მას გარდა იმისა რო FiFo პრინციპზეა აგებული აქვს უამრავი ქვე ინტერფეისი და კლასი, რომლებიც პრიორიტეტების მიხედვით ალაგებენ სიას. მაგალითისთვის წარმოიდგინეთ საავადმყოფო, სადაც ექიმთან პაციენტის მოხვედრა პრიორიტეტის მიხედვით ხდება,  ნათია რომელსაც ხელი აქვს გაკაწრული, გიორგი რომელიც ავტო კატასტროფაში მოხვდა და მაია რომელიც სკამიდან გადმოვარდა FIFO პრინციპით ვერ მოხვდებიან ექიმთან, მსგავსი ქმედება არ იქნება ლოგიკური, ნათია მიუხედავად იმისა რო პირველი მოვიდა სააავადმყოფოში პირველი ვერ წავა, იმიტომ რო გიორგის გადაუდებელი დახმარება ჭირდება. მსგავსი ოპერაციის შესასრულებლად PriorityQueue იდეალური არჩევანი იქნება, სხვა სიტუაციას თუ წარმოვიდგენთ, ალბათ ყველას გქონიათ ბანკთან შეხება, ბანკში რო შევდივართ კართან აპარატი დგას რომელიც ნომერს გვაძლევს რათა რიგში ჩავდგეთ, კასაზე გამოძახება ამის შემდგომ ხდებ, სანამ თქვენ საკასო ოპერაციას ასრულებთ რიგში ადამიანები დგანან მაგრამ კასაზე ვერ მოვლენ, რადგან კასა დაკავებულია, როცა განთავისუფლდება მხოლოდ ამის შემდგომ მიდის კასასთან ახალი მომხარებელი. მსგავსი ოპერაცია რო შესრულდეს BlockingQueue ნორმალური არჩევანი იქნება, (არსებობს მრავალი სახეობა BlockingQueue-ს) უამრავი სხვა მაგალითის მოყვანა შეიძლება, მაგრამ  ჯობია რეალურად ჩავიხედოთ Queue ფუნქიონალიზმში რათა უკეთ გავერკვეთ როგორ მუშაობს იგი.

ინფო: საკუთარი რიგის შექმნა აუცილებლობას არ წარმოადგენს რადგან ჯავას ბიბლიოთეკაში ის უკვე შექმნილია, მაგრამ უკეთ რო გაითავისოთ, ყოველთვის უკეთესია ცადოთ საკუთარის შექმნა, შეცდომებიც რომ დაუშვათ, თვეები რომც დაჭირდეს ყოველთვის უკეთესია გქონდეთ საკუთარი რო უკეთ იცოდეთ სტანდარტული.

მაშ ასე რა არის რიგი:

რიგი არის უბრალო სია სადაც პრიორიტეტული ელემენტი არის ელემენტი, რომელიც პირველი დაემატა სიას. პირველი დამატებული ელემენტი პირველი დატოვებს მას.

რიგის იმპლემენტაცია შესაძლებელია ორი სახით: სტატიკურად და დინამიურად. სტატიკური რიგი იქნება მასივზე ბაზირებული, მსგავსად ArrayList, Vector, Stack-სა List ინტერფეისიდან და დინამიურად მსგავსად LinkedList-სა. რიგზე ელემენტის დამატება შესაძლებელია მხოლოდ ერთი მიმართულებით, ელემენტი რიგში შედის ერთი მხირდან და ტოვებს მას მეორე მხრიდან, (რამოდენიმე გამონაკლისის გარდა ). ნახეთ ფოტო:

მსგავსად List ინტერფეისისა Queue-ც არის ADT(Abstract data type) რაც ნიშნავს იმას რომ, არ აქვს მნიშვნელობა რომელ ენაზე წერთ სტუკტურას. ნებისმიერ ენაში, C++, C#, java ფუნქციონალიზმი და შიგთავსი სტრუკტურის ერთი იქნება.  მისი იმპლემენტაცია კოლექციაში საინტერესოდ გამოიყურება,

სუპერ ინტერფეისები: Collection, Itarable:

ქვე ინტერფეისები : BlockingQueue, BlockDequeue, TransfareQueue, Deque.  (ამ ოთხი ინტერფეისიდან მხოლოდ  Deque ინტერფეისია java.util.*; პაკეტიდან, დანარჩენი სამი არის java.util.concurrent პაკეტიდან, რაც ნიშნავს იმას რომ კონკურენტული პაკეტიდან სტრუკტურები გამოიყენება მრავალ განშტოებიანი და კონკურენტული პროგრამირების დროს, მათზე რამოდენიმე ბლოგის შემდგომ ვისაუბრებთ)

ქვე კლასები: SynchronousQueue, DelayQueue, ArrayDeque, LinkedList, ArrayBlockingQueue, LinkedBlockingDeque, ConcurrentLinkedDeque და ა.შ

ჯერ-ჯერობით ყველაზე ნაცნობი იმპლემენტაცია  Queue ინტერფეისის არის LinkedList.

Queue ინტერფეის გააჩნია 6 მეთოდი. რეალურად ასრულებს 3 ოპერაციას. (ყველა მეთოდს “რიგში” აქვს იდენტური  ფუნქციონალიზმის მეთოდი, რომელიც ასრულებს იგივე ოპერაციას და რომელიც სრულდება სხვა შედეგით)

ოპერაციის ტიპი	ისვრის გამონაკლის	აბრუნებს ღირებულებას ან null-ს
დამატება	Add(E value)	Offer(E value)
წაშლა	Remove()	Poll()
წაკითხვა	Element()	Peek()

გამონაკლის ისვრის იმ შემთხვევაში თუ: ვერ ამატებს რიგს ელემენტს. მეხსიერება გადაივსო ან ვმუშაობთ განსაზღვრული სიდიდის მეხსიერებით. ვერ შლის რიგიდნ ელემენტს, რადგან რიგი ცარიელია, ვერ გამოაქვს ელემენტი რიგიდან რადგან რიგი ცარიელია.

ღირებულების დაბრუნების შემტხვევაში: აბრუნებს false თუ ვერ დაამატა ელემენტი რიგს. შემდეგი ორი მეთოდის შემთხვევაში აბრუნებს null-ს თუ რიგში არ იმყოფება ელემენტები.

ჯავა კონვენციის მიხედვით ელემენტის დამატების პროცეს ქვია enqueue და ელემენტის წაშლის პროცეს dequeue.

Linear Data Structur-ს, List და  Queue-ს იმიტომ ეძახიან რომ მათი მეხსიერებაში ალოკაცია ხდება ერთ რიგში, რიგი შეიძლება იყოს თანმიმდდევრული (static) arraylist, vector, stack ან მიმოფანტული, მაგრამ მაინც თანმიმდევრული, ელემენტი მიმოფანტულია მეხსირებაში ერთი თანმიმდევრობით. (dynamic) linkedlist.

ვნახოთ მაგალითი რიგის გამოყენების:

კომპილირების შემდგომ:

LinkedList-ის ამ სახით იმპლემენტაცია ართმევს მას მის საბაზისო ფუნქციონალიზმს. როგორც იცით დაკავშირებული სია ახდენსს ორივე საბაზისო ინტერფეისის (List, Queue) იმპლემენტაციას, კლასების და ინტერფეისების განხილვის დროს, ვისაუბრეთ რომ ქვე მდგომი კლასი იღებს იმ ფუნქიონალიზმს, რომელიც მის ზემდგომ კლას ან ინტერფეის გააჩნია. ანუ მეთოდები დეფინირებული ზემდგომში წვდომადია ზემდგომისთვის ქვემდგომში. სხვა შემთხვევაში კასტინგი გვიწევს. უფრო კონკრეტული თუ ვიქნებით LinkedList არ ახდენს Queue პირდაპირ იმპლემენტაციას. ის ახდენს Deque ინტერფეისის იმპლემენტაციას, რომელიც ქვე ინტერფეისია Queue სუპერ ინტერფეისის.

Deque ინტერფეის-ზე ცოტა ხანში ვისაუბრებთ.

როგორც ხედავთ რიგს აქვს 6 მეთოდი + მეთოდები რომლებიც დეფინირებულია ზემდგომ ინტერფეისებში. კოლექციასა და იტერატორში.

ვნახოთ პატარა მაგალითი დინამიური და სტატიკური ინსტანცირების მხოლოდ Queue ინტერფეისის.

დასაწყისისთვის შევქმათ ინტეფეისი 6 მეთოდით:

და მოვახდინოთ მისი იმპლემენტაცია დინამიურად.

რის შემდგომაც, დავიწყებთ მეთოდების დამუშავებას.

Add()

დაკავშირებული სიების დროს რამოდენიმე სახით მოვახერხეთ ამ მეთოდის შექმნა, ამ ჯერზე root ელემენტი მიუთითებს პირველ დამატებულ ელემენტზე და tail ელემენტი ბოლო დამატებულ ელემენტზე. აღქმა არ უნდა გაგიჭირდეთ თუ დაკავშირებული სია, ცალმხრივად მაინც გაქვთ აგებული.

Peek()

ეს ორი მეთოდი უბრალლოდ გვეტყვის რომელი ელემენტია სიაში პირველი.

Remove()

პირველი დამატებული ელემენტის წაშლა მარტივად შესაქმნელია თუ დაკავშირებული სიებიდან removeFirst() მეთოდი გაქვთ დანაწერი როდისმე.

სულ ეს არის დინამიური იმპლემენტაცია რიგის. მხოლოდ ეს მეთოდებია რიგში მაგიტომაც არ გავაკეთე სხვა მეთოდების მაგალითი. დანარჩენს მეთოდებს, ისეთებს როგორიც toArray(), size(), isEmpty(), Remove(E Value) და სხვანი რიგი მემკვიდრეობით იღებს კოლექციიდან. კოლექციაზე არ გვისაუბრია ამიტომ დავტოვოთ ისე როგორც არის. შევეცდები კოლექციაზე დეტალურად სტრუკტურული მონაცემების დასასრულისკენ ვისაუბრო, ისევე როგორც Iterator & Iterable ინტერფეისებზე.

იგივე ოპერციების განმეორება სტატიკურად გაცილებით მარტივია.  ხშირ შემთხვევაში მასივზე ბაზირებული რიგი არის განსაზღვრული სიდიდის, ამიტომ შემდგომ მაგალითზე არ გვექნება მეთოდები რომელბიც დინამიურად გაზრდიან მასივს, გადაამოწმებენ null შიგთავსზე  და ა.შ

კლასის ინსტანცირების დროს კონსტრუკტორის მხარე მოგვთხოვს სიდიდის შეყვანას.

რის შემდგომაც დავიწყებთ ელემენტების ჩასმას მასივში:

შეყვანილი ელემენტების კონტროლს მოახენს tail ცვლადი. თუ რიგში ადგილი არ არის მეთოდი დააბრუნებს False,  წინააღმდეგ შემთხვევაში დაამატებს ელემენტს.

შემდეგი ორი მეთოდი გვანახებს ელემენტს რომელმაც უნდა დატოვოს რიგი.

Root ცვლადის ღირებულება არის 0. მასივში ათვლა როგორც ვიცით იწყება 0-ან, გამომდინარე აქედან  Root ცვლადი ყოველთვის მიგვითითებს პირველ ელემენტზე რიგში.

მეთოდები რომლებიც წაშლიან პირველ ელემენტს რიგში. წაშლის შემდგომ აუცილებელია მოვახდინოთ Root ცვლადის გადაადგილება ერთით მარჯვნივნ რათა მიგვითითოს შემდეგ პირველ ელემენტზე რიგში.

ამის შემდგომ ვტესტავთ რიგს:

კომპილირების შემდგომ:

იდეალურად მუშაობს, როგორც ხედავთ, თუმცა გვაქ ერთი პრობლემა. როდესაც რიგი მუშაობს განსაზღვრული სიდიდით, root ცვლადი ყოველთვის მიგვითითებს პირველ ელემენტზე და  tail ბოლოზე. როდესაც წაშლა ხდება root-ის მხრიდან ჩვენ ელემენტს უბრალოდ ვანულებთ და ვწევთ root-ს ერთით მარჯვნივ. საჩუქრად კი ვიღებთ შემდეგ სურათს.

პირველი ელემენტი კი წავშალეთ,  მაგრამ მის ადგილას კომპილების შემდგომ გვაქ null, ვიზუალურად შეიძლება ამაზე გვერდის ავლა, მოვახდენთ კომპილირებას იმ ელემენტების რომლებიც მასივში იმყოფებიან მაგრამ ვიზუალურად პრობლემაზე გვერდის ავლა პრობლემის გადაჭრას არ ნიშნავს. ჩდება კითხვა, როგორ მივხედოთ ამ პრობლემას? ყოველ შემდეგ წაშლაზე null-ბი დაემატება მასივს.

?

წლების უკან მსგავს პრობლემას რო გადავაწყდი, გამოსავალი მარტივად მოვნახე, მეთქი ყველა არსებულ ელემენტს ჩავწევ მარცხივ და პრობლემაც მოგვარდებათქო, მაგრამ მარტივი გამოსავალი, გამოსავალი ხშირ შემთხვევაში არ არის. პროგრამირებაში სიმარტივე არ არის გენიალური. მარცხნივ ელემენტების ჩაწევას მოყვება შემდეგი პრობლემები. უნდა გადმოვწიოთ Root და  Tail ელემენტები რო მართებულ ელემენტებზე მიგვითითონ მასივში. შემთხვევით null-ზე თუ მიგვითითა, კომპილატორი ისვრის nullpoinetexception-ს, რაც არც ისე სტაბილური შედეგია, შემდეგი პრობლემა იყო სიძვირე, მსგავსი ოპერაცია მოითხოვს იტერაციას, ინტეგრირებულს ან თქვენ მიერ შექმნილს, ყოველი ელემენტის წაშლაზე იტერაცია საკმაოდ ნელს გახდის პროგრამას და ბოლო პრობლემა, იტერაციით ჩაწევის შემდგომ null ღირებულებები მოექცეოდა რიგის ბოლოში, მსგავსად arraylist და vector-სა, სადაც მეთოდი გვაქ რომელიც სიდიდეს არსებულ ელემენტების ოდენობამდე ამცირებს. trimToSize მეთოდით. ჯერ ერთი მსგავსი მეთოდი არ არსებობს რიგში, მაგრამ ისევ სიმარტივემდე მოვედით, შევქმნიდით მეთოდს რომელიც შეასრულებდე მასზე დაკისრებულ ამოცანას იდეალურად. რაც საერთო ჯამში მოგვცემს 3 იტერაციას ერთი მარტივი ოპერაციის შესარულებლად. გამომდინარე ამ ყველაფრიდან, მივედით იმ აზრამდე რო ელემენტების ჩაწევა მარცხნივ ვერ იქნება გამოსავალი.

მაშინ რაშია გამოსავალი? არსებობს რამოდენიმე ვარიანტი, ყველაზე მისაღები და მარტივად გასააზრებელი არის ცირკულაური მასივის შექმნა, მსგავსად ცირკულარული სიისა. სადაც ელემენტები განსაზღვრული სიდიდის წრეზე იმოძრავებენ.

ვნახოთ მაგალითი:

ყველა დანარჩენი მეთოდი იგივეა გარდა დამატებისა და წაშლისა. ამიტომ მხოლოდ ამ 2 მეთოდს ვნახავთ:

და წაშლა:

მთავარი რაც ამ 2 ოპერაციაშია არის tail = (tail+1)%data.length და root = (root+1)%data.length სადაც ვამბობთ: კუდი = კუდს + 1 ნაშთი ელემენტების სიდიდისგან. დაუშვათ თუ კუდი უდრის 1-ს მაშინ მისი ღირებულება გახდება 1+1 %5 რაც დაგვიბრუნებს 2-ს, შემდეგი ელემენტი დაემატება ინდექს 2-ზე. მომდევნო 3-ზე და ა.შ, მაგრამ თუ ელემენტი მივიდა მაქსიმუმ სიდიდემდე. 5 + 1 % 5 = 1 და კუდი გახდება 1, ანუ ელემენტების დამატება დაიწყება ახლიდან. წაშლაც იგივე პრინციპით. ვნახოთ როგორ მუშაობს ჩვენი რიგი:

კომპილირების შემდგომ:

დააკვირდით, რიგმა ახლიდან დაიწყო შევსება წრეზე. თუმცა რიგში პირველი ისევ ლოლა არის. არ იქნება ლოგიკური რო ახალი მოსული ძაღლი პირველი გახდეს, წრეზე კი წავიდა მაგრამ ლაილა ბოლო ძაღლია ვეტერინართან რიგში. მიუხედავად იმისა რო 0 ინდექსზე ზის. (კართან ახლოს) (ცირკულარული რიგი როგორც წესი ავტომატურად იზრდება)

იმედია პრინციპი დინამიური და სტატიკური რიგის გასაგებია. არც ისე რთულია. არც ისეთუ რთული იმპლემენტაციები აქვს და არც ისე რთულად არის შესაქმნელი როგორც List ინტერფეისის  კლასები.

Queue გამოყენების წესები:

1.     Null-ის დამატება არ შეიძლება რიგზე. ისვრის გამონაკლის.

2.     შეუძლია ექნეს დუბლირებული ელემენტები

3. განსხვავებით List ინტერფეისისა, რიგს არ აქვს “Random Access” წვდომა ელემენტებზე. ანუ არ გააჩნია get, set, insert, insertAfter index მეთოდები.

4.   90 % შემთხვევებისა, რიგის კლასები ელემენტებს იმატებენ ერთი მხრიდან და ტოვებენ მას მეორე მხრიდან, რამოდენიმე გამონაკლისი არსებობს სადაც ელემენტები ნატურალური თანმიმდევრობით შედის რიგში(მაგ: პრიორიტეტული რიგი)

რა მოხდება თუ არსებულ ძაღლებს სხვა და სხვა პრობლემები აქვთ? უბრალო რიგით ხომ ვერ მივიღებთ ყველას. მსგავსი ქმედება ჩვენი პროგრამის მიერ ალოგიკური იქნება. ჯავაში მსგავს სიტუაციებს PriorityQueue უმკლავდება. ვნახოთ როგორ გამოიყურება ეს კლასი ბიბლიოთეკაში.

მემკვიდრეობით იმფორმაციას იღებს აბსტრაკტული რიგიდან, რომელიც თავის მხრივ მემკვიდრეა და ახდენს იმპლემენტაციას აბსტრაკტული კოლექციის, რიგის, იტერატორის და სერიალიზაციის.

პრიორიტეტული რიგის გამოყენების წესები:

1.     არ არის ნებადართული Null-ის დამატება.

2.   შეუძლებელია შევქმნათ პრიორიტეტული რიგი ობიეკტების რომლებიც არ ახდნენ იმპლემენტირებას comparable ინტერფეისის.

3. ელემენტები პრიორიტეტულ რიგში ხვდება ნატურალური თანმიმდევრობით, რომელთა სორტირებაც ხდება Binary Heap-ის მეშვეობით, რაც ნიშნავს იმას რომ ელემენტების თანმიმდევრობას არ აქვს არსებითი მნიშვნელობა რიგში, რიგისთვის მხოლოდ მნიშვნელოვანია Root ელემენტი, რომელიც ნატურალურად არის Ascending order, მაგალითად, რიგს თუ დავამატებთ 1,2,5,6,8,28,0 რიგის სათავეში მოექცევა 0 და ის პირველი დატოვებს რიგს, დატოვების შემდგომ მის ადგილს დაიკავებს 1 და ა.შ. თუ სურვილი გაგვიჩდა მოვახდინოთ საკუთარი თანმიმდევორიბს დეფინირება, მაგალითად სურვილი გვაქ რო Root ელემენტი იყოს ყველაზე დიდი ლემენეტი რიგში, მაშინ შეგვიძლია საკუთარი Comparator-ის შექმნა, რის შემდგომაც გადავწერთ compare მეთოდს და რიგს დავალაგებთ ჩვენი სურვილის და მიხედვით. თანმიმდევრობებზე უფრო ვრცლად https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html

4. პრიორიტეტული  რიგი არ არის განსაზღვრული სიდიდის, ის იზრდება მოთხოვნასთან ერთად.

5.   როგორც წესი ის ბაზირებულია მასივზე, თუმცა კვანძე ბაზირებაც არ არის პრობლემა თუ ამის სურვილი გაგიჩდათ. (ჯავას ბიბლიოთეკა მასივზე ბაზირებულ პრიორიტეტულ რიგს გვთავაზობს)

სულ ეს არის საბაზისო წესები პრიორიტეტული რიგირს. სანამ საკუთარ მაგალითს გავაკეთებდეთ, გადავხედოთ თუ როგორ მუშაობს იგი ბიბლიოთეკიდან.

როდესაც ვიწყებთ პრიორიტეტული რიგის შექმნას მისი სიდიდე უდრის 11 ელემენტს.  გვაქ შესაძლებლობა იმ სიდიდის რიგი შევქმნათ რა სიდიდსაც გვურს, თუ კონსტრუკტორს გადავაწოდებთ სიდიდეს. შესაძლებელია კოლექციის და კომპერატორის გადაწოდებაც კონსტრუკტორზე, სიდიდის და კომპერატორის ერთდროულად გადაწოდება , სეთის გადაწოდება.

პირველ მაგალითზე დავამატოთ რამოდენიმე ციფრი რიგს და გამოვიტანოთ შიგთავსი ეკრანზე:

კომპილირებიშ შემდგომ:

ხედავთ რო ელემენტები არ არიან თანმიმდევრულად განლაგებული რიგში. ეს იმიტომ რო მისი იმპლემენტაცია ხდება Binary Heap-ის მეშვეობით, რომელისთვისაც პრიორიტეტული ელემენტი, ყველაზე პატარა ელემენტია რიგში. Binary Heap-ზე საუბარი მომავალში დეტალურად მოგვიწევს, ახლა უბრალო მონახაზს გავაკეთებ, რო წარმოდგენა შეგვექმნას რასთან გვაქ საქმე.

Binary Heap კოლექციაში წარმოდგენილია როგორც მასივი, რომლის root ელემენტია array[0] მასივი 0 ინდექსზე. ელემენტების განლაგება მასივში ხდება 2 პრიორიტეტის მიხედვით. ესენია ელემენტი რომელსაც გააჩნია მაქსიმალური ღირებულება და ელემენტი რომელსაც გააჩნია მინიმალური ღირებულება. პრიორიტეტულ რიგში ელემენტები განლაგებულია  ნატურალური ღირებულებით, რიგს კი ტოვებენ მინიმალური ღირებულებით.  Binary Heap არის Heap სტრუკტურული მონაცემი, რომელიც აგებულია Binary Tree მსგავსად, რაც ნიშნავს იმას რომ ის წარმოდგენილია მეხსირებაში როგორც ხე, რომელსაც აქვს Parent Nodes (Root Node, Parent, Parent leafs) და Child Nodes. (child  Node, child , child leafs). მასში ელემენებტების განლაგება ხდება მარცხნიდან მარჯვნიბ და ივსება მინიმალური ან მაქსიმალური პრიორიტეტით. ელემენტების განლაგების კონტროლი ხდება სხვა და სხვა მეთოდების მეშვეობით, რომლებზეც ახლა არ ვისაუბრებთ. ჩემი აზრით ჯობია პრიორიტეტული რიგის ჩვენ მიერ შექმნას ამ ჯერზე გვერდი აუაროთ და მოუბრუდნეთ მას როცა ხეებზე ვისაუბრებთ. რადგან საკმაოდ რთულად აღსაქმელი იქნება მისი სტრუკტურა ამ ეტაპზე თქვენთვის. ნახეთ ფოტო როგორ გამოიყურება ბინარული ჰიპი, რომელსაც იყენებს პრიორიტეტული რიგი.

ჩვენ რიგსაც იგივე პრინციპით გამოაქვს ინფორმაცია კონზოლში და ტოვებს მას მინიმალური პრიორიტეტით. ნახეთ მაგალითი:

კომპილირების შემდგომ:

მაგრამ რა მოხეება თუ არ გვაწყობს მსგავსი თანმიმდევრპბის ქონა? ვმუშაობთ „სადმე“ და ჩვენი ამოცანა არის რომ პრიორიტეტი რიგში იყოს ყველაზე დიდი ელემენტი. ასეთ სიტუაციაში რიგის კონსტრუკტორი გვაძლევს საშუალებას გადავაწოდოთ მას კომპერატორი და დავალაგოთ თანმიმდევრობა ისე როგორც გვსურს. ნახეთ მაგალითი:

კონსტრუკტორს გადავაწოდეთ კომპერატორი, რის შემდგომაც ანონიურ კლასში გადავწერეთ compare მეთოდი. სადაც ვამბობთ , რომ რიგიდან ელემენტებმა უნდა დატოვოს თანმიმდევრობა დაღმავლობის პრინციპით, ანუ ყველაზე მაღალი ელემენტით დაიწყოს. 

და ვიწყებთ წაშლას.

როგორც ხედავთ.  პრიორიტეტული ელემენტი გახდა ყველაზე დიდი ელემენტი რიგში. შესაძლებელია უამრავი სახეობის პრიორიტეტით დაალაგოთ როგი.  ნახეთ String-ის მაგალითი, სადაც რიგში ელემენტებს დავალაგებთ სიტყვის სიდიდის მიხედვით.

Return ველებს არ მიაქციოთ ყურადღება, არ აქვს დიდი მნიშვნელობა მანდ რას დაწერ, კომპილირების შემდგომ:

ნატურალური თანმიმდევრობა სტრინგის შემთხვევაში არის ალფავიტური თანმიმდევრობა, ა,ბ,ვ << და რიგის დატოვებაც მოხდება ამ თანმიდმევრობით. ვნახოთ კიდევ ერთი მაგალითი, ამ ჯერზე საკუთარი კლასი გვაქ შექმნილი სადაც ძაღლები და კატები  რიგს დროის მიხედვით დატოვებენ.

კომპილირების შემდგომ:

სამწუხაროდ კატის კომპილირება ვერ ხერხდება. როგორც მაღლა ვახსენე პრიორიტეტული იღებს ობიეკტებს, რომლებაც მოახდინეს კომპერატორის ან Comparable-ის იმპლემენტაცია.

ჩვენი კლასი კი არ ახდენს მსგავსი იმპლემენტაციის დეფინირებას. გადავიდეთ ძაღლზე.

ძაღლი ახდენს იმპლემენტაციას სადაც რეალურ პარამეტრად ახდენს საკუთარი თავის გადაწოდებას.

გადაწერილი მეთოდი აკონტროლებს, ძაღლს რომელიც ყველაზე ადრე მოვიდა ყველაზე ადრე დატოვებს ვეტერინარს.

რის შემდგომაც ვქმნით ობიეკტებს და ვახდენთ კომპილირებას.

კომპილირების შემდგომ:

ნებისმიერი გრაფით შესაძლებელია ობიეკტების დალაგება, სახელით, ნომრით, სერიული ნომრით. ამის მაგალითები მაღლა ნახეთ. რეალურ პრაკტიკაში, მოგიწევთ მონაცემთა ბაზასთან მუშაობა, სადაც გრაფა (კოლონა) გექნებათ, რომლის შევსებაც მოხდება პრიორიტეტებით. ექიმი შეიყვანს, „გადაუდებელი“, „საშუალო“, „სასწრაფო“, „სტაბილური“ საკვანძო სიტყვებს და თქვენ დაალაგებთ პაციენტებს საკვანძო სიტყვებზე დაყრდნობით. ამ კონკრეტულ მაგალითზე დროის გრაფაში დროის კლასების გამოყენება მინდოდა, მაგრამ მაგათ ცალკე თავს დაუთმობ, რომ არ გავართულოთ. ჯავაში კი არსებობს უამრავი სასარგებლო ხელსაწყო რომლის გამოყენებასაც მსგავს სიტუაციაში მარტივად შეძლებთ. კლასები რომლებიც დროს აკონტროლებენ (Date, Time, Period, Instant, LocatDate და ა.შ)

როგორც მაღლა ვახსენე, არა კონკურენტული ინტერფეისი რომელიც ახდენს რიგის იმპლემენტაციას არის Deque ინტერფეისი, რომლის მემკვიდრენიც არიან ArrayDeque, ConcurrentLinkedQueue, LinkedList, LinkedBlockingQueue. დაკავშირებულ სიებზე უკვე ვისაუბრეთ, ამიტომ ამ თავს დაუთმოთ ArrauDeque კლას. ConcurrentLinkedQueue, LinkedBlockingQueue კლასები არიან კონკურენტული პაკეტიდან დამათზე არ ვისაუბრებთ.

Deque(Double Ended Queue) ინტერფეისი, არის ინტერფეისი, რომელიც საშუალებას გვაძლევს რიგს ელემენტები დავამატოთ ორივე მხრიდან. მაღლა ვახსენე რომ რიგში ელემენტების დამატება ხდება ერთი მხრიდან და ტოვებენ მას მეორე მხრიდან, Deque ინტერფეისის შემთხვევაში ეს ასე არ არის, ვინაიდან ის გვაძლევს ორივე მხრიდან ელემენტების დამატების საშუალებას,  მისი პრინციპი მუშაობის შეიძლება წარმოდგენილ იქნეს როგორც FIFO ისე LIFO თანმიმდევრობით. თუ დავფიქრდებით ეს ინტერფეისი გვაძლევს საშუალებას გამოვიყენოთ იგი როგორც რიგი ან როგორც stack.

პროგრამირებაში Deque ინტერფეის, სლენგის დონეზე ეძახიან. Deck’s(გასაუბრებაზე თუ გკითხეს დექსზე რას გვეტყვიო Deque ინტერფეის გულისხმობენ) 

თუ ჯავას დეველოპერებს დაუჯერებთ: Deque ინტერფეისის გამოყენება უკეთესია ვიდრე Stack სტრუკტურის, რადგან Deque ინტერფეისი უფრო მაღალი ხარისხის პერფომენს გვთავაზობს, უფრო სწრაფია. იგივე შეიძლება ითქვას დაკავშირებულ სიებზეც. ბევრად უფრო ეფეკტურია დაკავშირებული სიის Deque იმპლემენტაციის გამოყენება ვიდრე List ინპლმემენტაციით.  ვნახოთ მაგალითი  :

კომპილირების შემდგომ:

როგორც ხედავთ ზუსტად იგივე ფუნქციონალიზმი აქვს თუ მას ვიყენებთ როგორც სთექს. ბაზირებულია LIFO პრინციპზე.

კომპილირების შემდგომ:

წესები Deque ინტერფეისის არსებითად არ განსხვავდება მისი სუპერ ინტერფეისის წესებისგან.  ამიტომ გადავიდეთ პირდაპირ საკუთარი Deque-ს შექმნაზე, რომელიც იქნება მასივზე და კვანძზე ბაზირებული.

დასაწყისისთვის შევქმნათ ინტერფეისი:

და შემდგომ მოვახდენთ მის იმპლემენტაციას, როგორც კვანძე ისე მასივზე ბაზირებულ კლასში. დიდი გამოვიდა მაგრამ სავალდებულო მეთოდებია რომელიც დექიუს უნდა გააჩნდეს.

კვანძის შექმნის მაგალითს არ ვნახავთ, რადგან უამრავჯერ გაქვთ ნანახი: ამ კონკრეტულ მაგალითში ვიყენებთ DoublyLinkedList-ის მსგავს კვანძს სადაც ელემენტების დამატება შესაძლებელია ორივე მხრიდან.

პირველი რაც უნდა გავაკეთოთ: უნდა შევქმნათ კონსტრუკტორები და მოვახდინოთ ცვლადების დეფინირება, (ინიციალიზაციის გარეშე)

ვინაიდან დაკავშირებულ კვანძს არ ჭირდება სიდიდის მითითება და შემდგომ მისი ხელოვნური ზრდა ორი კონსტრუკტორი სავსებით საკმარისია რო ამოცანას გავართვათ თავი. პირველ Default კონსტრუკტორს ვიძახებთ მეორე კონსტრუკტორში this საკვანძო სიტყვის დახმარებით. გვაქ ორი ცვლადი რომელიც მოახდენენ კვანძების კონტროლს. და მესამე პრიმიტიული ცვლადი რომელიც დაადგენს სიდიდეს.

მეთოდები რომლებიც ამატებენ რიგს იმფორმაციას.

მეთოდები რომლებიც აბრუნებენ ელემენტს რომლებმაც უნდა დატოვოს რიგი.

მეთოდები რომლებიც შლიან პირველ და ბოლო ელემენტებს:

Stack მეთოდები:

სულ ეს გახლავთ საბაზისო მეთოდები, კიდევ რამოდენიმე არის კლასში, რომელიც მაგალითებში ვერ მოხვდა და რომელსაც გითჰაბზე ნახავთ.

დავტესტოთ როგორ მუშაობს კვანძზე ბაზირებული რიგი.

Stack:

კომპილირების შემდგომ:

Deque:

კომპილირების შემდგომ:

როგორც ხედავთ იდეალურად ართმევს ამოცანას თავს ჩვენი კლასი: კლას აგრეთვე გააჩნია size(), Contains() toString(), toArray() მეთოდები. საკმაოდ პრიმიტიულებია ამიტომ არ ვნახავთ, თუმცა გვაქ ერთი მეთოდი რომელსაც აქვს უნარი მიიღოს მთლიანი კოლექცია, გამოძახებით ან კონსტრუკტორის დახმარებით და მას addAll() მეთოდი ქვია. მისი იმპლემენტირება მასივზე ბაზირებულ კლასში საკმაოდ მარტივია, თუმცა კვანძში მოითხოვს იტერაციებს, რაც საკმაოდ ნელს ხდის მის მოქმედებას თუ დიდი ზომის ინფორმაციასთან გვაქ საქმე. ვნახოთ მეთოდი და შემდგომ სტაქ-ის შიგთავსი გადავაწოდოთ რიგს, ანუ მოვახდინოთ მასი კომბინირება და შემდგომ ერთად კომპილაცია. :

პირველი გამოხატულება. (If() ველი ) იმუშავებს თუ რიგი ცარიელია, წინააღმდეგ შემთხვევაში იმუშავებს მეორე გამოხატულება.

თუ რიგი ცარიელია, მაშინ ყველა შეყვანილ ღირებულებას ვამატებთ სათითაოდ რიგს, ანუ ამ ველის გამოყენება მოხდება მაშინ როცა ინფორმაციას ახლად შექმნილ რიგს ვაწვდით კონსტრუკტორის მეშვეობით. მისი ალგორითმია O(n) რადგან არ ვიცით რა სიდიდის ინფორმაციასთან მოგვიწევს მუშაობა. მეორე გამოხატულება ინფორმაციას დაამატებს რიგს თუ მაში ინფორმაცია უკვე იმყოფება. როგორც ხედავთ ორი იტერაცია ხდება რაც 2*O(n) დროს მოითხოვს. თუმცა როგორც ალგორითმებიდან გვახსოვს კონსტანტურ სიდიდეს არ აქვს არსებითი  მნიშვნელობა. განვიხილოთ რა ხდება მეორე გამოხატულებაში. პირველი რასაც ვაკეთებთ ვიწყებთ ელემენტების წაკითხვას ბოლო ელემენტამდე, როდესაც კურსორი მიდის ბოლო ელემენტთან ჩვენ ცვლადში გვაქ შენახული მისი ღირებულება, რომლის შემდგომი ღირებულებაც არის null (ანუ სიცარიელე) ამის შემდგომ ვიწყებთ გადმოწოდებული ინფორმაციის წაკითხვას რომელსაც ვინახავთ მასივში, ყველა წაკითხული ინფორმაცია კი შედის კვანზში კონსტრუკტორის დახმარებით. ყველა შეყვანილი ინფორმაცია კვანძიდან გადაეცემა იმ ცვლადს (prev) რომელმაც მოახდინა არსებული ინფორმაციას ბოლო ელემენტამდე წაკითხვა. რის შემდგომაც ის სვამს მის შემდგომ ელემენტად გადმოცემულ ინფორმაციას. გადმოცემული ინფორმაციის წინა ელემენტი არის ბოლო შეყვანილი ელემენტი და ამის შემდგომ prev ცვლადი მიყვება ყველა ელემენტს ბოლო ღირებულებამდე, ბოლო ველზე კი მას თან მისდევს tail ცვლადი რომელმაც უნდა მოახდინოს ბოლო ელემენტის დაფიქსირება, რათა ყველა სხვა დანარჩენმა მეთოდმა გამართულად მოახერხოს ფუნქციონირება. ვნახოთ მაგალითი:

ამის შემდგომ კი მთლიანი რიგი გადავაწოდოთ ახალ რიგს:

კომპილირების შემდგომ:

როგორც წესი კარგ პრაკტიკად ითვლება გამოყენებული რესურსების წაშლა ან განულება. რადგან ინფორმაციას უკვე სხვა ცვლადი ატარებს.

ამით დასრულდა რიგის კვანძზე ბაზირებული იმპლემენტაცია.  შემედ მაგალითზე ვნახოთ რიგის მასივზე ბაზირებული ვარიანტი:

როგორც მოგეხსენებათ, მასივზე ნებისმიერი რამის ბაზირება გაცილებით მარტივია და რაც მთავარია რამოდენიმე ოპერაცია სრულდება 0 დროში. რაც გარკვეულ უპირატესობას ანიჭებს მას.

ვნახოთ რამოდენიმე საკვანძო მეთოდი. :

addFirst და addLast მეთოდები:მათი შექმნის პრინციპი მარტივია. თუ შეყვანილი იმფორმაცია უდრის ნულს მაშინ ვისვრით გამონაკლის თუ არა და ელემენტს ვამატებთ მასივს. ბოლო ინდექსზე დამატებას აკონტროლებს root ცვლადი, რომლის საწყისი ღირებულება არის 0. დაუშვათ შეგვყავს ელემენტი რომელიც პირველ პოზიციაზე გვინდა დაემატოს. რაც მოგვცემს შემდეგ სურათს: [ 0 = (0-1)&(16-1)] = ღირებულებას. ღირებულება ამ სიტუაციაში დაჯდება ინდექს 15-ზე. შემდეგი შეყვანილი 14,13,12,11 და ა.შ.  წარმოდგენა თუ გაგიჭირდათ რატომ ხდება ამ გზით დამატება გაიხსენეთ ცირკულაური მასივი. რომელიც რიგის იმპლემენტაციის დროს გამოვიყენეთ.  თუ გეზარებათ გახსენება სურათს დახედეთ.

addLast მეთოდი შესაბამისად მოძრაობას დაიწყებს მეორე მხრიდან. შეყვანილი ინფორმაცია მოხვდება 0 ინდექსზე და არა 15, რადგან tail ცვლადი უდრის სტანდარტულ სიდიდეს. მეთოდში ვამბობთ რომ შეყვანილი ცვლადი დაჯდება tail ცვლადზე, რის შემდგომაც tail ცვლადის ინდექსი იცვლება და იზრდება ყველა ჯერზე 1-ით.

მეთოდები, რომლებიც შლიან პირველ და ბოლო ელემენტს:

მსგავსად დამატებისა ამ ორ მეთოდშიც გვიწევს პირველი და ბოლო ცვლადის კონტროლი, ამ ჯერად ისინი მოძრაობენ საპირისპირო მხარეს. დაუშვათ თუ root ცვლადიდან ვშლით ელემენტს მაშინ მან უნდა გადაინაცვლოს შემდეგ ელემენტზე და არსებული ელემენტი უნდა გავანულოთ. Tail ცვლადის შემთხვევაში ცვლადი ინაცვლებს ერთი ნაბიჯით მარცხნივ და არსებული ელემენტს ვანულებთ.

სულ ეს არის ბირთვი DeQue ინტერფეისის რომელიც მასივზეა ბაზირებული. როგორც შეატყვეთ, გაცილებით ნაკლები გვაქ საწერი, ოპერაციები სწრაფია. არ მოითხოვს დიდ დროს და რესურსებს, მაღლა ვთქვი და ისევ გავიმეორებ, თუ stack ან LinkedList გამოყენება გვსურს, უმჯობესია გამოვიყენოთ ArrayDeque, ორივე სტრუკტურის ფუნქციონალიზმს ითავსებს და ორივეს ჯობია პერფომენსში.  სხვა მეთოდებს იმიტომ არ ვნახავთ, რომ თუ ამ ორი მეთოდის შექმნა შეგიძლიათ , სხვების შექმნა დიდ სირთულეს არ წარმოადგენს. ვნახოთ როგორ მუშაობს ჩვენ მიერ შექმნილი რიგი:

კომპილირების შემდგომ:

ფოტოზე რიგს ვიყენებთ როგორც სტეკს. შემდეგ ფოტოზე რიგს გამოვიყენებთ როგორც ორმხრივად მოძრავ რიგს.

კომპილირების შემდგომ:

იდეალურად ართმევს თავს ამოცანას.

ამით რიგზე საუბარს მოვრჩით. საკმარისი იმფორმაციაა იმისთვის რომ წარმოდგენა შეგექმნათ რა არის რიგი. დამატებითი იმფორმაციის მოპოვება არასდროს არის რთული თუ ეს მცირედი რიგის გამოყენების ინტერეს გაგიჩენთ. ჩვენი შემდეგი გაჩერება იქნება Set, Map, Tree ან HashTable  სტრუკტურული მონაცემი. (თუ სურვილი გაქვთ მომწერეთ იმეილზე და იმ სტრუკტურაზე ვისაუბრებ ჩამოთვლილთაგან, რომელიც უფრო გაინტერესებთ)

დამატებითი ინფორმაცია: როგორც წესი რიგი განსაზღვრული სიდიდთ გვხვდება ჯავას კონკურენტულ პაკეტში, ჯავა უტილ პაკეტში რიგი განსაზღვრული სიდიდით არ გვხვდება. რიგის განსაზღვრული სიდიდით გამოყენება მიზანშეწონილია, როცა იცით თქვენ პროდუკტს რამდენი ადამიანი, ან სერვისი გამოიყენებს, ამის შემდგომ მარტივია მათ მიცეთ უფლება ოპერაციის დამატების და გამოტანის რიგიდან თანმიმდევრულად. თუ რიგი შეივსება მაშინ მასზე დამატება ვერ მოხდება, თუ რიგი ცარიელია მაშინ მისგან ინფორმაციის გამოტანა შეუძლებელია. ასევე შესაძლებელია ყველა ოპერაციას მიანიჭოთ გარკვეული დრო, დროის ამოწურვის შემდგომ კი გაანთავისუფლოთ იგი. ამ და სხვა მრავალ დეტალზე ჯავა უტილ კონკურენტულ-ზე საუბრის დროს დავბრუნდებით. 

მაგალითებად მოყვანილი კლასების სანახავად გადადით შემდეგ ბმულზე