Java тіліндегі деректер құрылымдары – стек және кезек

Сәлеметсіз бе! Бүгін біз кез келген бағдарламашы үшін деректер құрылымдары сияқты маңызды нәрселер туралы сөйлесетін боламыз . Википедия былай дейді: Деректер құрылымы ( ағылш. деректер құрылымы ) – есептеуіште бір типті және/немесе логикалық байланысқан көптеген деректерді сақтауға және өңдеуге мүмкіндік беретін бағдарламалық құрал. Анықтамасы аздап түсініксіз, бірақ оның мәні түсінікті. Деректер құрылымы - бұл деректерді әрі қарай пайдалану үшін сақтайтын сақтаудың бір түрі. Бағдарламалауда деректер құрылымдарының алуан түрлілігі бар. Көбінесе белгілі бір мәселені шешу кезінде ең бастысы осы мақсат үшін ең қолайлы деректер құрылымын таңдау болып табылады. Ал сіз олардың көпшілігімен бұрыннан таныссыз! Мысалы, массивтермен . Сондай-ақ Map(ол әдетте «сөздік», «карта» немесе «ассоциативті массив» деп аударылады). Түсіну өте маңызды: деректер құрылымдары ешқандай белгілі бір тілге байланысты емес . Бұл жай абстрактілі «сызбалар», соған сәйкес әрбір бағдарламалау тілі өз сыныптарын жасайды - осы құрылымды іске асыру. Мысалы, ең танымал деректер құрылымдарының бірі байланыстырылған тізім болып табылады . Сіз Википедияға кіріп, оның қалай жұмыс істейтіні, қандай артықшылықтар мен кемшіліктер бар екендігі туралы оқи аласыз. Сізге оның анықтамасы таныс болуы мүмкін :) «Байланыстырылған тізім – бұл әр қайсысында деректердің өзі де, келесіге және/немесе бір немесе екі сілтеме («сілтемелер») бар түйіндерден тұратын информатикадағы негізгі динамикалық деректер құрылымы алдыңғы түйіндер тізімі» Демек, бұл біздікі LinkedList! Дәл солай :) Байланыстырылған тізім деректер құрылымы сыныпта Java тілінде жүзеге асырылады LinkedList. Бірақ басқа тілдер де байланыстырылған тізімдерді жүзеге асырады! Python тілінде ол « » деп аталады llist, Scala тілінде Java тіліндегідей « LinkedList» деп аталады. Байланыстырылған тізім негізгі жалпы деректер құрылымдарының бірі болып табылады, сондықтан оның орындалуын кез келген заманауи бағдарламалау тілінде табуға болады. Ассоциативті массивпен бірдей нәрсе. Міне, оның Уикипедиядағы анықтамасы: Ассоциативті массив – «(кілт, мән)» пішінінің жұптарын сақтауға мүмкіндік беретін және жұпты қосу, сонымен қатар іздеу операцияларын қолдайтын дерексіз деректер түрі (деректер қоймасының интерфейсі). және жұпты перне арқылы жою. Сізге ештеңені еске түсірмейді ме? :) Дәл біз Javaists үшін ассоциативті массив интерфейс болып табыладыMap. Бірақ бұл деректер құрылымы басқа тілдерде де жүзеге асырылады! Мысалы, C# тіліндегі бағдарламашылар оны «Сөздік» деген атпен біледі. Ал Ruby тілінде ол «Хэш» деп аталатын сыныпта жүзеге асырылады. Жалпы алғанда, сіз мағынасының не екенін шамамен түсінесіз: деректер құрылымы - бұл әр нақты тілде әртүрлі жүзеге асырылатын барлық бағдарламалауға ортақ нәрсе. Бүгін біз осындай екі құрылымды зерттейміз және олардың Java тілінде қалай жүзеге асырылатынын көреміз - стек пен кезек.

Java тіліндегі стек

