Реализация метода Push с использованием Stack и List ADT

Question

Как я могу написать реализацию push для стека ADT, используя список ADT? Предполагая, что я нажимаю на вершину стека, должен ли я создать список temp и сделать что-то, чтобы добавить предыдущую голову в хвост?

private someList<E> stack; 

public void push(E element){ 
      stack.add(element); 
     } 



//another file 
public someList<E> add(E newHead){ 

    return new someList<E>(newHead, this); 
} 

Answer 1

Что важно в реализации АТД стека, где вы собираетесь добавить новые элементы, которые вы push и где вы собираетесь удалять элементы, которые вы pop. Очевидно, push(someElement); pop(); должен оставить стек неизменным.

Итак, у нас есть 2 варианта, добавление/удаление элементов в конце списка или спереди.

public void push(E element){ 
     stack.add(element); 
} 

Вы решили добавить/удалить их в конце списка. Я не знаю, что должен сделать метод add, однако если он возвращает новый someList, который представляет новый стек, то приватное поле stack должно получить этот новый созданный стек!

Обратите внимание, что если цель add является изменение тока головки (заменить текущие TOS (= вершине стека) от этого), то вы могли бы просто написать его как следовать

public someList<E> add(E newHead){ 
    pop(); // remove TOS 
    push(newHead); // Add newHead as the new TOS 
    return this.stack; 
} 

Я реализовал stack ADT для String. Я оставляю это как простое упражнение, чтобы изменить его на ваши нужды (используя someList вместо List и используя дженерики).

public class Stack { 
    private List<String> stack = new ArrayList<String>(); 

    public void push(String element){ 
     stack.add(element); 
    } 

    public List<String> add(String newHead){ 
     stack = new ArrayList<String>(stack); // you should do "stack = new someList<E>(newHead, this);" 
     return stack; // return the new stack 
    } 

    public String pop() { 
     String res = stack.get(stack.size() - 1); 
     stack.remove(stack.size() - 1); // 
     return res; 
    } 

    public void printStack() { 
     System.out.println("TOS (Top Of Stack)"); 
     for(int i = stack.size() - 1; i >= 0; i--) 
      System.out.println(stack.get(i)); 
     System.out.println("EOS (End Of Stack)"); 
    } 
} 

// Test it 
... 
String a = "a", b = "b"; 
Stack stck = new Stack(); 

stck.push(a); 
stck.push(b); 
stck.push(b); 
stck.push(a); 
stck.pop(); 

stck.printStack(); 
... 

Это то, как стек меняется во время теста.

TOS (Top Of Stack)   

a ---> b ---> b ---> a ---> b 
      a   b   b   b 
        a   b   a 
           a 

EOS (End Of Stack) 

Обратите внимание, что в данной реализации stack ADT мы толкание/выскакиваем элементы из стека путем добавления/удаления элементов из списка хвоста (точнее arrayList). Это идеально подходит для использования с java arrayList, потому что добавление элемента в хвост списка или удаление последнего элемента находится в O (1).

Методы, определяющие положение вставки должны скопировать все элементы массива вправо от вставки

(Source)

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

В этом случае вы должны изменить реализацию stack ADT так, чтобы передняя часть someList представляла TOS, а хвост списка представлял конец стека. Следовательно, push/pop будет добавлять/удалять элементы на фронте списка.

EDIT: Вы могли бы реализовать count метод:

• Явно вспоминая, сколько элементов в стеке (то есть у вас есть size поле, которое вы инкремент для каждого push() и декремента для каждого успешногоpop() (т.е. для каждого pop() когда size > 0 затем уменьшаем size).

• опираясь на size() метода ArrayList, который используется для представления стека.

Поэтому возможная реализация

public class Stack { 
    private List<String> stack = new ArrayList<String>(); 

    ...   

    public int count() { 
     return stack.size(); 
    } 
}