Сохторҳои додаҳо дар Java - Стек ва навбат

Салом! Имрӯз мо дар бораи чунин чизҳои муҳим барои ҳар як барномасоз ба монанди сохторҳои додаҳо сӯҳбат хоҳем кард . Википедиа мегӯяд: Сохтори додаҳо ( англ. сохтори додаҳо ) як воҳиди нармафзорест, ки ба шумо имкон медиҳад, ки миқдори зиёди як навъ ва/ё маълумоти мантиқӣ алоқамандро дар компютер ҳифз ва коркард кунед. Таъриф андаке печида бошад хам, вале мохияти он равшан аст. Сохтори додаҳо як навъ нигоҳдорӣ мебошад, ки дар он мо маълумотро барои истифодаи минбаъда нигоҳ медорем. Дар барномасозӣ намудҳои зиёди сохторҳои додаҳо мавҷуданд. Аксар вақт, ҳангоми ҳалли як масъалаи мушаххас, чизи аз ҳама муҳим ин интихоби сохтори мувофиқтарин барои ин мақсад аст. Ва шумо аллакай бо бисёре аз онҳо шинос ҳастед! Масалан, бо массивҳо . Ва инчунин бо Map(ки одатан ҳамчун "лугат", "харита" ё "массиви ассотсиативӣ" тарҷума мешавад). Фаҳмидани он хеле муҳим аст: сохторҳои додаҳо ба ягон забони мушаххас алоқаманд нестанд . Инҳо танҳо "нақшаҳои" абстрактӣ мебошанд, ки мувофиқи онҳо ҳар як забони барномасозӣ синфҳои худро эҷод мекунад - татбиқи ин сохтор. Масалан, яке аз сохторҳои машҳуртарини додаҳо рӯйхати алоқаманд аст . Шумо метавонед ба Википедиа равед, бихонед, ки он чӣ гуна кор мекунад, кадом бартариятҳо ва нуқсонҳои он дорад. Шояд шумо таърифи онро шинос ёбед :) "Рӯйхати алоқаманд ин сохтори асосии динамикии додаҳо дар илми информатика мебошад, ки аз гиреҳҳо иборат аст, ки ҳар яки онҳо ҳам худи маълумот ва ҳам як ё ду истинод ("пайванд") ба дигар ва/ё пайванд доранд. Рӯйхати гиреҳҳои қаблӣ" Пас ин аз они мост LinkedList! Маҳз ҳамин тавр аст :) Сохтори маълумоти рӯйхати алоқаманд бо забони Java дар синф амалӣ карда мешавад LinkedList. Аммо забонҳои дигар низ рӯйхатҳои алоқамандро амалӣ мекунанд! Дар Python онро “ llist”, дар Scala ҳамон тавре меноманд, ки дар Java - “ LinkedList“. Рӯйхати алоқаманд яке аз сохторҳои асосии умумии додаҳо мебошад, бинобар ин шумо метавонед татбиқи онро дар ҳама забони барномасозии муосир пайдо кунед. Ҳамин чиз бо массиви ассотсиативӣ. Ин аст таърифи он аз Википедиа: Массиви ассотсиативӣ як намуди абстрактии додаҳо (интерфейс барои анбори додаҳо) мебошад, ки имкон медиҳад ҷуфтҳои шакли "(калид, арзиш)" нигоҳ дошта шавад ва амалиёти илова кардани ҷуфт, инчунин ҷустуҷӯро дастгирӣ кунад. ва нест кардани як ҷуфт ба воситаи калид. Оё ба шумо чизеро хотиррасон намекунад? :) Маҳз, барои мо Javaists, массиви ассотсиативӣ интерфейс астMap. Аммо ин сохтори додаҳо бо забонҳои дигар низ амалӣ карда мешавад! Масалан, барномасозони C# онро бо номи "Луғат" медонанд. Ва дар забони руби он дар синф бо номи "Хаш" амалӣ карда мешавад. Умуман, шумо тахминан фаҳмед, ки маъно чист: сохтори додаҳо як чизи умумӣ барои ҳама барномасозӣ аст, ки дар ҳар як забони мушаххас ба таври гуногун амалӣ карда мешавад. Имрӯз мо ду чунин сохторро меомӯзем ва мебинем, ки онҳо дар Java чӣ гуна татбиқ мешаванд - стек ва навбат.

Стек дар Java

Стек сохтори маълуми додаҳост. Ин хеле содда аст ва бисёр an objectҳои ҳаёти ҳаррӯзаи мо ҳамчун стек "амалӣ карда мешаванд". Вазъияти оддиро тасаввур кунед: шумо дар мехмонхона зиндагй мекунед ва рузона мактубхои тичоратй мегиред. Азбаски шумо дар он вақт дар ҳуҷра набудед, корманди меҳмонхона танҳо мактубҳои воридшударо рӯи мизи шумо мегузорад. Аввал харфи аввалро ба руи миз гузошт. Баъд дуюмаш омад ва ба болои аввал гузошт. Ҳарфи сеюмро, ки дар болои дуюм омада буд, ва чорумро дар болои сеюм гузошт. Акнун, ба як саволи оддӣ ҷавоб диҳед: вақте ки шумо ба ҳуҷраи худ меоед ва дар рӯи миз стекро мебинед, кадом ҳарфро аввал мехонед ? Дуруст, шумо ҳарфи болоро хонед . Яъне он касе, ки дар вақташ охирин омад . Маҳз ҳамин тавр стек кор мекунад. Ин принсипи кор 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()). Биёед бигӯем, ки ин механикаи бонуси "Интеллект" хоҳад буд, ки ба плеер имкон медиҳад фаҳмад, ки кадом корт дар оянда ба бозӣ меояд.

