Как реализовать методы add у Queue и метод push у Stack

168
02 апреля 2018, 23:32

Добрый день сообщество . Задали задание решить . Реализовать контейнеры Queue и Stack на базе Linkedlist . Как работает метод add я знаю т.е добавляем новый элемент в начало очереди . А вот как реализовать специфический порядок никак не получается. Если не трудно напишите реализацию на базе линкед листа двухсвязанного списка . Смотрел реализацию в самой коллекции , но почему то она у меня не работает.

 private int size = 0;
    private Node<E> first;
    private Node<E> last;
    private int count = 0;
    public SimpleQueue() {
        first = new Node(null, null, last);
        last = new Node(first, null, null);
    }

    private  class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    public E  poll() {
        final Node<E> result = first.next;
        return (result.item == null) ? null : helpForPoll(result);
    }
    //метод извлекает иэлемент из головы очереди и возвращает его . удаляет этот элемент или возвращает нул если очередь пустая
    private E helpForPoll(Node<E> value) {
        final E element = value.item;
        first = new Node<>(null, null, first.next.next);
        value.prev = null;
        value.item = null;
        value.next = null;
        size--;
        return element;
    }
    // метод вставляет элемент в конец очереди согласно логике
    public boolean offer(E value) {
        size++;
        return true;
    }
    @Override
    public boolean add(Object value) {
        size++;
        return true;
    }
    @Override
    public E get(int index) {
        Node<E> temp = first.next;
        for (int i = 0; i < index; i++) {
            temp = getNextElement(temp);
        }
        return temp.item;
    }
    private Node<E> getNextElement(Node<E> value) {
        return value.next;
    }
    @Override
    public Iterator iterator() {
        return new Iterator() {
            @Override
            public boolean hasNext() {
                return count < size;
            }
            @Override
            public E next() {
                if (count == size) {
                    throw new NoSuchElementException();
                }
                return get(count++);
            }
        };
    }
Answer 1

Я не знаю Java в достаточной мере, но список выглядит неработоспособным.

    first = new Node(null, null, last);
    last = new Node(first, null, null);

Здесь в первой строк создаётся узел со ссылкой next на ёще не существующий last. Её надо поправить после создания last.

Метод вставки в конец (push) не реализован. Он един для стека и очереди и может выглядеть так:

 newNode = new Node(last.prev, Data, last);
 last.prev = newNode
 счётчик и чего там ещё обновить

Извлечение нужно сделать из начала и с конца. Первое понадобится для очереди, второе для стека.

popBegin:
   node = first.next
   if node = last
     return null
   first.next = node.next
   node.next.prev = first
   теперь можно забрать данные и освободить node 
popEnd:
   сделать зеркально по аналогии
READ ALSO
Не отправляется сообщение с сервера к клиенту в Websocket Java

Не отправляется сообщение с сервера к клиенту в Websocket Java

Прошу не пинать я новичок в JavaНе могу отправить данные с сервера к клиенту

192
Слушатель на BooleanProperty

Слушатель на BooleanProperty

Добрый день

223
Помощь в переводе кода на java AWT в JavaFX

Помощь в переводе кода на java AWT в JavaFX

Есть код на java awtИз него мне нужна была только "логика"

211
Сглаживание шрифтов в CSS, как? [требует правки]

Сглаживание шрифтов в CSS, как? [требует правки]

Сглаживание шрифтов в CSS, как?

216