05. Очередь

Этот и следующий блок будут посвящены структурам данных на ссылках. В си им соответствуют структуры данных на указателях.

Однонаправленная очередь

В качестве примера рассмотрим однонаправленную очередь. Суть её работы схожа со стеком MyStack из прошлого блока.

Очередь также позволяет обращаться только к первому элементу, однако реализована она не с помощью динамического массива, а на ссылках.

Для приложения с очередью нам понадобится три класса: Node - элемент очереди, MyQueue - сама очередь и Main - главный класс приложения

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

Первый класс - это класс элемента Node. У него всего два поля: значение value и ссылка на следующий элемент next.

Node.java

// Элемент очереди
public class Node {
    // Ссылка на следующий элемент очереди
    public Node next;
    // Значение элемента
    public int value;

    // конструктор элемента очереди
    public Node(int value) {
        this.value = value;
        // при создании у элемента очереди нет следующего
        // поэтому указатель смотрит в никуда
        this.next = null;
    }
}

Однонаправленная очередь должна хранить ссылку на первый элемент. При этом каждый элемент очереди указывает на следующий, у последнего элемента поле next хранит null. Если в очереди нет элементов, то ссылка на первый элемент должна хранить null

MyQueue.java

// класс очереди
public class MyQueue {
    // ссылка на первый элемент очереди
    // если она пустая, то равен null
    public Node first;

    // конструктор по умолчанию
    public MyQueue() {
        // ссылка на первый элемент равна null,
        // т.е. указывает в никуда
        first = null;
    }
    
    // конструктор копии
    public MyQueue(MyQueue myQueue) {
        // ссылка на первый элемент 
        this.first = myQueue.first;
    }

    // добавить элемент в очередь (v - значение элемента)
    public void add(int v) {
        // создаём новый элемент очереди
        Node n = new Node(v);
        // если в очереди есть хотя бы один элемент,
        if (first != null)
            // то указываем, что для созданного элемента следующим
            // будет тот, который сейчас является первым в очереди
            n.next = first;

        // делаем созданный элемент первым в очереди
        first = n;
    }


    // возвращает true, если очередь пуста
    public boolean isEmpty() {
        // отсутствие элементов в очереди эквивалентно
        // тому, что ссылка на первый элемент будет смотреть в никуда
        return first == null;
    }



    // возвращает значение первого элемента очереди
    // если очередь пустая, будет брошено исключение
    public int element() {
        return first.value;
    }

    // возвращает значение первого элемента очереди и
    // удаляет его
    // если очередь пустая, будет брошено исключение
    public int remove() {
        // сохраняем значение первого элемента очереди
        int res = first.value;
        // делаем первым элементом тот, который был следующим
        // для первого до удаления элемента. Если в очереди был
        // ровно один элемент, то всё в порядке, ссылка
        // на первый элемент будет указывать вникуда,
        // т.е. first будет хранить значение null
        first = first.next;
        return res;
    }

    // очистить очередь
    public void clear() {
        // меняем ссылку на первый элемент очереди
        // так, чтобы она указывала в никуда, все созданные
        // элементы очереди java удалит сама
        first = null;
    }

}

Главный класс приложения будет таким:

Main.java

// главный класс приложения
public class Main {
    public static void main(String[] args) {
        // создаём очередь
        MyQueue mq = new MyQueue();
        // добавляем в неё последовательно числа
        // от 0 до 9
        for (int i = 0; i < 10; i++)
            mq.add(i);

        // пока в очереди есть элементы
        while (!mq.isEmpty())
            // удаляем первый элемент и выводим его значение
            // в консоль
            System.out.print(mq.remove() + " ");

    }
}

Если запустим программу, то получим:

9 8 7 6 5 4 3 2 1 0 

Задание

Трудоёмкость

Это задание рассчитано на два урока, за него будет выставлено две оценки

Пусть уже определён класс элемента двунаправленной очереди:

Node2.java

// Элемент очереди
public class Node2 {
    // Ссылка на следующий элемент очереди
    public Node2 next;
    // Ссылка на предыдущий элемент очереди
    public Node2 prev;
    // Значение элемента
    public int value;

    // конструктор элемента очереди
    public Node2(Node2 prev, int value) {
        this.value = value;
        // при создании у элемента очереди нет следующего
        // поэтому указатель смотрит в никуда
        this.next = null;
        // сохраняем ссылку на предыдущий элемент
        this.prev = prev;
    }

    // конструктор элемента очереди
    public Node2(int value) {
        this.value = value;
        // при создании у элемента очереди нет следующего
        // поэтому указатель смотрит в никуда
        this.next = null;
        // указатель смотрит в никуда
        this.prev = null;
    }
}

Допишите класс MyQueue так, чтобы он реализовывал следующую логику:

Использовать встроенные коллекции java запрещается

1. Перейдите от Node к Node2, добавьте поле ссылки на последний элемент очереди Node2 last
2. Конструктор по умолчанию (first и last инициализируются значением null)
3. Конструктор копии (копирует значения first и last)
4. int [] getData() - возвращает массив, содержащий все элементы очереди с сохранением порядка
5. void addFirst(int v) - добавить элемент в начало очереди
6. void addLast(int v)- добавить элемент в конец очереди
7. int removeFirst() - удалить первый элемент, возвращает значение удалённого элемента
8. int removeLast() - удалить последний элемент, возвращает значение удалённого элемента
9. int getFirst() - возвращает значение первого элемента
10. int getLast() - возвращает значение последнего элемента
11. void clear() - очистить очередь
12. boolean contains(int v) - возвращает true, если очередь содержит элемент с полученным значением и false- если нет
13. int size() - возвращает размер очереди

Очередь, построенная на массиве не засчитывается.

Все поля и методы должны иметь модификатор public

Ссылка на контест