Skip to main content

05. Очередь

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

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

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

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

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

mdl

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

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

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

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

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

// класс очереди
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;
}

}

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

// главный класс приложения
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 

Задание

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

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

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

// Элемент очереди
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

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