Стек, что вы можете переместить n-й элемент на вершину стека

Question

Я ищу структуру данных стека, которая также позволяет перемещать n-й элемент в верхнюю часть стека.Так что в дополнение к pop (), push (), peek () мне нужно что-то вроде moveToTop (int n), где верхняя часть стека n = 0, а нижняя часть стека n = size-1.

Как лучше всего это осуществить?Я работаю на Java.

Answer 1

Есть несколько способов реализовать стек, которые мне известны:

- реализовать его с помощью расширения Vector

- реализовать его с помощью любого компонента List

- реализовать его как связанную структуру данных

- реализовать его с помощью базового массива Java

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

Answer 2

java.util.LinkedList выполняет ваше требование, потому что оно linked list / stack / queue одновременно.

Соответствующие методы:

• public E remove(int index)
  Удалить по индексу и получить удаленное значение.
• public void push(E e)
  Переместиться наверх.

Итак, что вам нужно сделать, это:

• Определите индекс.
• Удалите его по индексу и получите возвращаемое значение.
• Переместите возвращаемое значение вверх.

Answer 3

Вы можете создать другой массив или другую базовую структуру для временного хранения элементов.Переместите элементы перед элементом n в него, отодвиньте эти элементы назад и нажмите на элемент, который вы хотите поместить поверх этого.

public class MyStack<T> {
    T items[size];
    ....
    void moveToTop(int n)
    {
        T obj = items[n];
        T[] tempItems = new T[n - 1];
        Arrays.copyOf(items, n - 1);
        System.arraycopy(items, 0, tempItems, 0, n - 1);
        System.arraycopy(tempItems, 0, items, 1, n - 1);
        items[0] = obj;
    }
    ....
}

Для краткости удалены другие части.Вместо того, чтобы делать все это, вы можете проверить список с двумя ссылками или список пропусков.

Answer 4

Зачем изобретать?Простой класс Stack https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html Он наследует remove (int index) от Vector.

Answer 5

В стандартной структуре стека нет элемента moveToTop, но если вы хотите это сделать, я думаю, что вы можете реализовать его следующим образом:

public class MyStack<T> extends Stack<T>{

    public synchronized void moveToTop(int n) throws Exception {
        int size = this.size();
        if(n>size) {
            throw new Exception("error position");
        }
        T ele = remove(n);
        push(ele);
    }
}