Java-da ma'lumotlar tuzilmalari - Stack va Queue

Salom! Bugun biz har qanday dasturchi uchun ma'lumotlar tuzilmalari kabi muhim narsalar haqida gaplashamiz . Vikipediyada shunday deyiladi: Ma'lumotlar strukturasi ( ing. ma'lumotlar strukturasi ) - bu hisoblashda bir xil turdagi va/yoki mantiqiy bog'liq bo'lgan ko'plab ma'lumotlarni saqlash va qayta ishlash imkonini beruvchi dasturiy ta'minot birligi. Ta'rif biroz chalkash, ammo uning mohiyati aniq. Ma'lumotlar strukturasi - bu biz keyingi foydalanish uchun ma'lumotlarni saqlaydigan saqlash turi. Dasturlashda turli xil ma'lumotlar tuzilmalari mavjud. Ko'pincha, muayyan muammoni hal qilishda, eng muhimi, bu maqsad uchun eng mos ma'lumotlar strukturasini tanlashdir. Va siz ularning ko'pchiligi bilan allaqachon tanishsiz! Masalan, massivlar bilan . Va shuningdek Map(odatda "lug'at", "xarita" yoki "assotsiativ massiv" deb tarjima qilinadi) bilan. Tushunish juda muhim: ma'lumotlar tuzilmalari hech qanday aniq tilga bog'liq emas . Bu shunchaki mavhum "loyihalar" bo'lib, unga ko'ra har bir dasturlash tili o'z sinflarini - ushbu tuzilmani amalga oshirishni yaratadi. Masalan, eng mashhur ma'lumotlar tuzilmalaridan biri bu bog'langan ro'yxatdir . Siz Vikipediyaga kirishingiz, uning qanday ishlashi, qanday afzalliklari va kamchiliklari borligi haqida o'qishingiz mumkin. Uning ta'rifi sizga tanish bo'lishi mumkin :) "Bog'langan ro'yxat - bu kompyuter fanidagi asosiy dinamik ma'lumotlar tuzilmasi bo'lib, ularning har biri ma'lumotlarning o'zini va keyingi va/yoki bir yoki ikkita havolani ("bog'lanish") o'z ichiga olgan tugunlardan iborat. oldingi tugunlar ro'yxati" Demak, bu bizniki LinkedList! Aynan shunday bo'ladi :) Bog'langan ro'yxat ma'lumotlar strukturasi sinfda Java tilida amalga oshiriladi LinkedList. Ammo boshqa tillar ham bog'langan ro'yxatlarni amalga oshiradi! Pythonda u “ llist” deb ataladi, Scala-da u Java-dagi kabi deyiladi - “ LinkedList“. Bog'langan ro'yxat asosiy umumiy ma'lumotlar tuzilmalaridan biridir, shuning uchun uni har qanday zamonaviy dasturlash tilida amalga oshirishingiz mumkin. Assotsiativ massiv bilan ham xuddi shunday. Mana uning Vikipediyadagi ta'rifi: Assotsiativ massiv - bu "(kalit, qiymat)" ko'rinishidagi juftlarni saqlashga imkon beruvchi va juftlikni qo'shish, shuningdek qidirish operatsiyalarini qo'llab-quvvatlaydigan mavhum ma'lumotlar turi (ma'lumotlar do'konining interfeysi). va juftlikni kalit bo'yicha o'chirish. Sizga hech narsani eslatmayaptimi? :) Aynan biz Javaistlar uchun assotsiativ massiv interfeysdirMap. Ammo bu ma'lumotlar tuzilmasi boshqa tillarda ham qo'llaniladi! Misol uchun, C# dasturchilari uni "Lug'at" nomi bilan bilishadi. Va Ruby tilida u "Hash" deb nomlangan sinfda amalga oshiriladi. Umuman olganda, siz ma'no nima ekanligini taxminan tushunasiz: ma'lumotlar strukturasi - bu barcha dasturlash uchun umumiy narsa bo'lib, u har bir aniq tilda boshqacha tarzda amalga oshiriladi. Bugun biz ikkita shunday tuzilmani o'rganamiz va ular Java-da qanday amalga oshirilishini ko'rib chiqamiz - stek va navbat.

Java-da stack

Stack - ma'lum ma'lumotlar tuzilmasi. Bu juda oddiy va kundalik hayotimizdagi juda ko'p ob'ektlar stek sifatida "amalga oshirilgan". Oddiy vaziyatni tasavvur qiling: siz mehmonxonada yashaysiz va kun davomida sizga biznes xatlari keladi. Siz o'sha paytda xonada bo'lmaganingiz uchun mehmonxona xodimi kelgan xatlarni shunchaki stolingizga qo'ydi. Avval u birinchi harfni stolga qo'ydi. Keyin ikkinchisi kelib, birinchisining ustiga qo'ydi. U kelgan uchinchi harfni ikkinchisining ustiga, to‘rtinchisini esa uchinchisining ustiga qo‘ydi. Endi oddiy savolga javob bering: xonangizga kelganingizda va stol ustidagi to'plamni ko'rganingizda birinchi navbatda qaysi xatni o'qiysiz ? To'g'ri, siz yuqoridagi harfni o'qiysiz. Ya'ni, o'z vaqtida oxirgi kelgan . Stack aynan shunday ishlaydi. Ushbu ish printsipi LIFO deb ataladi - "oxirgi kir - birinchi chiqadi" ("oxirgi kir, birinchi chiqadi"). Stack nima uchun foydali bo'lishi mumkin? Misol uchun, siz Java-da qandaydir karta o'yinini yaratyapsiz. Stolda kartalar to'plami yotadi. O'ynalgan kartalar bekor qilinadi. Siz ikkita stack yordamida pastki va tashlab qo'yishingiz mumkin. O'yinchilar kemaning yuqori qismidan kartalarni chizishadi - harflar bilan bir xil printsip. O'yinchilar kartalarni tashlab yuborishganda, eski kartalar ustiga yangi kartalar qo'yiladi. Stack yordamida amalga oshirilgan o'yinimizning birinchi loyihasi qanday ko'rinishga ega bo'ladi:

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();
   }

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