Стек - белгілі деректер құрылымы. Бұл өте қарапайым және біздің күнделікті өміріміздегі көптеген нысандар стек ретінде «жүзеге асырылады». Қарапайым жағдайды елестетіп көріңіз: сіз қонақ үйде тұрасыз, ал күндіз сіз іскерлік хаттарды аласыз. Сіз ол кезде бөлмеде болмағандықтан, қонақүй қызметкері келген хаттарды жай ғана үстеліңізге қойды. Алдымен үстелдің үстіне бірінші әріпті қойды. Сосын екіншісі келіп, біріншісінің үстіне қойды. Ол келген үшінші әріпті екіншісінің үстіне, төртіншісін үшіншінің үстіне қойды. Енді қарапайым сұраққа жауап беріңіз: бөлмеңізге келіп, үстелдің үстіндегі дестекті көргенде бірінші қай әріпті оқисыз ? Дұрыс, жоғарғы әріпті оқисыз. Яғни, уақытында соңғы келген . Стек дәл осылай жұмыс істейді. Бұл жұмыс принципі LIFO деп аталады - «соңғы кірген - бірінші шығады» («соңғы кірген, бірінші шығады»). Стек не үшін пайдалы болуы мүмкін? Мысалы, сіз Java тілінде карта ойынының қандай да бір түрін жасап жатырсыз. Үстелде карталар палубасы жатыр. Ойналған карталар жойылады. Палубаны да, тастауды да екі стектің көмегімен жүзеге асыруға болады. Ойыншылар карталарды палубаның жоғарғы жағынан тартады - әріптермен бірдей принцип. Ойыншылар карталарды тастаған кезде, ескі карталардың үстіне жаңа карталар қойылады. Стек арқылы жүзеге асырылған ойынымыздың бірінші жобасы мынандай болады:

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

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

Жоғарыда айтқанымыздай, бізде екі стек бар: палуба және тастау. Стек деректер құрылымы Java тілінде іске асырылады java.util.Stack. Біздің карта ойынында ойыншылардың әрекеттерін сипаттайтын 3 әдіс бар:

• палубадан картаны алу (әдіс getCardFromDeck());
• картаны тастау (әдіс discard());
• жоғарғы картаға қараңыз (әдіс lookTopCard()). Айталық, бұл ойыншыға келесі карта ойнайтынын білуге ​​мүмкіндік беретін бонустық механик «Интеллект» болады.

Біздің әдістеріміздің ішінде класс әдістері деп аталады Stack:

• push()— стектің жоғарғы жағына элемент қосады. Біз картаны тастаған кезде, ол бұрын лақтырылған карталардың үстіне шығады;
• pop()— стектен жоғарғы элементті алып тастап, оны қайтарады. Бұл әдіс «ойыншы картаны тартады» механикті жүзеге асыру үшін өте қолайлы.
• peek()- стектің жоғарғы элементін қайтарады, бірақ оны стектен алып тастамайды

Ойынымыз қалай жұмыс істейтінін көрейік:

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

Сонымен, біз палубаға бес карта қостық. Бірінші ойыншы оның үшеуін алды. Ол қандай карталар алды? Консоль шығысы:

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

Карталардың консольге шығу ретіне назар аударыңыз. «Эдвин Ван Клейфф» картасы палубаға соңғы тиген (қатарынан бесінші) және ойыншы бірінші алған карта болды. «Михлаус» палубада соңғы болып екінші болды, ал оның ойыншысы екінші болды. «Сильванас» палубаға соңынан үшінші соқты да, үшінші ойыншыға кетті. Содан кейін ойыншы өз карталарын тастайды. Алдымен Эдвинді, содан кейін Миллхаусты, содан кейін Сильванасты түсіреді. Содан кейін біз бір-бірден консольге шығарамыз, оларда жоқ карталарды шығарамыз: Консольге шығарамыз:

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

Тағы да біз стек қалай жұмыс істейтінін көреміз! Біздің ойынымыздағы тастау да стек болып табылады (палубада сияқты). Бірінші болып «Эдвин Ван Клифф» түсірілді. Екінші түсірілгені «Millhouse Manastorm» болды және Эдвиннің үстіне тасталды. Содан кейін Сильванас тасталды - және бұл карта Миллхаустың үстінде жатты. Көріп отырғаныңыздай, стек қалай жұмыс істейтіні туралы күрделі ештеңе жоқ. Дегенмен, бұл деректер құрылымын білу қажет - бұл туралы сұхбатта жиі сұралады және оның негізінде күрделірек деректер құрылымдары жиі құрастырылады.

Кезек

Кезек (немесе ағылшын тілінде «Кезек») басқа кең таралған деректер құрылымы болып табылады. Стек сияқты ол көптеген бағдарламалау тілдерінде, соның ішінде Java-да жүзеге асырылады. Кезек пен стектің айырмашылығы неде? Оның кезегі LIFO-ға негізделмейді, бірақ басқа принцип бойынша - FIFO («бірінші кірген - бірінші шығады», «бірінші кірген - бірінші шығады») . Түсіну оңай, мысал ретінде ... немесе, кем дегенде, нақты өмірден қарапайым, нақты кезек! Мысалы, дүкенге кезек. Кезекте бес адам болса, дүкенге бірінші кезекте тұрған адам кіреді . Егер тағы бір адам (кезекте тұрған бес адамнан басқа) бірдеңе сатып алғысы келіп, кезекке тұрса, ол дүкенге соңғы , яғни алтыншы болып кіреді. Кезекпен жұмыс істегенде соңына жаңа элементтер қосылады, ал егер элементті алғың келсе, ол басынан алынады. Бұл оның жұмыс істеуінің негізгі принципі, оны есте сақтау қажет.Кезек принципін интуитивті түсіну өте оңай, өйткені ол нақты өмірде жиі кездеседі. Java тілінде кезек класспен емес, интерфейс арқылы бейнеленетінін бөлек атап өткен жөн . Бірақ сонымен бірге Java-дағы кезек - бұл көптеген іске асырулары бар интерфейс. Егер Oracle құжаттамасын қарасақ, кезектен 4 түрлі интерфейс және өте әсерлі сыныптар тізімі мұраланғанын көреміз: Queue

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

