---

// === 1. ЭЛЕМЕНТ СПИСКА (ДВУСВЯЗНЫЙ УЗЕЛ) ===
class Node {
    public int data;  // Данные кирпичика
    public Node next; // Стрелочка на следующий элемент (вперед)
    public Node prev; // Стрелочка на предыдущий элемент (назад)

    public Node(int value) {
        data = value;
        next = null;
        prev = null;
    }
}

// === 2. ДВУХСВЯЗНЫЙ ДВУСТОРОННИЙ СПИСОК ===
class DoublyLinkedList {
    Node first = null; // Ссылка на начало списка
    Node last = null;  // Ссылка на конец списка
    int currentSize = 0; // Счетчик элементов

    public boolean isEmpty() {
        return first == null;
    }

    public int getSize() {
        return currentSize;
    }

    // Вставка в самое НАЧАЛО списка (для Стека)
    public void insertFirst(int value) {
        Node newBrick = new Node(value);
        if (isEmpty()) {
            last = newBrick; // Если список пуст, новый узел становится и последним
        } else {
            first.prev = newBrick; // Старый первый смотрит назад на новый
            newBrick.next = first; // Новый смотрит вперед на старый первый
        }
        first = newBrick; // Новый официально стал первым
        currentSize++;
    }

    // Вставка в самый КОНЕЦ списка (для Очереди)
    public void insertLast(int value) {
        Node newBrick = new Node(value);
        if (isEmpty()) {
            first = newBrick; // Если список пуст, новый узел становится и первым
        } else {
            last.next = newBrick; // Старый последний смотрит вперед на новый
            newBrick.prev = last; // Новый смотрит назад на старый последний
        }
        last = newBrick; // Новый официально стал последним
        currentSize++;
    }

    // Вставка ПО ПОРЯДКУ возрастания (для Приоритетной очереди)
    public void insertInOrder(int value) {
        Node newBrick = new Node(value);
        
        if (isEmpty()) {
            first = newBrick;
            last = newBrick;
            currentSize++;
            return;
        }

        Node current = first;
        // Шагаем вперед, пока не найдем число, которое больше нашего value
        while (current != null && value > current.data) {
            current = current.next;
        }

        if (current == first) { 
            insertFirst(value); // Если нужно встать в самое начало
        } else if (current == null) { 
            insertLast(value);  // Если нужно встать в самый конец
        } else { 
            // Вставка в середину между current.prev и current (раздвигаем вагоны)
            newBrick.next = current;
            newBrick.prev = current.prev;
            current.prev.next = newBrick;
            current.prev = newBrick;
            currentSize++;
        }
    }

    // Удаление ВСЕГДА С НАЧАЛА списка (для всех трех структур)
    public void removeFirst() {
        if (isEmpty()) return;

        if (first.next == null) { // Если в списке был всего один кирпичик
            first = null;
            last = null;
        } else {
            first = first.next; // Новым первым становится следующий узел
            first.prev = null;  // Отрезаем стрелочку назад у нового первого узла
        }
        currentSize--;
    }

    // Получить значение первого элемента
    public int getFirstValue() {
        if (isEmpty()) {
            return -1; 
        }
        return first.data;
    }

    // Вывод всех элементов на экран
    public void printList() {
        Node current = first;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

// === 3. КЛАСС СТЕК (LIFO) ===
class Stack {
    DoublyLinkedList list = new DoublyLinkedList();

    public void push(int num) {
        list.insertFirst(num); // Кладём всегда в начало (наверх стопки)
    }

    public void pop() {
        if (!list.isEmpty()) {
            list.removeFirst(); // Удаляем верхний элемент
        } else {
            System.out.println("Стек пуст");
        }
    }

    public int peek() {
        return list.getFirstValue(); // Просто смотрим на верхний элемент
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public int size() {
        return list.getSize();
    }

    public void printStack() {
        System.out.print("Стек: ");
        list.printList();
    }
}

// === 4. КЛАСС ОЧЕРЕДЬ (FIFO) ===
class Queue {
    DoublyLinkedList list = new DoublyLinkedList();

    public void push(int num) {
        list.insertLast(num); // Новые элементы встают в конец очереди
    }

    public void pop() {
        if (!list.isEmpty()) {
            list.removeFirst(); // Первые пришедшие уходят первыми из начала
        } else {
            System.out.println("Очередь пуста");
        }
    }

    public int peek() {
        return list.getFirstValue(); // Смотрим, кто первый на выход
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public int size() {
        return list.getSize();
    }

    public void printQueue() {
        System.out.print("Очередь: ");
        list.printList();
    }
}

// === 5. КЛАСС ПРИОРИТЕТНАЯ ОЧЕРЕДЬ ===
class Priority {
    DoublyLinkedList list = new DoublyLinkedList();

    public void push(int num) {
        list.insertInOrder(num); // Автоматическая сортировка при добавлении
    }

    public void pop() {
        if (!list.isEmpty()) {
            list.removeFirst(); // Удаляем самый приоритетный (минимальный) элемент
        } else {
            System.out.println("Приоритетная очередь пуста");
        }
    }

    public int peek() {
        return list.getFirstValue(); // Посмотреть на самый приоритетный элемент
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public int size() {
        return list.getSize();
    }

    public void printPriority() {
        System.out.print("Приоритетная очередь: ");
        list.printList();
    }
}

// === 6. ОСНОВНОЙ КЛАСС ДЛЯ ПРОВЕРКИ ===
public class Main {
    public static void main(String[] args) {
        System.out.println("=== СТЕК НА ДВУСВЯЗНОМ СПИСКЕ ===");
        Stack stack = new Stack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.printStack(); // Выведет: 30 20 10 (30 наверху)
        System.out.println("Вершина через peek: " + stack.peek());
        System.out.println("Текущий размер: " + stack.size());
        stack.pop();
        stack.printStack(); // Выведет: 20 10

        System.out.println("\n=== ОЧЕРЕДЬ НА ДВУСВЯЗНОМ СПИСКЕ ===");
        Queue queue = new Queue();
        queue.push(100);
        queue.push(200);
        queue.push(300);
        queue.printQueue(); // Выведет: 100 200 300 (100 в начале)
        System.out.println("Первый элемент через peek: " + queue.peek());
        System.out.println("Текущий размер: " + queue.size());
        queue.pop();
        queue.printQueue(); // Выведет: 200 300

        System.out.println("\n=== ПРИОРИТЕТНАЯ ОЧЕРЕДЬ НА ДВУСВЯЗНОМ СПИСКЕ ===");
        Priority pr = new Priority();
        pr.push(55);
        pr.push(11);
        pr.push(33);
        pr.printPriority(); // Автоматически выстроит по росту: 11 33 55
        System.out.println("Приоритетный (минимальный) через peek: " + pr.peek());
        pr.pop(); // Уберет 11
        pr.printPriority(); // Выведет: 33 55
    }
}