Javaдагы маалымат структуралары - Стек жана кезек

Салам! Бүгүн биз ар бир программист үчүн маалымат структуралары сыяктуу маанилүү нерселер жөнүндө сүйлөшөбүз . Wikipedia мындай дейт: Берorштер структурасы ( англ. data structure ) – бул эсептөөдө бир типтеги жана/же логикалык жактан байланышкан маалыматтарды сактоого жана иштетүүгө мүмкүндүк берген программалык камсыздоо. Аныктама бир аз түшүнүксүз, бирок анын маңызы түшүнүктүү. Берorштер структурасы - бул биз маалыматтарды андан ары колдонуу үчүн сактаган сактоонун бир түрү. Программалоодо маалымат структураларынын көп түрдүүлүгү бар. Көп учурда, белгилүү бир маселени чечүүдө, эң негизгиси бул максат үчүн эң ылайыктуу маалымат структурасын тандоо. Жана сиз алардын көбү менен мурунтан эле таанышсыз! Мисалы, массивдер менен . Жана ошондой эле менен Map(көбүнчө "сөздүк", "карта" же "ассоциативдик массив" деп которулат). Бул түшүнүү үчүн абдан маанилүү болуп саналат: маалымат структуралары эч кандай белгилүү бир тилге байланган эмес . Бул жөн гана абстракттуу "схемалар", ага ылайык ар бир программалоо тor өзүнүн класстарын - бул структураны ишке ашырууну түзөт. Мисалы, эң белгилүү маалымат структураларынын бири - бул шилтемеленген тизме . Википедияга кирип, анын кандай иштээри, кандай артыкчылыктары жана кемчorктери бар экенин окусаңыз болот. Сиз анын аныктамасын тааныш болушуңуз мүмкүн :) "Байланышкан тизме - бул информатикадагы негизги динамикалык берorштердин структурасы, түйүндөрдөн турган, алардын ар бири маалыматтын өзүн жана кийинкиге жана/же бир же эки шилтемени ("шилтеме") камтыйт. мурунку түйүн тизмеси" Демек, бул биздики LinkedList! Дал ушундай :) Шилтемеленген тизме маалыматтар структурасы класста Java тorнде ишке ашырылат LinkedList. Бирок башка тилдер да шилтемеленген тизмелерди ишке ашырат! Python тorнде ал “ ” деп аталат llist, Scalaда Javaдагыдай эле - “ LinkedList“ деп аталат. Шилтемеленген тизме негизги жалпы маалымат структураларынын бири болуп саналат, ошондуктан сиз анын аткарылышын каалаган заманбап программалоо тorнде таба аласыз. Ошол эле нерсе ассоциативдик массив менен. Бул жерде анын Wikipediaдагы аныктамасы: Ассоциативдик массив – бул “(ачкыч, маани)” формасындагы жуптарды сактоого мүмкүндүк берген жана жупту кошуу, ошондой эле издөө операцияларын колдогон абстрактуу маалымат түрү (маалыматтар дүкөнүнүн интерфейси). жана ачкыч менен жупту жок кылуу. Сизге эч нерсени эске салбайбы? :) Так, биз Javaists үчүн, ассоциативдик массив интерфейс болуп саналатMap. Бирок бул маалымат структурасы башка тилдерде да ишке ашырылат! Мисалы, C# программисттери аны "Сөздүк" деген ат менен бorшет. Ал эми Ruby тorнде ал "Хаш" деп аталган класста ишке ашырылат. Жалпысынан алганда, сиз мааниси эмне экенин болжол менен түшүнөсүз: маалымат структурасы - бул бардык программалоо үчүн жалпы нерсе, ал ар бир конкреттүү тилде ар кандай ишке ашырылат. Бүгүн биз эки ушундай структураны изилдеп, алар 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();
   }

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

Жогоруда айтылгандай, бизде эки стек бар: палуба жана таштанды. Стек берorштер структурасы Java ичинде ишке ашырылат java.util.Stack. Биздин карта оюнунда оюнчулардын аракеттерин сүрөттөгөн 3 ыкма бар:

