С какой стороны получаем доступ к элементам в Queue

С какой стороны получаем доступ к элементам в Queue

Queue (очередь) — это структура данных, которая работает по принципу FIFO (First In, First Out) — первый вошёл, первый вышел. Доступ осуществляется с двух разных сторон.

FIFO принцип

┌─────────────────────────────┐
│ Front (Начало)              │ Back (Конец)
├─────────────────────────────┤
│ 1   │ 2   │ 3   │ 4   │ 5   │
├─────────────────────────────┤
└─────────────────────────────┘
  ↑                             ↑
  poll/remove                  offer/add
  (получение)                  (добавление)

1. Добавление в Queue (Rear/Back)

Элементы добавляются в конец очереди:

public class QueueAddExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        
        // Добавление в конец (rear/back)
        queue.add(1);      // [1]
        queue.offer(2);    // [1, 2]
        queue.add(3);      // [1, 2, 3]
        queue.offer(4);    // [1, 2, 3, 4]
        
        // Разница add vs offer:
        // - add(E) выбросит исключение, если переполнена
        // - offer(E) вернёт false, если переполнена
        // В LinkedList оба работают одинаково
    }
}

Добавление элемента:
До:  [1, 2, 3]
         ↑
         rear

После add(4):
[1, 2, 3, 4]
            ↑
            rear (переместился)

2. Извлечение из Queue (Front/Head)

Элементы извлекаются с начала очереди:

public class QueueRemoveExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>(Arrays.asList(1, 2, 3, 4));
        // [1, 2, 3, 4]
        
        // Извлечение с начала (front/head)
        int first = queue.poll();   // 1, очередь: [2, 3, 4]
        int second = queue.remove(); // 2, очередь: [3, 4]
        
        // Просмотр без удаления
        int head = queue.peek();     // 3, очередь остаётся: [3, 4]
        int head2 = queue.element(); // 3, очередь остаётся: [3, 4]
        
        // Разница методов:
        // poll() вернёт null, если пуста
        // remove() выбросит исключение, если пуста
        // peek() вернёт null, если пуста
        // element() выбросит исключение, если пуста
    }
}

Извлечение элемента:
До:  [1, 2, 3, 4]
 ↑
 front/head

После poll():
[2, 3, 4]
 ↑
 front/head (переместился)

Методы Queue

public interface Queue<E> extends Collection<E> {
    // Добавление (rear/back)
    boolean add(E e);        // Исключение, если переполнена
    boolean offer(E e);      // false, если переполнена
    
    // Удаление (front/head)
    E remove();              // Исключение, если пуста
    E poll();                // null, если пуста
    
    // Просмотр (front/head)
    E element();             // Исключение, если пуста
    E peek();                // null, если пуста
}

// Таблица методов
/*
            Throws Exception    Returns special value
Insert      add(E)              offer(E)
Remove      remove()            poll()
Examine     element()           peek()
*/

Пример использования

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        
        // Эмуляция очереди в магазин
        System.out.println("=== Клиенты встают в очередь ===");
        queue.offer("Alice");   // Alice встала в очередь
        queue.offer("Bob");     // Bob встал после Alice
        queue.offer("Charlie"); // Charlie встал в конец
        queue.offer("David");   // David встал в конец
        
        System.out.println("Очередь: " + queue);
        // [Alice, Bob, Charlie, David]
        
        System.out.println("\n=== Кассир обслуживает клиентов ===");
        while (!queue.isEmpty()) {
            String customer = queue.poll();  // Первый в очереди идёт к кассе
            System.out.println("Обслуживаем: " + customer);
            System.out.println("Осталось в очереди: " + queue);
        }
    }
}

// Вывод:
// === Клиенты встают в очередь ===
// Очередь: [Alice, Bob, Charlie, David]
// 
// === Кассир обслуживает клиентов ===
// Обслуживаем: Alice
// Осталось в очереди: [Bob, Charlie, David]
// Обслуживаем: Bob
// Осталось в очереди: [Charlie, David]
// Обслуживаем: Charlie
// Осталось в очереди: [David]
// Обслуживаем: David
// Осталось в очереди: []

