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

Привет! Сегодня поговорим о таких важных для любого программиста вещах как структуры данных. Если совсем коротко: стек это структура данных, которая работает по принципу LIFO, то есть последний положенный элемент забирается первым. Очередь работает наоборот, по принципу FIFO: первым уходит тот элемент, который положили раньше всех. В Java стек это класс java.util.Stack, который в новом коде обычно заменяют на ArrayDeque, а очередь это интерфейс Queue с целым набором реализаций, среди которых ArrayDeque, LinkedList и PriorityQueue. Дальше разберем обе структуры по порядку и с примерами.

Кратко

• Структура данных это абстрактный чертеж хранения данных, а не свойство языка: связный список, стек и очередь есть в любом современном языке, просто под разными именами.
• Стек работает по LIFO: push() кладет элемент наверх, pop() снимает верхний и возвращает его, peek() показывает верхний, не снимая.
• Очередь работает по FIFO: новые элементы встают в хвост, а забираются из головы.
• В Java стек это класс java.util.Stack, а очередь это интерфейс Queue, у которого 4 подинтерфейса и 13 классов-реализаций.
• Deque это двусторонняя очередь: добавлять и забирать элементы можно с обоих концов.
• LinkedList одновременно и список, и очередь: он реализует List и Deque, поэтому умеет addFirst(), addLast(), pollFirst() и pollLast().

Что такое структура данных

Википедия гласит: Структура данных (англ. data structure) это программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Определение немного запутанное, но суть его ясна. Структура данных это такое своеобразное хранилище, где мы держим данные для дальнейшего использования. В программировании существует огромное количество разнообразных структур данных. Очень часто при решении конкретной задачи самое главное это выбор наиболее подходящей для этого структуры данных. И со многими из них ты уже знаком! Например, с массивами. А также с Map (которую обычно переводят как “словарь”, “карта”, или “ассоциативный массив”). Очень важно понимать: структуры данных не привязаны к какому-то конкретному языку. Это просто абстрактные “чертежи”, по которым каждый язык программирования создает свои собственные классы, то есть реализации этой структуры. Например, одна из самых известных структур данных это связный список. Ты можешь зайти в википедию, почитать о том как он устроен, какие у него есть достоинства и недостатки. Возможно, тебе покажется знакомым его определение :) “Свя́зный спи́сок это базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка” Так ведь это же наш LinkedList! Точно, так оно и есть :) Структура данных “связный список” реализована в языке Java в классе LinkedList. Но и в других языках связный список тоже реализован! В Python он называется “llist”, а в C++ это “std::list” из стандартной библиотеки. Связный список это одна из базовых распространенных структур данных, поэтому ее реализацию ты найдешь в любом современном языке программирования. То же самое с ассоциативным массивом. Вот его определение из Википедии: Ассоциативный массив это абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу. Ничего не напоминает? :) Точно, для нас, джавистов, ассоциативный массив это интерфейс 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

Внутри наших методов вызываются методы класса 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='Эдвин ван Клифф'}

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

Чем заменяют Stack в современном коде

Есть момент, о котором стоит знать сразу. Класс java.util.Stack появился еще в самой первой версии Java и с тех пор тянет за собой наследство: он расширяет класс Vector, поэтому все его методы синхронизированы, даже если никакой многопоточности в программе нет. Есть деталь и поковарнее: перебор такого стека в цикле идет от дна к верху, то есть в порядке, обратном тому, в котором элементы будут из него извлекаться. Поэтому документация Oracle для новых задач советует другой инструмент: полный и согласованный набор операций LIFO дает интерфейс Deque и его реализации, и предпочитать следует именно их. Выглядит это почти так же, как раньше:

Deque<Card> deck = new ArrayDeque<>();
deck.push(new Card("Рагнарос"));
deck.push(new Card("Эдвин ван Клифф"));

Card top = deck.peek();    //  посмотреть верхнюю карту
Card taken = deck.pop();   //  взять верхнюю карту

Методы называются точно так же: push(), pop(), peek(). Поменялся только тип, а вся логика примера с колодой и сбросом осталась бы прежней. Разобраться со Stack все равно стоит, он часто встречается в старом коде и в вопросах на собеседованиях, а вот в новом проекте лучше сразу брать ArrayDeque.

Очередь (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. Чем он примечателен? Deque это двусторонняя очередь. Она расширяет функционал обычной очереди, позволяя добавлять элементы на оба края (в начало и конец очереди) и забирать элементы с обоих краев очереди. Двусторонняя очередь широко используется в разработке.

LinkedList как двусторонняя очередь

Обрати внимание на список классов-очередей, которые мы привели выше. Список довольно велик, но нет ли там чего-то знакомого для нас?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ха, так здесь же наш старый знакомый, LinkedList! То есть, он имплементирует интерфейс Queue? Но как он может быть очередью? Ведь LinkedList это связный список! Верно, но это никак не мешает ему быть очередью :) Вот список всех интерфейсов, которые он реализует:

All Implemented Interfaces:

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

Одна оговорка про версии: в Java 21 к этому списку добавился еще один интерфейс, SequencedCollection. На разговор об очередях это никак не влияет, Deque и Queue никуда не делись. Как видишь, LinkedList реализует интерфейс Deque, то есть двустороннюю очередь. Зачем это нужно? Благодаря этому мы можем получать элементы и из начала, и из конца LinkedList. А еще добавлять элементы и в начало, и в конец. Вот какие методы достались LinkedList от интерфейса Deque:

• peekFirst(): возвращает (но не удаляет из очереди) первый элемент.
• peekLast(): возвращает (но не удаляет из очереди) последний элемент.
• pollFirst(): возвращает первый элемент из очереди и удаляет его.
• pollLast(): возвращает последний элемент из очереди и удаляет его.
• addFirst(): добавляет новый элемент в начало очереди.
• addLast(): добавляет элемент в конец очереди.

Как видишь, LinkedList в полной мере реализует функционал двусторонней очереди! И если такой функционал понадобится в программе, будешь знать, что его можно использовать :)

Стек и очередь: в чем разница

Соберем все, о чем мы говорили, в одну таблицу: А наша сегодняшняя лекция подходит к концу. Напоследок я дам тебе пару ссылок для дополнительного чтения. Во-первых, обрати внимание на документацию по классу PriorityQueue, “приоритетной очереди”. Это одна из самых интересных и полезных реализаций Queue. Например, если в очереди в твой магазин стоят 50 человек, и 7 из них являются VIP-клиентами, PriorityQueue позволит тебе обслужить их в первую очередь! Очень полезная штука, согласен? :) Во-вторых, не будет лишним еще раз упомянуть книгу Роберта Лафоре “Структуры данных и алгоритмы на Java”. Во время чтения книги ты не только изучишь много структур данных (включая стек и очередь), но и самостоятельно реализуешь многие из них! Представь, например, что в Java не было бы класса Stack. Что бы ты делал, если бы тебе понадобилась такая структура данных для твоей программы? Конечно, пришлось бы написать ее самому. При чтении книги Лафоре ты часто именно этим и будешь заниматься. Благодаря этому твое понимание структур данных будет намного шире, чем при простом изучении теории :) С теорией мы на сегодня закончили, но теория без практики это ничто! Задачи сами себя не решат, так что самое время взяться за них! :)

Вопросы и ответы

Чем стек отличается от очереди?

Порядком выдачи элементов. Стек работает по LIFO: последний добавленный элемент уйдет первым, как верхнее письмо из стопки. Очередь работает по FIFO: первым уйдет тот, кого добавили раньше всех, как первый человек в очереди в магазин. У стека добавление и извлечение идут с одного конца, у очереди с разных.

Какими методами работают с очередью в Java?

У интерфейса Queue методы идут парами: одна версия при неудаче бросает исключение, вторая возвращает специальное значение. Добавить элемент это add() или offer(), забрать с удалением это remove() или poll(), посмотреть голову очереди не удаляя это element() или peek(). Вторая версия каждой пары возвращает false или null вместо исключения, поэтому с очередями ограниченной вместимости удобнее она.

Что такое Deque и зачем он нужен?

Deque это двусторонняя очередь, один из четырех подинтерфейсов Queue. Она позволяет и добавлять, и забирать элементы с обоих концов: addFirst(), addLast(), pollFirst(), pollLast(), peekFirst(), peekLast(). За счет этого одна и та же коллекция умеет работать и как очередь, и как стек.

Почему LinkedList одновременно и список, и очередь?

Потому что он реализует сразу несколько интерфейсов: List, Deque, Queue, Collection, Iterable, Cloneable, Serializable, а с Java 21 еще и SequencedCollection. Внутри это двусвязный список, который хранит ссылки и на первый, и на последний узел, поэтому операции с обоими концами обходятся дешево, и роль очереди дается ему без всяких натяжек.

Стоит ли использовать java.util.Stack в новом коде?

Для учебных примеров он подходит, а вот для рабочего кода документация Oracle советует другое: полный и согласованный набор операций LIFO дает интерфейс Deque и его реализации, и предпочитать следует именно их, например Deque<Integer> stack = new ArrayDeque<>();. Причина в том, что Stack унаследован от Vector: все его методы синхронизированы, а перебор идет от дна стека к верху, что для стека неинтуитивно.

Где на практике применяются стек и очередь?

Стек это отмена действий по Ctrl+Z, разбор скобок и выражений, обход графа в глубину и стек вызовов методов, который ведет сама JVM. Очередь это обработка задач в порядке поступления, буферы между потоками, рассылки, обход графа в ширину. Если задачи нужно брать не по порядку, а по важности, вместо обычной очереди берут PriorityQueue.

Читайте также

• Коллекции в Java: Java Collections Framework
• Интерфейс List в Java и ArrayList
• Реализация очереди (Queue) в Java
• Топ 10 вопросов о коллекциях в Java