Yuqorida aytib o'tganimizdek, bizda ikkita stack bor: pastki va tashlab yuborish. Ma'lumotlar stek tuzilishi Java-da amalga oshiriladi java.util.Stack. Bizning karta o'yinimizda o'yinchilarning harakatlarini tavsiflovchi 3 ta usul mavjud:

• kemadan kartani oling (usul getCardFromDeck());
• kartani bekor qilish (usul discard());
• yuqori kartaga qarang (usul lookTopCard()). Aytaylik, bu "Intelligence" bonus mexanikasi bo'ladi, bu o'yinchiga keyingi o'yinda qaysi karta kelishini aniqlashga imkon beradi.

Bizning uslublarimiz ichida sinf usullari deyiladi Stack:

• push()— stekning yuqori qismiga element qo‘shadi. Biz kartani tashlaganimizda, u ilgari tashlangan kartalar ustiga chiqadi;
• pop()— stekdan yuqori elementni olib tashlaydi va uni qaytaradi. Ushbu usul "o'yinchi kartani tortadi" mexanikni amalga oshirish uchun ideal.
• peek()- stekning yuqori elementini qaytaradi, lekin uni stekdan olib tashlamaydi

Keling, o'yinimiz qanday ishlashini ko'ramiz:

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());
   }
}

Shunday qilib, biz kemamizga beshta kartani qo'shdik. Birinchi o'yinchi ulardan 3 tasini oldi. U qanday kartalarni oldi? Konsol chiqishi:

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

