Java-da Məlumat Strukturları - Stack və Queue

Salam! Bu gün hər hansı bir proqramçı üçün məlumat strukturları kimi vacib şeylər haqqında danışacağıq . Vikipediya deyir: Məlumat strukturu ( ing. data structure ) sizə hesablamada eyni tipli və/yaxud məntiqi əlaqəli verilənlərin çoxunu saxlamağa və emal etməyə imkan verən proqram vahididir. Tərif bir az qarışıqdır, amma mahiyyəti aydındır. Məlumat strukturu məlumatları sonrakı istifadə üçün saxladığımız bir növ yaddaşdır. Proqramlaşdırmada çox sayda məlumat strukturları var. Çox vaxt, müəyyən bir problemi həll edərkən, ən vacib şey bu məqsəd üçün ən uyğun məlumat strukturunu seçməkdir. Və siz onların çoxu ilə artıq tanışsınız! Məsələn, massivlərlə . Həm də Map(adətən “lüğət”, “xəritə” və ya “assosiativ massiv” kimi tərcümə olunur) ilə. Bunu başa düşmək çox vacibdir: məlumat strukturları heç bir xüsusi dillə əlaqəli deyil . Bunlar sadəcə olaraq mücərrəd “layihələrdir” və ona görə hər bir proqramlaşdırma dili öz siniflərini - bu strukturun tətbiqlərini yaradır. Məsələn, ən məşhur məlumat strukturlarından biri əlaqəli siyahıdır . Vikipediyaya daxil ola bilərsiniz, onun necə işlədiyini, hansı üstünlükləri və mənfi cəhətləri olduğunu oxuya bilərsiniz. Onun tərifini sizə tanış tapa bilərsiniz :) “Əlaqələndirilmiş siyahı hər biri həm məlumatın özünü, həm də növbəti və/yaxud bir və ya iki keçidi (“bağlantı”) ehtiva edən qovşaqlardan ibarət kompüter elmində əsas dinamik məlumat strukturudur. əvvəlki node siyahısı" Deməli, bu bizimdir LinkedList! Tam olaraq belədir :) Əlaqəli siyahı məlumat strukturu sinifdə Java dilində həyata keçirilir LinkedList. Ancaq digər dillər də əlaqəli siyahıları həyata keçirir! Python-da “ llist”, Scala-da Java-da olduğu kimi eyni adlanır - “ LinkedList“. Əlaqəli siyahı əsas ümumi məlumat strukturlarından biridir, ona görə də onun həyata keçirilməsini istənilən müasir proqramlaşdırma dilində tapa bilərsiniz. Assosiativ massiv ilə eyni şey. Vikipediyadan onun tərifi belədir: Assosiativ massiv “(açar, dəyər)” formasının cütlərini saxlamağa imkan verən və cüt əlavə etmək, eləcə də axtarış əməliyyatlarını dəstəkləyən mücərrəd məlumat növüdür (məlumat anbarına interfeysdir). və cütü açarla silmək. Sizə heç nəyi xatırlatmır? :) Məhz biz Javaistlər üçün assosiativ massiv interfeysdirMap. Lakin bu məlumat strukturu başqa dillərdə də həyata keçirilir! Məsələn, C# proqramçıları bunu “Lüğət” adı ilə bilirlər. Ruby dilində isə “Hash” adlı sinifdə həyata keçirilir. Ümumiyyətlə, mənasının nə olduğunu təxminən başa düşürsünüz: məlumat strukturu hər bir xüsusi dildə fərqli şəkildə həyata keçirilən bütün proqramlaşdırma üçün ümumi olan bir şeydir. Bu gün biz iki belə strukturu öyrənəcəyik və onların Java-da necə həyata keçirildiyini görəcəyik - stack və queue.

Java-da yığın