Дар дохor усулҳои мо усулҳои синфӣ номида мешаванд 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());
   }
}

Ҳамин тавр, мо ба саҳни худ панҷ корт илова кардем. Бозингари аввал 3-тоашро гирифт. Ӯ чӣ кортҳоро гирифт? Натиҷаи консол:

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

Ба тартибе, ки кортҳо ба консол бароварда шудаанд, диққат диҳед. Корти "Эдвин Ван Клифф" охирин кортест, ки ба саҳни майдон зад (панҷумин паиҳам) ва он кортест, ки плеер аввалин шуда гирифт. «Михлаус» дуюмин дар саҳни охирин буд ва бозигари он дуюмро гирифт. «Силванас» аз охир ба саҳни сеюм зада, ба бозигари сеюм рафт. Баъдан, бозигар кортҳои худро мепартояд. Аввал Эдвинро мепартояд, баъд Миллхаус, баъд Силванас. Пас аз он мо як ба як ба консол кортҳоеро, ки дар партови мо ҳастанд, мебарорем: Баромад ба консол:

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

Ва боз мо мебинем, ки стек чӣ гуна кор мекунад! Партофтан дар бозии мо низ як стек аст (мисли саҳни). "Эдвин Ван Клифф" аввалин шуда партофта шуд. Дуюме, ки партофта шуд "Millhouse Manastorm" буд - ва дар болои Эдвин дар партов хобид. Баъдан, Силванас партофта шуд - ва ин корт дар болои Миллхаус гузошта шуд. Тавре ки шумо мебинед, дар бораи чӣ гуна кор кардани стек ҳеҷ чизи мушкиле нест. Бо вуҷуди ин, донистани ин сохтори додаҳо зарур аст - аксар вақт дар мусоҳибаҳо дар бораи он мепурсанд ва сохторҳои мураккабтари додаҳо аксар вақт дар асоси он сохта мешаванд.

Навбат

Навбат (ё ба забони англисӣ, "навбат") сохтори дигари маъмули додаҳост. Мисли стек, он дар бисёр забонҳои барномасозӣ, аз ҷумла Java амалӣ карда мешавад. Фарқи байни навбат ва стек чист? Навбати он на ба LIFO, балки ба принсипи дигар асос ёфтааст - FIFO («аввал дар - аввал мебарояд», «аввал дар - аввал мебарояд») . Фаҳмидани он осон аст, мисол мегирем... ё ҳадди аққал як навбати оддӣ, воқеӣ аз ҳаёти воқеӣ! Масалан, навбат ба магазин. Агар панҷ нафар дар навбат бошанд, шахси аввал дар навбат ба мағоза ворид мешавад . Агар боз як нафар (ғайр аз панҷ нафари навбатдор) чизе хариданӣ шавад ва ба навбат нишинад, пас ӯ ба мағоза дар охир , яъне шашум ворид мешавад. Ҳангоми кор бо навбат ба охир элементҳои нав илова карда мешаванд ва агар шумо хоҳед, ки элемент гиред, он аз аввал гирифта мешавад. Ин аст принципи асосии кори он, ки шумо бояд онро дар хотир доред Принсипи навбатро ба таври интуитивӣ фаҳмидан хеле осон аст, зеро он дар ҳаёти воқеӣ аксар вақт дучор мешавад. Бояд алоҳида қайд кард, ки дар Java навбат на бо синф, балки бо интерфейси - Queue. Аммо дар айни замон, навбат дар Java интерфейсест, ки татбиқи зиёде дорад. Агар мо ба ҳуҷҷатҳои Oracle назар андозем, мо мебинем, ки 4 интерфейси гуногун ва рӯйхати бениҳоят таъсирбахши синфҳо аз навбат мерос гирифта шудаанд:

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— Ин навбат дутарафа аст. Он функсияи навбати муқаррариро васеъ мекунад, ки ба шумо имкон медиҳад, ки ба ҳарду канори навбат элементҳо илова кунед (оғоз ва охири навбат) ва элементҳоро аз ҳарду канори навбат гиред. 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 - "навбати афзалиятнок" диққат диҳед . Ин яке аз татбиқи ҷолибтарин ва муфиди Queue мебошад. Масалан, агар дар мағозаи шумо 50 нафар дар навбат бошанд ва 7 нафари онҳо муштариёни VIP бошанд, PriorityQueueин ба шумо имкон медиҳад, ки аввал ба онҳо хизмат кунед! Як чизи хеле муфид, оё шумо розӣ нестед? :) Сониян, бори дигар ёдовар шудан аз китоби Роберт Лафоре «Структураи додаҳо ва алгоритмҳо дар Java» зиёдатӣ нахоҳад буд . Ҳангоми хондани китоб шумо на танҳо сохторҳои зиёди маълумотро (аз ҷумла стек ва навбат) меомӯзед, балки бисёре аз онҳоро худатон низ амалӣ хоҳед кард! Масалан, тасаввур кунед, ки агар Java синфи Stack надошт. Агар ба шумо чунин сохтори додаҳо барои барномаи шумо лозим бошад, шумо чӣ кор мекардед? Албатта, ман бояд онро худам нависам. Ҳангоми хондани китоби Лафоре, шумо аксар вақт ин корро мекунед. Ба шарофати ин, фаҳмиши шумо дар бораи сохторҳои додаҳо нисбат ба омӯзиши назария хеле васеътар хоҳад буд :) Мо имрӯз бо назария тамом шудем, аммо назария бидуни амалия ҳеҷ чиз нест! Проблемаҳо худашон ҳал намешаванд, бинобар ин ҳоло вақти ҳалли онҳо аст! :)