Двусторонние очереди (DEQUES)

Двусторонние очереди (DEQUES)

http://java.sun.com/developer/JDCTechTips/2005/tt1214.html#2

Очередь поддерживает добавление элементов с одного конца и извлечение их с другого. Для сравнения двусторонняя очередь поддерживает добавление и удаление элементов с обоих концов. Ее работа напоминаю комбинацию стека и очереди. Интерфейс Deque, наследуется от интерфейса Queue, представленного в J2SE 5.0, и является одной из последних функций добавленных в Java SE 6 (Окончательное включение данной функциональности находится на рассмотрении в JCP). Данный интерфейс реализован в классах LinkedList, ArrayDeque и многопоточном классе LinkedBlockingDeque.

Класс LinkedList является наиболее используемым при работе с двусторонними очередями. Он не имеет ограничений на количество элементов и реализует быстродействующие методы добавления и удаления элементов с обоих концов. Класс ArrayDeque является другой реализацией не имеющей ограничения на число элементов. В нем реализована обертка для работы с индексами, обеспечивающая высокую производительность. Как и все реализации коллекций, данные реализации также не являются защищенными от многопоточного доступа. (Исторически такие коллекции как Vector и Hashtable являются защищенными от многопоточного доступа, но они не ориентированы на высокую производительность). Еслм вам нужна безопасная работа с потоками, используйте класс LinkedBlockingDeque. Класс LinkedBlockingDeque реализует интерфейс BlockingDeque наследуемый от интерфейса Deque. Данным класс может иметь ограничение на количество элементов. Если ограничение не задано, то оно равно значению Integer.MAX_VALUE.

Вы можете добавлять элементы в двустороннюю очередь при помощи следующих методов:

  • void addFirst(E e)
  • void addLast(E e)
  • boolean add(E e)

Метод add() аналогичен методу addLast(). В случае нехватки места в двусторонней очереди выбрасывается исключение IllegalStateException. Вы также можете добавить элементы при помощи следующих методов:

  • boolean offer(E e)
  • boolean offerFirst(E e)
  • boolean offerLast(E e)

В отличие от добавления элементов при помощи метода addXXX(), при добавлении элементов при помощи метода offerXXX(), возвращается значение false, если элемент не может быть добавлен.

Также существует пара методов для удаления элементов:

  • remove(), removeFirst(), and removeLast()
  • poll(), pollFirst(), and pollLast()

Методы removeXXX() выбрасывают исключение NoSuchElementException, если двусторонняя очередь пуста. Методы pollXXX() возвращают значение null, если двусторонняя очередь пуста. Вы даже можете удалять определенный объект при помощи следующих методов, хотя работа с двусторонними очередями подразумевает удаление элементов только с концов очереди.

  • boolean remove(Object o)
  • boolean removeFirstOccurrence(Object o)
  • boolean removeLastOccurrence(Object o)

В классе Deque имеется шесть методов для работы с элементами:

  • element()
  • getFirst()
  • getLast()
  • peek()
  • peekFirst()
  • peekLast()

Метод get() не определен, так как метод element() является методом интерфейса, унаследованным из интерфейса Queue. Методы get аналогичным методам removeXXX() и выбрасывают исключение NoSuchElementException, если двусторонняя очередь пуста. Методы peek в этом случае возвращают значение null. Естественно, так как вы можете добавлять элементы null, вы не можете проследить различие между элементом null и пустой двусторонней очередью. В данном случае может пригодится применение метода size().

Так как концептуально двусторонняя очередь является привязанной с двух сторон, то вы можете проводить поиск элементов в любом порядке. Используйте метод iterator() для поиска элементов с начала до конца и метод descendingIterator() для поиска элементов в обратном направлении с конца до начала. Однако вы не можете получить доступ к элементу по его местоположению, по крайней мере данный механизм не включен в интерфейс Deque. Однако класс LinkedList, реализующий интерфейс Deque, позволяет получить доступ в произвольному элементу через интерфейс List, который он также реализует. Без выполнения требования по произвольному доступу, реализация интерфейса Deque, может быть выполнена более эффективно.

