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 запрещается
- Перейдите от
Node
кNode2
, добавьте поле ссылки на последний элемент очередиNode2 last
- Конструктор по умолчанию (
first
иlast
инициализируются значениемnull
) - Конструктор копии (копирует значения
first
иlast
) int [] getData()
- возвращает массив, содержащий все элементы очереди с сохранением порядкаvoid addFirst(int v)
- добавить элемент в начало очередиvoid addLast(int v)
- добавить элемент в конец очередиint removeFirst()
- удалить первый элемент, возвращает значение удалённого элементаint removeLast()
- удалить последний элемент, возвращает значение удалённого элементаint getFirst()
- возвращает значение первого элементаint getLast()
- возвращает значение последнего элементаvoid clear()
- очистить очередьboolean contains(int v)
- возвращаетtrue
, если очередь содержит элемент с полученным значением иfalse
- если нетint size()
- возвращает размер очереди
Очередь, построенная на массиве не засчитывается.
Все поля и методы должны иметь модификатор public