Queue в Java

Что такое очередь (Queue) в Java

Очередь - это очень интересный тип хранения данных. Мы можем проводить с ней ограниченное количество операций - обычно только с верхним элементом, и не имеем доступа к "середине" очереди.

Выглядит странно? На самом деле, есть много примеров из повседневной жизни, которые помогут нам представить механизм работы очереди.

Во-первых... Очередь!

alt text

  • В идеале, мы не можем встать в середину очереди - только в конец. А тот, кто приходит первым, первый получает мороженное. Или справку. Или что-то там еще. Точно так же работает и Queue. Мы не можем ничего вставить в середину очереди - только в конец.
  • Тем не менее, убирать элемент можно и из середины очереди - так, например, человек в любой момент может махнуть рукой и сказать: "А, я уже три часа тут стою - пойду домой!"
  • Более того, элемент не всегда может влезть в очередь (в смысле в Queue). Например, не сталкивались с тем, что доходит очередь до Вас - и как раз начинается обед? 🙁 Или касса закрывается? Вот, теперь Вы видите, что очередь работает совсем как.. ну, очередь)

Какие есть виды очередей (Queue)

Для начала Вам хватит знания одного типа - PriorityQueue.

alt text

Что интересного в PriorityQueue? Дело в том, что элементы в ней располагаются не только по порядку, но и по приоритету. Этот приоритет можно задавать самостоятельно, но для начинающих это может быть пока немного сложная тема. Пока Вам стоит знать, что если создавать очередь из стандартных типов данных (Integer, Float, String), у нее будет стандартный приоритет:

  • для чисел по возрастанию
  • для строк по алфавиту

FIFO и LIFO в Java

Кстати, "принцип очереди" - то, что первый, кто пришел, первым получает мороженое - обозначается английской аббревиатурой FIFO ("First in first out"). Переводится как "первый пришел первый вышел". Кроме очереди можно привести пример с конвейером - то, что ты положил раньше на конвейерную ленту, первым станет готовым продуктом и поедет в магазин.

Также в Java есть структуры, которые работают чуть-чуть по-другому. В таких структурах тот элемент, который поступил первым, первым вынимается. Можно провести аналогию со стопкой тарелок - та тарелка, которую ты поставил первой, оказывается в самом низу. Очень неудобно доставать, правда?

alt text

Поэтому мы моем тарелки, начиная с самой верхней - т.е. той, которую мы поставили последней. Этот принцип называется LIFO ("Last in first out", "последний пришел первый вышел"). По такому принципу работает еще одна структура данных, очень похожая на очередь - стэк. Тот что overflow 🙂 Но это так, на будущее.

Операции с Queue

  1. add() - добавляет элемент в конец очереди.

    Поправка: если очередь с приоритетом - т.е. PriorityQueue - элемент ставится не обязательно в конец, а в соответствии со своим приоритетом

  2. remove() и poll() - удаляет верхний элемент из очереди.

  3. offer() - пытается вставить элемент в конец очереди.

  4. peek() и element() - показывают верхний элемент очереди

Пример 1

add() - добавляем элемент в конец очереди. (Поправка: если очередь с приоритетом - т.е. PriorityQueue - элемент ставится не обязательно в конец, а в соответствии со своим приоритетом):

public class Test {
  public static void main(String[] args) {

    PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

    myPriorityQueue.add(1);
    myPriorityQueue.add(2);
    myPriorityQueue.add(3);
    for(int pq : myPriorityQueue) {
      System.out.println(pq);
    }
  }
}

Пример 2

remove() и poll() - удаляем верхний элемент из очереди. Так сказать, "Три часа жду - надоело, иду домой!" 🙂 Но в чем между ними разница?

1. У метода remove() есть две формы - remove() и remove(Object o), а у poll() - только одна. В первой форме оба метода одинаковые - они убирают "голову" (первый элемент) очереди. Обезглавливают так сказать 🙂

Например, тут мы используем метод remove():

public class Test {
  public static void main(String[] args) {
    PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

    myPriorityQueue.add(1);
    myPriorityQueue.add(2);
    myPriorityQueue.add(3);

    for(int i: myPriorityQueue) {
      System.out.println(i);
    }

    myPriorityQueue.remove();
    System.out.println("After removing:");

    for(int i: myPriorityQueue) {
      System.out.println(i);
    }
  }
}

Точно то же самое получим, если напишем вместо remove() poll():

public class Test {
  public static void main(String[] args) {
    PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

    myPriorityQueue.add(1);
    myPriorityQueue.add(2);
    myPriorityQueue.add(3);

    for(int i: myPriorityQueue) {
      System.out.println(i);
    }

    myPriorityQueue.poll();
    System.out.println("After removing:");

    for(int i: myPriorityQueue) {
      System.out.println(i);
    }
  }
}

Но remove(Object o) позволяет убирать любой элемент, не только сверху. Например, попробуем убрать двойку - она лежит в середине очереди:

public class Test {
  public static void main(String[] args) {
    PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

    myPriorityQueue.add(1);
    myPriorityQueue.add(2);
    myPriorityQueue.add(3);

    for(int i: myPriorityQueue) {
      System.out.println(i);
    }

    myPriorityQueue.remove(2);
    System.out.println("After removing:");

    for(int i: myPriorityQueue) {
      System.out.println(i);
    }
  }
}
  1. Методы будут действовать по-разному если у нас пустая очередь. Например:
public class Test {
  public static void main(String[] args) {
    PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

    myPriorityQueue.remove();
  }
}

Если мы попытаемся вызвать метод remove() на пустом листе, получим Exception.

Если poll() - ничего не произойдет:

public class Test {
  public static void main(String[] args) {
    PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

    myPriorityQueue.poll();
  }
}

Вывод:

  • хотите Exception (т.е. если пустая очередь - недопустимое состояние) - берите remove()
  • Если нет - берите poll()

Пример 3

  • offer() - пытается вставить в конец очереди. С английского "offer" переводится как "предложить". Почему "предлагаем"? Потому что в очередях с фиксированным размером у нас может не получится вставить элемент в очередь. Давайте попробуем его использовать:
public class Test {
  public static void main(String[] args) {
    PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

    myPriorityQueue.add(1);
    myPriorityQueue.add(2);
    myPriorityQueue.add(3);
    myPriorityQueue.offer(22);

    for(int i: myPriorityQueue) {
      System.out.println(i);
    }
  }
}

Ура! Предложение принято 🙂

Пример 4

peek() (от англ. "подсматривать"), и element() - показывают верхний элемент очереди. Например:

public class Test {
  public static void main(String[] args) {
    PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

    myPriorityQueue.add(1);
    myPriorityQueue.add(2);
    myPriorityQueue.add(3);

    System.out.println(myPriorityQueue.peek());
  }
}

Все верно, мы получили первый элемент - единицу.

Или, давайте попробуем применить element():

public class Test {
  public static void main(String[] args) {
    PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

    myPriorityQueue.add(1);
    myPriorityQueue.add(2);
    myPriorityQueue.add(3);

    System.out.println(myPriorityQueue.element());
  }
}

Получаем то же самое - единицу.

Поздравляем - теперь Вы знаете, что такое очередь и как ей пользоваться! Увидимся в следующих уроках 😉

Использован материал с ресурса: Queue в Java

results matching ""

    No results matching ""