Yığın, məlum məlumat strukturudur. Bu, çox sadədir və gündəlik həyatımızda olan kifayət qədər çox obyekt yığın kimi “həyata keçirilir”. Sadə bir vəziyyəti təsəvvür edin: siz oteldə yaşayırsınız və gün ərzində iş məktubları alırsınız. Siz o vaxt otaqda olmadığınıza görə otel işçisi sadəcə olaraq gələn məktubları masanıza qoyub. Əvvəlcə birinci hərfi stolun üstünə qoydu. Sonra ikincisi gəldi və birincinin üstünə qoydu. Gələn üçüncü məktubu ikincinin, dördüncünü isə üçüncü məktubun üstünə qoydu. İndi sadə bir suala cavab verin: otağınıza gələndə və masanın üstündə bir yığın görəndə ilk olaraq hansı məktubu oxuyacaqsınız ? Düzdü, yuxarıdakı məktubu oxuyacaqsınız. Yəni zamanında sonuncu gələn . Yığın tam olaraq belə işləyir. Bu iş prinsipi LIFO adlanır - “son girən - ilk çıxan” (“son girən, ilk çıxan”). Bir yığın nə üçün faydalı ola bilər? Məsələn, siz Java-da bir növ kart oyunu yaradırsınız. Masanın üstündə bir kart göyərtəsi var. Oynanan kartlar atılır. Siz iki yığından istifadə edərək həm göyərtəni, həm də atmağı həyata keçirə bilərsiniz. Oyunçular göyərtənin yuxarı hissəsindən kartları çəkirlər - hərflərlə eyni prinsip. Oyunçular kartları atdıqda, köhnə kartların üstünə yeni kartlar qoyulur. Yığından istifadə edərək həyata keçirilən oyunumuzun ilk qaralamasının necə görünəcəyi budur:

public class Card {

   public Card(String name) {
       this.name = name;
   }

   private String name;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   @Override
   public String toString() {
       return "Card{" +
               "name='" + name + '\'' +
               '}';
   }
}

import java.util.Stack;

public class SimpleCardGame {

   //  колода
   private Stack<Card> deck;

   //  сброс
   private Stack<Card> graveyard;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       graveyard.push(card);
   }

   public Card lookTopCard() {

       return deck.peek();
   }

   //  ..геттеры, сеттеры и т.д.
}

Daha əvvəl dediyimiz kimi, iki yığınımız var: göyərtə və atma. Stack verilənlər strukturu Java-da java.util.Stack. Kart oyunumuzda oyunçuların hərəkətlərini təsvir edən 3 üsul var:

• göyərtədən bir kart götür (üsul getCardFromDeck());
• kartdan imtina (metod discard());
• yuxarı karta baxın (metod lookTopCard()). Deyək ki, bu, oyunçuya daha sonra hansı kartın oyuna girəcəyini öyrənməyə imkan verən bonus mexaniki "Kəşfiyyat" olacaq.

Metodlarımızın içərisində sinif metodları deyilir Stack:

• push()— yığının yuxarı hissəsinə element əlavə edir. Biz kartı atdığımız zaman o, əvvəllər atılmış kartların üstünə keçir;
• pop()— üst elementi yığından çıxarır və onu qaytarır. Bu üsul "oyunçu bir kart çəkir" mexanikini həyata keçirmək üçün idealdır.
• peek()- yığının yuxarı elementini qaytarır, lakin onu yığından çıxarmır

Baxaq oyunumuz necə işləyəcək:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       //  создаем колоду и добавляем в нее карты
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Рагнарос"));
       deck.push(new Card("Пират Глазастик"));
       deck.push(new Card("Сильвана Ветрокрылая"));
       deck.push(new Card("Миллхаус Манашторм"));
       deck.push(new Card("Эдвин ван Клифф"));

       //  создаем сброс
       Stack<Card> graveyard = new Stack<>();

       //  начинаем игру
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setGraveyard(graveyard);

       //  первый игрок берет 3 карты из колоды
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Какие карты достались первому игроку?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       //  первый игрок отправляет в сброс 3 своих карты
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("Какие карты находятся в сбросе?");
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
   }
}

