Как создать очередь на основе односвязного списка в java?

Question

[parkito]

Здравствуйте. Подскажите, пожалуйста, как орагнизовать очередь на односвяном списке.
Стек - легко.

public class List<T> {
    public int key;
    public T data;
    public List next;

    List(int key, T data) {
        this.key = key;
        this.data = data;
    }

    T getData() {
        return this.data;
    }
    void show(){
        System.out.println(key+") "+data+" ");
    }
}

public class LinkedList<T> {
    private int size;
    private List first;

    public LinkedList() {
        first = new List(0, 0);
        size = 0;
    }

    public void add(T element) {
        List newList = new List(size, element);
        size++;
        newList.next = first;
        first = newList;

    }

    public void display() {
        List<Integer> current = first;
        while (current != null) {
            System.out.println(current.getData());
            current = current.next;
        }
    }
}

Такую вещь я могу организовать на c++ с помощью указателей. Но тут задача меня поставила в тупик.

Answer 1

[MikkiMouse]

Помимо ссылки на первый элемент, можно добавить ссылку на последний. Элементы добавлять через ссылку на последний, извлекать через ссылку на первый.

Comments

[parkito]

Тогда получиться двусвязный список. Задание гласит о односвязный.

[MikkiMouse]

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

[Денис Загаевский]

MikkiMouse: бред. А->B->C , есть ссылка на С. Что делать будешь?

[MikkiMouse]

Денис Загаевский: Где бред? В классическом односвязном списке у нас нет ссылки на С, есть только ссылка на А. Автору я предложил хранить так же ссылку и на С. Если есть ссылки на А и С, добавляем через С, извлекаем через А.

[Денис Загаевский]

MikkiMouse: а, ок. Вопрос снят.

Answer 2

[Alexej Simakov]

Class MyQueue { 
Element head;
Element tail;
...
public void addElement(Element e){
e.setNext(this.getTail())
this.getTail()
this.setTail(e)
} ... }

что-то в этом роде. новый элемент сперва указывает на хвостовой элемент, а потом указатель хвостового элемента переводится на новый элемент.