Структури даних – стек і черга

Привіт! Сьогодні поговоримо про такі важливі для будь-якого програміста речі як структури даних. Вікіпедія свідчить: Структура даних(англ. data structure) – програмна одиниця, що дає змогу зберігати й обробляти безліч однотипних і/або логічно пов'язаних даних в обчислювальній техніці. Визначення трохи заплутане, але суть його зрозуміла. Структура даних – це таке своєрідне сховище, де ми тримаємо дані для подальшого використання. У програмуванні існує величезна кількість різноманітних структур даних. Дуже часто під час розв'язання конкретного завдання найголовніше – обрання найбільш доцільної для цього структури даних. І з багатьма з них ти вже знайомий! Наприклад, із масивами. А також із Map (яку зазвичай перекладають як "словник", "карта" або "асоціативний масив"). Дуже важливо розуміти: структури даних не прив'язані до якоїсь конкретної мови. Це просто абстрактні "креслення", за якими кожна мова програмування створює свої власні класи – реалізації цієї структури. Наприклад, одна з найвідоміших структур даних – зв'язний список. Ти можеш зайти у вікіпедію, почитати про те, як він влаштований, які в нього є переваги і недоліки. Можливо, тобі здасться знайомим його визначення :) "Зв'язний список – базова динамічна структура даних в інформатиці, що складається з вузлів, кожен з яких містить як власне дані, так і одне або два посилання («зв'язки») на наступний та/або попередній вузол списку" Так це ж наш LinkedList! Точно , так воно і є :) Структура даних "зв'язний список" реалізована в мові Java в класі LinkedList. Але і в інших мовах зв'язний список теж реалізовано! У Python він називається "llist", у Scala називається так само, як у Java – "LinkedList". Зв'язний список – одна з базових поширених структур даних, тому її реалізацію ти знайдеш у будь-якій сучасній мові програмування. Те саме з асоціативним масивом. Ось його визначення з Вікіпедії: Асоціативний масив – абстрактний тип даних (інтерфейс до сховища даних), що дає змогу зберігати пари у формі "(ключ, значення)" і підтримує операції додавання пари, а також пошуку і видалення пари за ключем. Нічого не нагадує? :) Точно, для нас, джавістів, асоціативний масив – це інтерфейс Map. Але ця структура даних реалізована і в інших мовах! Наприклад, програмісти на C# знають його під назвою "Dictionary". А в мові Ruby він реалізований у класі під назвою "Hash". Загалом, ти приблизно зрозумів, у чому сенс: структура даних – це така загальна для всього програмування штука, яка реалізується по-своєму в кожній конкретній мові. Сьогодні ми вивчимо дві такі структури і подивимося, як вони реалізовані в Java – стек і чергу.

Стек у Java

