Создание стека фиксированного размера

Question

Я хочу создать стек в Java, но исправить размер. Например, создайте новый стек, установите размер 10, затем, когда я помещаю элементы в стек, он заполняется, а когда он заполняется до десяти, последний элемент в стеке отбрасывается (удаляется). Я хочу использовать Stack, потому что он использует LIFO и очень хорошо соответствует моим потребностям.

Но метод setSize (), который Stack наследует от Vector, похоже, на самом деле не ограничивает размер стека. Я думаю, что мне чего-то не хватает в том, как работают стеки, или, может быть, стеки не предназначены для ограничения, поэтому это невозможно. Пожалуйста, просветите меня!

Answer 1

Вот тип SizedStack, который расширяет Stack:

import java.util.Stack;

public class SizedStack<T> extends Stack<T> {
    private int maxSize;

    public SizedStack(int size) {
        super();
        this.maxSize = size;
    }

    @Override
    public T push(T object) {
        //If the stack is too big, remove elements until it's the right size.
        while (this.size() >= maxSize) {
            this.remove(0);
        }
        return super.push(object);
    }
}

Используйте это так: SizedStack<Float> mySizedStack = new SizedStack<Float>(10);. Кроме размера, он работает как любой другой Stack.

Answer 2

Вы можете создать очень простой стек следующим образом:

public class FixedStack<T>
{
    private T[] stack;
    private int size;
    private int top;

    public FixedStack<T>(int size)
    {
        this.stack = (T[]) new Object[size];
        this.top = -1;
        this.size = size;
    }

    public void push(T obj)
    {
        if (top >= size)
            throw new IndexOutOfBoundsException("Stack size = " + size);
        stack[++top] = obj;
    }

    public T pop()
    {
        if (top < 0) throw new IndexOutOfBoundsException();
        T obj = stack[top--];
        stack[top + 1] = null;
        return obj;
    }

    public int size()
    {
        return size;
    }

    public int elements()
    {
        return top + 1;
    }
}

Answer 3

Это не невозможно :) Вам просто нужно предоставить собственную реализацию.

Я бы начал с RingBuffer, например this , и настроил бы его соответствующим образом.

Answer 4

A LinkedBlockingDeque является одним простым вариантом. Используйте конструктор LinkedBlockingQueue(int), где параметром является предел вашего стека.

---

Как вы заметили, Stack и Vector моделируют неограниченные последовательности. Метод setSize() усекает стек / вектор. Это не мешает структуре данных расти выше этого размера.

Answer 5

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

Вы можете написать собственный стек, который реализует описанные вами потребности. Тем не менее, вы нарушите LIFO, если вы это сделаете. Если достигнут максимальный размер, и вы помещаете что-то новое в стек, вы просто теряете ранее добавленный элемент. Так что если вы начнете выталкивать предметы из своего стека, вы пропустите некоторые.

Answer 6

Вы можете использовать LinkedHashMap и переопределить его метод removeEldestEntry:

public class FixedStack extends LinkedHashMap<Long, String> {

    private final int capacity;

    public FixedStack(int capacity) {
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(final Map.Entry<Long, String> eldest) {
        return super.size() > capacity;
    }
}

И чтобы проверить это:

    public static void main(String[] args) {

        FixedStack stack = new FixedStack(10);

        long added = 0;
        for (Locale locale : Locale.getAvailableLocales()) {
            if (locale.getDisplayCountry().length() > 0) {
                stack.put(added, locale.getDisplayCountry());
                System.out.println(locale.getDisplayCountry());
                added++;
            }
        }
        System.out.println(String.format(">>>>>>>>> %s added",
                added));
        Iterator<Entry<Long, String>> iterator = stack.entrySet().iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next().getValue());
        }
    }

Вам просто нужно решить, что вы хотите использовать в качестве ключа, в примере я использовал простой счетчик.

Answer 7

Вам нужна двусторонняя очередь типа LinkedList. Это не будет автоматически отбрасывать элементы спереди, но, создав подкласс / декорирование, вы можете добавить эту функциональность.

Answer 8

Вы можете создать подкласс Stack и переопределить соответствующий метод (методы) для реализации этого пользовательского поведения. И обязательно дайте ему четкое имя (например, FixedStack).