Сравнение с другими структурами

public class DataStructureComparison {
    // QUEUE (FIFO) - очередь
    Queue<Integer> queue = new LinkedList<>(Arrays.asList(1, 2, 3));
    // Добавление в конец: queue.offer(4)  -> [1, 2, 3, 4]
    // Удаление с начала: queue.poll()     -> 1, остаток [2, 3, 4]
    
    // STACK (LIFO) - стек
    Stack<Integer> stack = new Stack<>();
    stack.push(1); stack.push(2); stack.push(3);
    // Добавление на вершину: stack.push(4)  -> [1, 2, 3, 4]
    // Удаление с вершины:    stack.pop()    -> 4, остаток [1, 2, 3]
    
    // DEQUE (Double Ended Queue) - двусторонняя очередь
    Deque<Integer> deque = new LinkedList<>(Arrays.asList(1, 2, 3));
    // Добавление с обоих концов: addFirst(), addLast()
    // Удаление с обоих концов:   removeFirst(), removeLast()
    // poll() -> удаляет с начала
    // pollLast() -> удаляет с конца
}

Реализации Queue

public class QueueImplementations {
    public static void main(String[] args) {
        // LinkedList (FIFO)
        Queue<String> queue1 = new LinkedList<>();
        // offer() -> addLast() -> O(1)
        // poll()  -> removeFirst() -> O(1)
        
        // PriorityQueue (Приоритетная очередь)
        Queue<Integer> queue2 = new PriorityQueue<>();  // Min-heap
        queue2.offer(5);
        queue2.offer(2);
        queue2.offer(8);
        queue2.poll();  // 2 (наименьший, не первый добавленный)
        
        // BlockingQueue (для потоков)
        BlockingQueue<String> queue3 = new LinkedBlockingQueue<>();
        // offer(E, timeout, unit) - добавление с timeout
        // poll(timeout, unit) - удаление с timeout
        
        // ArrayBlockingQueue (ограниченный размер)
        BlockingQueue<Integer> queue4 = new ArrayBlockingQueue<>(10);
        // offer(E) блокирует, если полна
        // poll() блокирует, если пуста
        
        // ConcurrentLinkedQueue (для параллелизма)
        Queue<String> queue5 = new ConcurrentLinkedQueue<>();
        // Lock-free реализация
    }
}

BlockingQueue для потоков

public class BlockingQueueExample throws InterruptedException {
    public static void main(String[] args) throws InterruptedException {
        BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(3);
        
        // Producer thread
        new Thread(() -> {
            try {
                for (int i = 1; i <= 5; i++) {
                    System.out.println("Producing: " + i);
                    queue.put(i);  // Блокирует, если очередь полна
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }).start();
        
        // Consumer thread
        new Thread(() -> {
            try {
                for (int i = 0; i < 5; i++) {
                    Thread.sleep(1000);  // Медленное потребление
                    Integer value = queue.take();  // Блокирует, если пуста
                    System.out.println("Consuming: " + value);
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }).start();
    }
}

Выводы

public class QueueAccessSides {
    // ✅ ДОБАВЛЕНИЕ В КОНЕЦ (Rear/Back)
    // - offer(E e) - предпочтительно
    // - add(E e) - альтернатива
    // - put(E e) - для BlockingQueue
    
    // ✅ УДАЛЕНИЕ С НАЧАЛА (Front/Head)
    // - poll() - возвращает null если пуста
    // - remove() - выбросит исключение если пуста
    // - take() - для BlockingQueue, блокирует если пуста
    
    // ✅ ПРОСМОТР БЕЗ УДАЛЕНИЯ (Front/Head)
    // - peek() - возвращает null если пуста
    // - element() - выбросит исключение если пуста
    
    // Порядок FIFO: первый добавленный - первый удалённый
}

Ответ на вопрос

С какой стороны получаем доступ?

• Добавление (insertion): С конца (rear/back) - через offer() или add()
• Извлечение (removal): С начала (front/head) - через poll() или remove()
• Просмотр (peek): С начала (front/head) - через peek() или element()

Это является основной характеристикой Queue — FIFO (First In, First Out).