Стек – це відома структура даних. Вона дуже проста і досить багато предметів з нашого повсякденного життя "реалізовані" як стек. Уяви собі просту ситуацію: ти живеш у готелі, і протягом дня тобі надходили ділові листи. Оскільки тебе в цей час не було в номері, службовець готелю просто складав листи, що приходили, на твій стіл. Спочатку він поклав на стіл перший лист. Потім прийшов другий, і він поклав його поверх першого. Третій лист, що прийшов, він поклав поверх другого, а четвертий – поверх третього. А тепер відповідай на просте запитання: який лист ти прочитаєш першим, коли прийдеш у номер і побачиш стіс на столі? Правильно, ти прочитаєш верхній лист. Тобто той, який прийшов останнім за часом. Саме так і працює стек. Такий принцип роботи називається LIFO – "last in – first out" ("останнім прийшов – першим вийшов"). Для чого може стати в пригоді стек? Наприклад, ти створюєш на 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 карти з колоди
       Картка card1 = game.getCardFromDeck();
       Картка card2 = game.getCardFromDeck();
       Картка 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 з них. Які ж карти йому дісталися? Виведення в консоль: Зверни увагу, в якому порядку карти були виведені в консоль. Карта "Едвін ван Кліфф" у колоду потрапила останньою (п'ятою за ліком), і саме її гравець узяв першою. "Міллхаус" потрапив у колоду передостаннім, і його гравець узяв другим. "Сільвана" потрапила в колоду третьою з кінця, і дісталася гравцеві третьою. Далі гравець скидає карти. Спочатку він скидає Едвіна, потім Міллхауса, потім Сільвану. Після чого ми почергово виводимо в консоль карти, які лежать у нас у зносі: Виведення в консоль: І знову ми бачимо як працює стек! Знос в нашій грі теж є стеком (як і колода). "Едвін ван Кліфф" був скинутий першим. Другим був скинутий "Міллхаус Манашторм" – і ліг поверх Едвіна в зносі. Далі була скинута Сільвана – і ця карта лягла вже поверх Міллхауса. Як бачиш, нічого складного в роботі стека немає. Проте знати цю структуру даних необхідно – про неї досить часто запитують на співбесідах, а на її основі нерідко будують складніші структури даних.

Черга (Queue)

Черга (або, англійською, "Queue") – ще одна поширена структура даних. Так само як стек її реалізовано в багатьох мовах програмування, зокрема і в Java. У чому ж відмінність черги від стека? Її черга ґрунтується не на LIFO, а на іншому принципі – FIFO ("first in – first out", "першим увійшов – першим вийшов"). Його легко зрозуміти, взявши для прикладу...та хоча б звичайну, справжню чергу з реального життя! Наприклад, черга в магазин. Якщо в черзі стоїть п'ятеро людей, першим до магазину потрапить той, хто встав у чергу першим. Якщо ще одна людина (крім п'яти в черзі) захоче щось купити і встане в чергу, то в магазин вона потрапляє останньою, тобто шостою. Під час роботи з чергою нові елементи додаються в кінець, а якщо ти хочеш отримати елемент, він буде взятий з початку. Це основний принцип її роботи, який потрібно запам'ятати: Принцип роботи черги дуже легко зрозуміти інтуїтивно, оскільки вона часто трапляється в реальному житті. Варто окремо зауважити, що в Java чергу представлено не класом, а інтерфейсом – Queue. Але водночас черга в Java – це інтерфейс, у якого є дуже багато реалізацій. Якщо ми зазирнемо в документацію Oracle, то побачимо, що від черги успадковуються 4 різні інтерфейси, і вкрай значний список класів: Який великий список! Але, звісно, тобі не потрібно заучувати всі ці класи та інтерфейси зараз – голова може лопнути :) Ми розглянемо лише декілька найважливіших і найцікавіших моментів. По-перше, звернемо увагу на один із чотирьох "суб-інтерфейсів" черги – Deque. Чим він примітний? Deque – це двостороння черга. Вона розширює функціонал звичайної черги, даючи змогу додавати елементи на обидва краї (на початок і кінець черги) і забирати елементи з обох країв черги. Двостороння черга широко використовується в розробці. Зверни увагу на список класів-черг, які ми навели вище. Список досить великий, але чи немає там чогось знайомого для нас? Ха, так тут же наш старий знайомий – LinkedList! Тобто він імплементує інтерфейс Queue? Але як він може бути чергою? Адже LinkedList – це зв'язний список! Правильно, але це ніяк не заважає йому бути чергою :) Ось список усіх інтерфейсів, які він реалізує: Як бачиш, LinkedList реалізує інтерфейс Deque – двосторонню чергу. Навіщо це потрібно? Завдяки цьому ми можемо отримувати елементи і з початку, і з кінця LinkedList. А ще – додавати елементи і в початок, і в кінець. Ось які методи дісталися LinkedList від інтерфейсу Deque:

• peekFirst() – повертає (але не видаляє з черги) перший елемент.
• peekLast() – повертає (але не видаляє з черги) останній елемент.
• pollFirst() – повертає перший елемент із черги і видаляє його.
• pollLast() – повертає останній елемент із черги і видаляє його.
• addFirst() – додає новий елемент на початок черги.
• addLast() – додає елемент у кінець черги.

Як бачиш, LinkedList повною мірою реалізує функціонал двосторонньої черги! І якщо такий функціонал знадобиться в програмі, знатимеш, що його можна використовувати :) А наша сьогоднішня лекція добігає кінця. Наостанок я дам тобі кілька посилань для додаткового читання. По-перше, зверни увагу на статтю, присвячену PriorityQueue – "пріоритетній черзі". Це одна з найцікавіших і найкорисніших реалізацій Queue. Наприклад, якщо в черзі до твого магазину стоять 50 осіб, і 7 з них є VIP-клієнтами, PriorityQueue дасть тобі змогу обслужити їх першочергово! Дуже корисна штука, згоден? :) По-друге, не буде зайвим ще раз згадати книгу Роберта Лафоре "Структури даних і алгоритми мовою Java". Під час читання книги ти не тільки вивчиш багато структур даних (включно зі стеком і чергою), а й самостійно реалізуєш багато з них! Уяви, наприклад, що в Java не було б класу Stack. Що б ти робив, якби тобі знадобилася така структура даних для твоєї програми? Звісно, довелося б написати її самому. Під час читання книги Лафоре ти часто саме цим і будеш займатися. Завдяки цьому твоє розуміння структур даних буде набагато ширшим, ніж при простому вивченні теорії :) З теорією ми на сьогодні закінчили, але теорія без практики – ніщо! Завдання самі себе не вирішать, тож саме час взятися за них! :)