Алгоритмы и структуры данных

АТД: Дек

Дек (Deque) — это абстрактный тип данных, который вбирает в себя возможности как стека, так и очереди, то есть может работать с элементами как по LIFO, так и по FIFO принципу.

Операции на деке

Дек должен поддерживать следующие основные операции:

  • Вставка в начало (pushFront)
  • Вставка в конец (pushBack)
  • Удаление элемента с начала (popFront)
  • Удаление элемента с конца (popBack)

Имплементация

Дек можно имплементировать с помощью кольцевого буфера и двусвязного списка.

Имплементация на основе кольцевого буфера

Данная имплементация дека ограничена по размеру.

Идея данной имплементации заключается в следующем: мы будем поддерживать два указателя — на голову и хвост списка. Голова будет крутиться по кольцевому буферу по часовой стрелке, а хвост в обратном направлении, таким образом они будут идти навстречу друг другу.

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

Итак, инициализация:

    public ArrayDeque() {
        arr = new Integer[arraySize];
        head = 0;
        tail = 0;
    }

Вставка в начало работает следующим образом: мы вставляем новый элемент в ячейку, куда указывает head, а затем сдвигаем head вперед:

    public void addFirst(Integer e) {
        int head = this.head;
        if (((head == arraySize - 1 && tail == 0) || (head + 1 == tail))) {
            throw new IllegalStateException("Deque is full");
        }
        arr[head] = e;
        this.head = nextHead(head);
    }
    private int nextHead(int head) {
        if (head == arraySize - 1) {
            return 0;
        }
        return ++head;
    }

Метод удаления с начала сдвигает head назад, а затем забирает элемент из ячейки:

    public Integer removeFirst() {
        int head = this.head;
        if (head == tail) {
            throw new NoSuchElementException("Deque is empty");
        }
        head = prevHead(head);
        Integer elem = arr[head];
        arr[head] = null;
        this.head = head;
        return elem;
    }

    private int prevHead(int head) {
        if (head == 0) {
            return arraySize - 1;
        }
        return --head;
    }

Метод вставки в конец почти не отличается от вставки в начало. Разница лишь в том, что мы сначала сдвигаем tail и только затем вставляем элемент. Так необходимо делать потому, что при инициализации оба указателя указывают на нулевую ячейку массива, но head начинает вставлять с начала массива, а хвост должен начать вставлять с конца массива.

Итак, метод вставки в конец:

    public void addLast(Integer e) {
        int tail = this.tail;
        if (((head == arraySize - 1 && tail == 0) || (head + 1 == tail))) {
            throw new IllegalStateException("Deque is full");
        }
        tail = nextTail(tail);
        arr[tail] = e;
        this.tail = tail;
    }
   
    private int nextTail(int tail) {
        if (tail == 0) {
            return arraySize - 1;
        }
        return --tail;
    }

Метод удаления:

    public Integer removeLast() {
        int tail = this.tail;
        if (head == tail) {
            throw new NoSuchElementException("Deque is empty");
        }
        Integer elem = arr[tail];
        arr[tail] = null;
        this.tail = prevTail(tail);
        return elem;
    }

    private int prevTail(int tail) {
        if (tail == arraySize - 1) {
            return 0;
        }
        return ++tail;
    }

Имплементация на основе связного списка

Для этой имплементации нам понадобится двусвязный список. Данную структуру данных мы уже имплементировали раннее, так давайте же заиспользуем ее.

Имплементация получается довольно тривиальной.

Инициализация:

    public LinkedListDeque() {
        this.linkedList = new DoublyLinkedList<>();
    }

Добавление и удаление с начала:

    public void addFirst(E e) {
        linkedList.addFirst(e);
    }

    public E removeFirst() {
        return linkedList.removeFirst().key;
    }

Добавление и удаление с конца:

    public void addLast(E e) {
        linkedList.addLast(e);
    }

    public E removeLast() {
        return linkedList.removeLast().key;
    }

Добавить комментарий

Ваш адрес email не будет опубликован.