• палубадан картаны алуу (ыкма getCardFromDeck());
• жок кылуу картасы (ыкмасы discard());
• жогорку картаны карагыла (ыкма lookTopCard()). Айталы, бул бонустук механик "Интеллект" болот, ал оюнчуга кийинки кайсы карта ойноорун билүүгө мүмкүндүк берет.

Биздин методдордун ичинде класстык методдор деп аталат Stack:

• push()— стектин башына элемент кошот. Биз картаны таштаганда, ал мурда ташталган карталардын үстүнө чыгат;
• pop()— стектен жогорку элементти алып салып, аны кайтарат. Бул ыкма "оюнчу картаны тартат" механикти ишке ашыруу үчүн идеалдуу.
• peek()- стектин жогорку элементин кайтарат, бирок аны стектен чыгарbyte

Оюнубуз кандай болорун карап көрөлү:

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 тorнде кезек класс менен эмес, интерфейс менен көрсөтүлөт - . Бирок, ошол эле учурда, Javaдагы кезек - бул көптөгөн ишке ашыруулары бар интерфейс. Эгерде биз Oracle documentтерин карасак, 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, бул байланышкан тизме! Туура, бирок бул анын кезек болушуна тоскоолдук кылbyte :) Бул жерде ал ишке ашырган бардык интерфейстердин тизмеси:

All Implemented Interfaces:

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

Көрүнүп тургандай, LinkedListал интерфейсти Deque- эки тараптуу кезекти ишке ашырат. Бул эмне үчүн керек? Мунун аркасында биз элементтерди башынан да, аягында да ала алабыз LinkedList. Жана ошондой эле - элементтерди башына да, аягына да кошуу. LinkedListБул жерде интерфейстен мураска калган ыкмалар Deque:

• peekFirst()— биринчи элементти кайтарат (бирок кезектен чыгарbyte).
• peekLast()— акыркы элементти кайтарат (бирок кезектен чыгарbyte).
• pollFirst()- кезектен биринчи элементти кайтарат жана аны алып салат.
• pollLast()- кезектеги акыркы элементти кайтарат жана аны алып салат.
• addFirst()— кезектин башына жаңы элементти кошот.
• addLast()— кезектин аягына элементти кошот.

Көрүнүп тургандай, LinkedListал эки тараптуу кезектин функциясын толугу менен ишке ашырат! Ал эми программада мындай функция керек болсо, аны колдонууга болорун билесиз :) Жана биздин бүгүнкү лекциябыз аяктап баратат. Акырында, мен сизге мындан ары окуу үчүн бир нече шилтеме берем. Биринчиден, PriorityQueue - "артыкчылыктуу кезек" деген макалага көңүл буруңуз . Бул кезектин эң кызыктуу жана пайдалуу ишке ашырууларынын бири. Мисалы, дүкөнүңүздө 50 адам кезекте турса жана алардын 7си VIP кардар болсо, PriorityQueueбул сизге биринчи кезекте аларды тейлөөгө мүмкүндүк берет! Абдан пайдалуу нерсе, макул эмессизби? :) Экинчиден, Роберт Лафореттин "Явадагы берorштердин структуралары жана алгоритмдери" китебин дагы бир жолу айтып коюу ашыкча болбойт . Китепти окуп жатып, сиз көптөгөн маалымат структураларын (анын ичинде стек жана кезек) үйрөнүп тим болбостон, алардын көбүн өзүңүз да ишке ашырасыз! Мисалы, Javaда Stack классы жок болсо элестетиңиз. Сиздин программаңыз үчүн ушундай маалымат структурасы керек болсо эмне кылат элеңиз? Албетте, мен өзүм жазыш керек болчу. Laforet китебин окуп жатканда , сиз эмне кыласыз. Ушунун аркасында, маалымат структураларын түшүнүүңүз жөн гана теорияны изилдөөгө караганда алда канча кененирээк болот :) Биз бүгүн теория менен бүттүк, бирок практикасыз теория эч нерсе эмес! Көйгөйлөр өзүнөн өзү чечилбейт, андыктан аларды чечүүгө убакыт келди! :)