Beləliklə, göyərtəmizə beş kart əlavə etdik. Birinci oyunçu onlardan 3-nü götürdü. Hansı kartları aldı? Konsol çıxışı:

Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}

Kartların konsola çıxma ardıcıllığına diqqət yetirin. "Edwin Van Cleiff" kartı göyərtəni vuran sonuncu kart idi (ard-arda beşinci) və oyunçunun ilk götürdüyü kart idi. "Michhlaus" göyərtədə sonuncu, ikincisi isə onun oyunçusu oldu. "Sylvanas" göyərtəni sondan üçüncü vurdu və üçüncü oyunçuya keçdi. Sonra oyunçu kartlarını atır. Əvvəlcə Edvini, sonra Millhouse, sonra Silvanası düşür. Bundan sonra atdığımız kartları bir-bir konsola çıxarırıq: Konsola çıxış:

Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}

Və yenidən yığının necə işlədiyini görürük! Oyunumuzdakı atma da bir yığındır (eynilə göyərtə kimi). "Edwin Van Clyffe" ilk olaraq buraxıldı. İkinci atılan "Millhouse Manastorm" idi - və atılan Edvinin üstündə yatdı. Sonra Sylvanas atıldı - və bu kart Millhouse-un üstündə yatdı. Gördüyünüz kimi, yığının necə işləməsi ilə bağlı mürəkkəb bir şey yoxdur. Bununla belə, bu məlumat strukturunu bilmək lazımdır - müsahibələrdə bu barədə tez-tez soruşulur və daha mürəkkəb məlumat strukturları çox vaxt onun əsasında qurulur.

Növbə

Növbə (və ya ingiliscə “Queue”) başqa bir ümumi məlumat strukturudur. Bir yığın kimi, Java da daxil olmaqla bir çox proqramlaşdırma dillərində həyata keçirilir. Növbə ilə yığın arasındakı fərq nədir? Onun növbəsi LIFO-ya deyil, başqa bir prinsipə əsaslanır - FIFO ("ilk gələn - ilk çıxan", "ilk gələn - ilk çıxan") . Bunu başa düşmək asandır, nümunə götürsək... və ya heç olmasa real həyatdan adi, real növbə! Məsələn, mağazaya növbə. Növbədə beş nəfər varsa, növbəyə birinci gələn şəxs mağazaya girəcək . Əgər daha bir nəfər (beş növbədən başqa) bir şey almaq istəsə və növbəyə düşərsə, o, mağazaya sonuncu , yəni altıncı daxil olur. Növbə ilə işləyərkən sona yeni elementlər əlavə olunur və əgər element almaq istəyirsinizsə, o, əvvəldən götürüləcək. Bu, onun işinin əsas prinsipidir, onu yadda saxlamaq lazımdır.Növbə prinsipini intuitiv şəkildə başa düşmək çox asandır, çünki real həyatda tez-tez rast gəlinir. Ayrı-ayrılıqda qeyd etmək lazımdır ki, Java-da növbə siniflə deyil, interfeys ilə təmsil olunur - Queue. Ancaq eyni zamanda, Java-da növbə çoxlu tətbiqetmələrə malik bir interfeysdir. Oracle sənədlərinə nəzər salsaq görərik ki, növbədən 4 fərqli interfeys və son dərəcə təsir edici siniflər siyahısı miras qalıb:

All Known Subinterfaces

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All Known Implementing Classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque

ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

PriorityBlockingQueue, PriorityQueue, SynchronousQueue