Қандай үлкен тізім! Бірақ, әрине, қазір барлық осы сыныптар мен интерфейстерді жаттап алудың қажеті жоқ - сіздің басыңыз жарылып кетуі мүмкін :) Біз ең маңызды және қызықты сәттердің бірнешеуін ғана қарастырамыз. Алдымен кезектің төрт «ішкі интерфейсінің» біріне назар аударайық - Deque. Оның ерекшелігі неде? Deque– Бұл екі жақты кезек. Ол элементтерді екі ұшына (кезектің басы мен соңы) қосуға және кезектің екі басынан элементтерді алуға мүмкіндік беру арқылы қалыпты кезектің функционалдығын кеңейтеді. Деке әзірлеуде кеңінен қолданылады. Жоғарыда біз берген кезек кластарының тізіміне назар аударыңыз. Тізім өте ұзақ, бірақ бізге таныс нәрсе бар ма?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ха, біздің ескі досымыз осында LinkedList! Яғни, ол интерфейсті жүзеге асырады Queue? Бірақ ол қалай кезек бола алады? Өйткені LinkedList, бұл қосылған тізім! Рас, бірақ бұл оның кезек болуын тоқтатпайды :) Мұнда ол жүзеге асыратын барлық интерфейстердің тізімі берілген:

All Implemented Interfaces:

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

Көріп отырғаныңыздай, LinkedListол интерфейсті Deque- екі жақты кезекті жүзеге асырады. Бұл не үшін қажет? Осының арқасында біз элементтерді басынан да, аяғынан да ала аламыз LinkedList. Сондай-ақ - элементтерді басына да, соңына да қосыңыз. LinkedListМіне, интерфейстен мұраға алынған әдістер Deque:

• peekFirst()— бірінші элементті қайтарады (бірақ кезектен алып тастамайды).
• peekLast()— соңғы элементті қайтарады (бірақ кезектен алып тастамайды).
• pollFirst()- бірінші элементті кезектен қайтарады және оны жояды.
• pollLast()- кезектен соңғы элементті қайтарады және оны жояды.
• addFirst()— кезектің басына жаңа элемент қосады.
• addLast()— кезектің соңына элемент қосады.

Көріп отырғаныңыздай, LinkedListол екі жақты кезектің функционалдығын толығымен жүзеге асырады! Ал егер мұндай функционалдылық бағдарламада қажет болса, оны пайдалануға болатынын білесіз :) Ал бүгінгі лекциямыз аяқталуға жақын. Соңында мен сізге қосымша оқу үшін бірнеше сілтеме беремін. Біріншіден, PriorityQueue - «басымдық кезек» мақаласына назар аударыңыз . Бұл кезектің ең қызықты және пайдалы іске асыруларының бірі. Мысалы, сіздің дүкеніңізде кезекте 50 адам болса және олардың 7-і VIP клиент болса, PriorityQueueбұл сізге алдымен оларға қызмет көрсетуге мүмкіндік береді! Өте пайдалы нәрсе, келісесіз бе? :) Екіншіден, Роберт Лафоренің «Java тіліндегі деректер құрылымдары мен алгоритмдері» кітабын тағы бір рет атап өту артық болмас еді . Кітапты оқу барысында сіз көптеген деректер құрылымдарын (стек пен кезекті қоса) біліп қана қоймай, олардың көпшілігін өзіңіз де жүзеге асырасыз! Мысалы, Java-да Stack сыныбы болмағанын елестетіп көріңіз. Бағдарламаңыз үшін осындай деректер құрылымы қажет болса, не істер едіңіз? Әрине, оны өзім жазуым керек еді. Лафоренің кітабын оқығанда , сіз мұны жиі жасайсыз. Осының арқасында деректер құрылымдары туралы түсінігіңіз жай ғана теорияны оқып-үйренуден әлдеқайда кеңірек болады :) Біз бүгінде теориямен бітті, бірақ практикасыз теория ештеңе емес! Мәселелер өздігінен шешілмейді, сондықтан оларды шешудің уақыты келді! :)