Kartalarni konsolga chiqarish tartibiga e'tibor bering. "Edwin Van Cleiff" kartasi kemaning eng oxirgisi (ketma-ket beshinchi) bo'lib, o'yinchi birinchi bo'lib olgan karta edi. "Michlaus" kemaning ikkinchi o'yinchisi bo'ldi va uning o'yinchisi ikkinchi o'rinni egalladi. "Silvanas" oxirigacha uchinchi o'rinni egallab, uchinchi o'yinchi tomon yo'l oldi. Keyin o'yinchi o'z kartalarini tashlaydi. Avval u Edvinni, keyin Millxausni, keyin Silvanasni tushiradi. Shundan so'ng biz birma-bir konsolga tashlab qo'yilgan kartalarni chiqaramiz: Konsolga chiqaramiz:

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

Va yana biz stek qanday ishlashini ko'ramiz! Bizning o'yinimizdagi tashlandiq ham stek (xuddi pastki kabi). "Edvin Van Kliff" birinchi bo'lib tushdi. Ikkinchi tashlab ketilgan "Millhouse Manastorm" edi - va Edvinning tepasida tashlab yotardi. Keyin Silvanas tashlandi - va bu karta Millhouse tepasida yotardi. Ko'rib turganingizdek, stek qanday ishlashi haqida hech qanday murakkab narsa yo'q. Biroq, bu ma'lumotlar strukturasini bilish kerak - bu haqda ko'pincha intervyularda so'raladi va ko'pincha uning asosida murakkabroq ma'lumotlar tuzilmalari quriladi.

Navbat

Navbat (yoki ingliz tilida "Queue") yana bir keng tarqalgan ma'lumotlar strukturasidir. Xuddi stek kabi, u ko'plab dasturlash tillarida, jumladan Java-da ham amalga oshiriladi. Navbat va stek o'rtasidagi farq nima? Uning navbati LIFO asosida emas, balki boshqa tamoyilga asoslanadi - FIFO (“birinchi kiruvchi birinchi chiqadi”, “birinchi kiruvchi birinchi chiqadi”) . Buni tushunish oson, misol tariqasida ... yoki hech bo'lmaganda haqiqiy hayotdan oddiy, haqiqiy navbat! Masalan, do'konga navbat. Agar navbatda besh kishi bo'lsa, navbatdagi birinchi odam do'konga kiradi . Agar yana bir kishi (navbatdagi besh kishidan tashqari) biror narsa sotib olmoqchi bo'lsa va navbatda tursa, u do'konga oxirgi marta kiradi , ya'ni oltinchi. Navbat bilan ishlashda oxiriga yangi elementlar qo'shiladi va agar element olishni istasangiz, u boshidan olinadi. Bu uning ishlashining asosiy printsipi bo'lib, siz uni eslab qolishingiz kerak Navbatning printsipini intuitiv ravishda tushunish juda oson, chunki u real hayotda tez-tez uchrab turadi. Alohida ta'kidlash joizki, Java-da navbat sinf bilan emas, balki interfeys bilan ifodalanadi Queue. Shu bilan birga, Java-da navbat ko'plab ilovalarga ega interfeysdir. Agar biz Oracle hujjatlarini ko'rib chiqsak, navbatdan 4 xil interfeys va sinflarning juda ta'sirli ro'yxati meros qilib olinganligini ko'ramiz:

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