Nə böyük siyahı! Ancaq əlbəttə ki, indi bütün bu sinifləri və interfeysləri əzbərləməyə ehtiyac yoxdur - başınız partlaya bilər :) Ən vacib və maraqlı məqamlardan yalnız bir neçəsini nəzərdən keçirəcəyik. Əvvəlcə növbənin dörd "alt interfeysindən" birinə diqqət yetirək - Deque. Bunda xüsusi nə var? Deque- Bu, ikitərəfli növbədir. O, hər iki ucuna (növbənin əvvəli və sonuna) elementlər əlavə etməyə və növbənin hər iki ucundan elementlər götürməyə imkan verməklə adi növbənin funksionallığını genişləndirir. Deque inkişafda geniş istifadə olunur. Yuxarıda təqdim etdiyimiz növbə siniflərinin siyahısına diqqət yetirin. Siyahı kifayət qədər uzundur, amma orada bizə tanış olan bir şey varmı?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, bizim köhnə dostumuz buradadır LinkedList! Yəni interfeysi həyata keçirir Queue? Amma o, necə növbə ola bilər? Axı LinkedListbu, əlaqəli siyahıdır! Doğrudur, lakin bu, onun növbə olmasına mane olmur :) Budur onun həyata keçirdiyi bütün interfeyslərin siyahısı:

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

Gördüyünüz kimi, LinkedListo, interfeysi Deque- ikitərəfli növbəni həyata keçirir. Bu niyə lazımdır? Bunun sayəsində həm əvvəldən, həm də sondan elementlər əldə edə bilərik LinkedList. Həm də - həm başlanğıca, həm də sonuna elementlər əlavə edin. LinkedListBudur interfeysdən miras alınan üsullar Deque:

• peekFirst()— birinci elementi qaytarır (ancaq növbədən çıxarmır).
• peekLast()— sonuncu elementi qaytarır (ancaq növbədən çıxarmır).
• pollFirst()- birinci elementi növbədən qaytarır və onu silir.
• pollLast()- növbədən sonuncu elementi qaytarır və onu silir.
• addFirst()— növbənin əvvəlinə yeni element əlavə edir.
• addLast()— növbənin sonuna element əlavə edir.

Gördüyünüz kimi, LinkedListo, ikitərəfli növbənin funksionallığını tam şəkildə həyata keçirir! Və proqramda belə funksionallıq lazımdırsa, ondan istifadə edilə biləcəyini biləcəksiniz :) Və bugünkü mühazirəmiz başa çatmaq üzrədir. Nəhayət, sizə əlavə oxumaq üçün bir neçə link verəcəyəm. Əvvəlcə PriorityQueue-ə həsr olunmuş məqaləyə diqqət yetirin - "prioritet növbəsi". Bu Queue-un ən maraqlı və faydalı tətbiqlərindən biridir. Məsələn, mağazanızda 50 nəfər növbə varsa və onlardan 7-si VIP müştəridirsə, PriorityQueuebu, ilk olaraq onlara xidmət göstərməyə imkan verəcək! Çox faydalı bir şey, razı deyilsiniz? :) İkincisi, Robert Laforetin “Java-da verilənlərin strukturları və alqoritmləri” kitabını bir daha xatırlatmaq artıq olmaz . Kitabı oxuyarkən siz nəinki bir çox məlumat strukturlarını (o cümlədən yığın və növbə) öyrənəcəksiniz, həm də onların bir çoxunu özünüz həyata keçirəcəksiniz! Məsələn, Java-nın Stack sinfi olmadığını təsəvvür edin. Proqramınız üçün belə bir məlumat strukturuna ehtiyacınız olsa nə edərdiniz? Təbii ki, özüm yazmalıydım. Laforetin kitabını oxuyarkən , çox vaxt bunu edəcəksiniz. Bunun sayəsində məlumat strukturları haqqında anlayışınız sadəcə nəzəriyyəni öyrənməkdən daha geniş olacaq :) Bu gün nəzəriyyə ilə işimiz bitdi, amma praktikasız nəzəriyyə heç bir şey deyil! Problemlər öz-özünə həll olunmayacaq, ona görə də indi onları həll etməyin vaxtıdır! :)