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

Question

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

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

Answer 1

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

Answer 2

Я бы написал свою собственную реализацию Deque на основе кольцевого буфера .

Answer 3

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

Вы помещаете объекты в начало очереди. И если длина больше 3, вы выдвигаете спину.

Answer 4

Вот моя реализация 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);
    }
}

Answer 5

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

Answer 6

Это на 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 7

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

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

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

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