Qanday katta ro'yxat! Lekin, albatta, hozir bu sinflar va interfeyslarni yodlab olishingiz shart emas - sizning boshingiz portlashi mumkin :) Biz faqat bir nechta muhim va qiziqarli fikrlarni ko'rib chiqamiz. Birinchidan, navbatning to'rtta "pastki interfeysi" dan biriga e'tibor qarataylik - Deque. Buning nimasi o'ziga xos? Deque- Bu ikki tomonlama navbat. U har ikki uchiga (navbatning boshi va oxiri) elementlar qo‘shish va navbatning ikkala uchidan elementlarni olish imkonini berib, oddiy navbatning funksionalligini kengaytiradi. Deque rivojlanishda keng qo'llaniladi. Yuqorida biz taqdim etgan navbat sinflari ro'yxatiga e'tibor bering. Ro'yxat juda uzun, lekin u erda bizga tanish narsa bormi?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, bizning eski do'stimiz shu erda LinkedList! Ya'ni, u interfeysni amalga oshiradi Queue? Lekin u qanday qilib navbat bo'lishi mumkin? Axir LinkedList, bu bog'langan ro'yxat! To'g'ri, lekin bu uning navbatda turishiga to'sqinlik qilmaydi :) Mana u amalga oshiradigan barcha interfeyslarning ro'yxati:

All Implemented Interfaces:

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

Ko'rib turganingizdek, LinkedListu interfeysni Deque- ikki tomonlama navbatni amalga oshiradi. Bu nima uchun kerak? Buning yordamida biz boshidan ham, oxiridan ham elementlarni olishimiz mumkin LinkedList. Va shuningdek - boshiga ham, oxiriga ham elementlar qo'shing. LinkedListMana interfeysdan meros bo'lib qolgan usullar Deque:

• peekFirst()— birinchi elementni qaytaradi (lekin navbatdan olib tashlamaydi).
• peekLast()— oxirgi elementni qaytaradi (lekin navbatdan olib tashlamaydi).
• pollFirst()- navbatdan birinchi elementni qaytaradi va uni olib tashlaydi.
• pollLast()- navbatdagi oxirgi elementni qaytaradi va uni olib tashlaydi.
• addFirst()— navbat boshiga yangi element qo'shadi.
• addLast()— navbat oxiriga element qo‘shadi.

Ko'rib turganingizdek, LinkedListu ikki tomonlama navbatning funksionalligini to'liq amalga oshiradi! Va agar dasturda bunday funksionallik kerak bo'lsa, undan foydalanish mumkinligini bilib olasiz :) Va bizning bugungi ma'ruzamiz o'z nihoyasiga yetmoqda. Va nihoyat, men sizga keyingi o'qish uchun bir nechta havolalarni beraman. Birinchidan, PriorityQueue-ga bag'ishlangan maqolaga e'tibor bering - "ustivor navbat". Bu Queue-ning eng qiziqarli va foydali ilovalaridan biridir. Misol uchun, agar sizning do'koningizda 50 kishi navbatda bo'lsa va ulardan 7 nafari VIP mijoz bo'lsa, PriorityQueuebu sizga birinchi navbatda ularga xizmat ko'rsatish imkonini beradi! Juda foydali narsa, rozi emasmisiz? :) Ikkinchidan, Robert Laforetning "Java'da ma'lumotlar tuzilmalari va algoritmlari" kitobini yana bir bor eslatib o'tish ortiqcha bo'lmaydi . Kitobni o'qiyotganda siz nafaqat ko'plab ma'lumotlar tuzilmalarini (jumladan, stek va navbatni) o'rganasiz, balki ularning ko'pini o'zingiz ham amalga oshirasiz! Misol uchun, Java-da Stack sinfi bo'lmaganligini tasavvur qiling. Agar dasturingiz uchun shunday ma'lumotlar tuzilmasi kerak bo'lsa nima qilgan bo'lardingiz? Albatta, buni o'zim yozishim kerak edi. Laforetning kitobini o'qiyotganda , siz ko'pincha shunday qilasiz. Buning yordamida ma'lumotlar tuzilmalari haqidagi tushunchangiz shunchaki nazariyani o'rganishdan ko'ra ancha kengroq bo'ladi :) Biz bugungi kun uchun nazariyani tugatdik, ammo amaliyotsiz nazariya hech narsa emas! Muammolar o'z-o'zidan hal etilmaydi, shuning uchun ularni hal qilish vaqti keldi! :)