Структуры данных в Java — стек и очередь

Привет! Сегодня поговорим о таких важных для любого программиста вещах как структуры данных. Википедия гласит: Структура данных (англ. 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 карты из колоды
       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='Эдвин ван Клифф'}

И снова мы видим как работает стек! Сброс в нашей игре тоже является стеком (как и колода). “Эдвин ван Клифф” был сброшен первым. Вторым был сброшен “Миллхаус Манашторм” — и лег поверх Эдвина в сбросе. Далее была сброшена Сильвана — и эта карта легла уже поверх Миллхауса. Как видишь, ничего сложного в работе стека нет. Тем не менее, знать эту структуру данных необходимо — о ней довольно часто спрашивают на собеседованиях, а на ее основе нередко строятся более сложных структуры данных.

Очередь (Queue)

Очередь (или, по-английски, “Queue”) — еще одна распространенная структура данных. Также как стек она реализована во многих языках программирования, в том числе и в Java. В чем же отличие очереди от стека? Ее очередь основана не на LIFO, а на другом принципе — FIFO (“first in — first out”, “первым вошел — первым вышел”). Его легко понять, взяв для примера...да хотя бы обычную, настоящую очередь из реальной жизни! Например, очередь в магазин. Если в очереди стоит пять человек, первым в магазин попадет тот, кто встал в очередь первым. Если еще один человек (помимо пяти в очереди) захочет что-то купить и встанет в очередь, то в магазин он попадает последним, то есть шестым. При работе с очередью новые элементы добавляются в конец, а если ты хочешь получить элемент, он будет взят из начала. Это основной принцип ее работы, который нужно запомнить Принцип работы очереди очень легко понять интуитивно, поскольку она часто встречается в реальной жизни. Стоит отдельно заметить, что в 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 — это двусторонняя очередь. Она расширяет функционал обычной очереди, позволяя добавлять элементы на оба края (в начало и конец очереди) и забирать элементы с обоих краев очереди. Двусторонняя очередь широко используется в разработке. Обрати внимание на список классов-очередей, которые мы привели выше. Список довольно велик, но нет ли там чего-то знакомого для нас?

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. Что бы ты делал, если бы тебе понадобилась такая структура данных для твоей программы? Конечно, пришлось бы написать ее самому. При чтении книги Лафоре ты часто именно этим и будешь заниматься. Благодаря этому твое понимание структур данных будет намного шире, чем при простом изучении теории :) С теорией мы на сегодня закончили, но теория без практики — ничто! Задачи сами себя не решат, так что самое время взяться за них! :)