Какая структура данных будет содержать ограниченный набор элементов в LIFO?

Question

Я ищу структуру данных, которая в основном представляет собой ограниченный стек.

Если я объявляю, что стек может содержать не более 3 элементов, и я вставляю в него еще один элемент, извлекается самый старый элемент.

Answer 1

Ну, структура LIFO (Last In First Out) известна как стек, который является тем, что вам нужно для основной части вашего требования

Структура FIFO (First In First Out) известна как Очередь, которая является тем, что вам нужно для возможности удаления самых старых элементов с обратной стороны.

Комбинация этих факторов известна как Deque.Где у вас есть возможность нажимать или выскакивать с любого конца.

Я не уверен, есть ли в Java встроенная структура данных Deque, но если она есть (или вы можете найти реализацию в Google), вы можете просто добавить некоторую логику переноса, чтобы гарантировать, что если вы нажмете на начало, и deque.Сосчитайте > 3, затем также выскочите сзади.

Answer 2

Вы сможете реализовать это, используя оболочку поверх deque (http://en.wikipedia.org/wiki/Deque), или двусторонняя очередь.Просто убедитесь, что вы вызываете метод pollLast внутри метода offerFirst, если достигнут размер стека.

Answer 3

Я бы написал свой собственный Деке реализация, основанная на кольцевой буфер.

Answer 4

Вам нужна очередь.Односвязный список, в котором записаны первый и последний элементы.Двусвязный, если вы хотите перейти с обхода O (n) на O (1), чтобы обновить последний элемент.

Вы толкаете объекты в начало очереди.И если длина больше 3, вы откидываете заднюю часть.

Answer 5

Это на C #, поскольку, боюсь, я не знаю Java, но идея должна быть воплощена.

public class BoundedStack<T>
{
    private readonly int limit;
    private LinkedList<T> list;

    public BoundedStack(int limit)
    {
        this.limit = limit;
        list = new LinkedList<T>();
    }

    public void Push(T item)
    {
        if (list.Count == limit) list.RemoveFirst();
        list.AddLast(item);
    }

    public T Pop()
    {
        if (list.Count == 0) 
            throw new IndexOutOfRangeException("No items on the stack");

        var item = list.Last.Value;
        list.RemoveLast();

        return item;
    }

    public int Count()
    {
        return list.Count;
    }
}

Answer 6

В Apache commons есть что-то близкое к тому, что вам нужно, за исключением того, что это Fifo: Круговой буфер.Я думаю, вы застрянете в написании пользовательской оболочки для создания реализации, подобной Lifo.

Answer 7

Вот моя реализация LIFO, вдохновленная ответом Гарри Шатлера

public class BoundedStack<T> {

    private int limit;
    private LinkedList<T> list;

    public BoundedStack(int limit) {
        this.limit = limit;
        list = new LinkedList<>();
    }

    public void push(T item) {
        if (list. size() == limit) {
            list.removeLast();
        }
        list.addFirst(item);
    }

    public int size() {
        return list.size();
    }

    public List<T> getAll() {
        return list;
    }

    public T peek() {
        return list.get(0);
    }
}