Для чего использовать двусторонние очереди? Двусторонние очереди предоставляют удобные структуры данных для использования в рекурсивных процедурах, как, например работа с лабиринтами и разбор исходных данных. Когда вы разбираете исходную часть, вы сохраняете правильные варианты, добавляя с одной стороны. Если вариант оказывается не верным вы удаляете его, возвращаясь к последнему верному элементу. В данном варианте вы работаете только с одним концом, как в стеке. Как только вы достигли конца, вам необходимо вернуться в начало для получения решения, которое начинается с последнего элемента. Другим типичным примером является планировщик заданий в операционной системе.

Нижеприведенная программа Blocked, демонстрирует использование интерфейса Deque, а вернее класса LinkedBlockingDeque с установленными границами очереди. Конечно, это не лучший пример использования двусторонней очереди, но он позволяет показать применение API и события, возникающие при достижении предела очереди. Данная программа получает 23 названия месяцев (полные и сокращенные) и по одному добавляет их в начало очереди, поддерживающей шесть элементов. Другой поток удаляет элементы из начла и конца двусторонней очереди, основываясь на количестве элементов, находящихся в коллекции.

import java.io.*;
import java.util.*;
import java.util.concurrent.*;

public class Blocked {
  public static void main(String args[]) {
    Calendar now = Calendar.getInstance();
    Locale locale = Locale.getDefault();
    final Console console = System.console();
    final Map names = now.getDisplayNames(Calendar.MONTH,
        Calendar.ALL_STYLES, locale);
    console.printf("Starting names: %s%n", names);
    final Deque deque = new LinkedBlockingDeque(6);
    // Добавление элемента в начало
    new Thread() {
      public void run() {
        Set keys = names.keySet();
        Iterator itor = keys.iterator();
        String element = null;
        while (itor.hasNext() || element != null) {
          if (element == null) {
            element = itor.next();
            console.printf("MapGot: %s%n", element);
          }
          console.printf("Offering: %s%n", element);
          if (deque.offerFirst(element)) {
            console.printf("MapRemoving: %s%n", element);
            itor.remove();
            element = null;
          } else {
            try {
              Thread.sleep(250);
            } catch (InterruptedException ignored) {
            }
          }
        }
        try {
          Thread.sleep(3500);
        } catch (InterruptedException ignored) {
        }
        System.exit(0);
      }
    }.start();
    while (true) {
      if ((deque.size() % 2 == 1)) {
        // удаление из начала
        console.printf("Remove head: %s%n", deque.pollFirst());
      } else {
        // удаление из конца
        console.printf("Remove tail: %s%n", deque.pollLast());
      }
      // пауза между циклами
      try {
        Thread.sleep(500);
      } catch (InterruptedException ignored) {
      }
    }
  }
}

Как показано ниже, при выполнении программы, выводится множество строк. Это происходит из-за частого использования оператора printf(). Строка выводится на экран каждый раз, когда элемент получается из источника, удаляется из источника, добавляется в двустороннюю очередь или удаляется из нее. Обратите внимание на случай, когда добавление происходит в полную двустороннюю очередь.

>> java Blocked


   Starting names: {Jun=5, March=2, December=11, April=3, 
   November=10, September=8, October=9, Sep=8, Aug=7, Apr=3, 
   May=4, June=5, Feb=1, Dec=11, Oct=9, Jan=0, Mar=2, Jul=6, 
   August=7, January=0, February=1, July=6, Nov=10}
   Remove tail: null
   MapGot: Jun
   Offering: Jun
   MapRemoving: Jun
   MapGot: March
   Offering: March
   MapRemoving: March
   ...

   Remove tail: Jul
   Remove head: Nov
   Remove tail: August
   Remove head: July
   Remove tail: January
   Remove head: February
   Remove tail: null

Следует отметить две вещи. Первое, используется только 23 элемента (а не 24) для представления полных и сокращенных названий месяцев, тат как "May" используется для обоих представлений. Метод getDisplayNames() возвращает таблицу, таким образом значение "May" не может быть ключом для двух полей, полного и сокращенного. Второе, если единственное, что вам необходимо - это добавление элементов с одного конца и извлечение их с другого используйте реализацию интерфейса Queue, вместо Deque.

Для сравнения двусторонних очередей и векторов см.статью An In-Depth Study of the STLDeque Container. В ней обсуждаются вопросы производительности каждого из решений. Реальные цифры для Java платформы будут другими, но основные идеи останутся верными.

Теги: deques