java - 使用 Stack 和 List ADT 实现推送方法

Question

我将如何着手为使用列表 ADT 的堆栈 ADT 编写推送实现？假设我推到堆栈的顶部，我是否必须创建一个临时列表并做一些事情来将前一个头部添加到尾部？

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

在堆栈 ADT 的实现中重要的是，您要在何处添加您push 的新元素以及您要在何处删除您pop 的元素.显然 push(someElement); pop(); 应该保持堆栈不变。

所以我们有 2 个选择，在列表末尾或前面添加/删除元素。

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

您已选择在列表末尾添加/删除它们。我不知道 add 方法必须做什么，但是如果它返回一个新的 someList 代表一个/新的堆栈，那么私有(private) stack 字段应该分配这个新创建的堆栈!

请注意，如果 add 的目的是更改当前头部(用这个替换当前 TOS(= 栈顶))，那么您可以简单地编写如下

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

我已经为 String 实现了 stack ADT。我把它作为一个简单的练习来根据您的需要进行更改(使用 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) 中。

Methods specifying insertion position have to copy all array elements to the right from insertion

(Source)

在使用您自己的 someList 实现时，您必须检查是否同样适用。但是，如果将一个元素添加到列表的尾部(或删除最后一个元素)需要您遍历整个列表(例如单个链表就是这种情况，因此 O(n))，那么添加/删除第一个元素应该在 O(1) 中。

在这种情况下，您应该更改 stack ADT 的实现，以便 someList 的前面现在代表 TOS，列表的尾部代表结尾的堆栈。因此，push/pop 将在列表的前面 添加/删除元素。

编辑:你可以实现一个count方法:

• 通过显式记住堆栈上有多少元素(即您有一个 size 字段，您为每个 push() 递增并为每个 < strong>成功 pop()(即对于每个 pop() 当 size > 0 然后递减 size).

• 依靠ArrayList的size()方法来表示栈。

因此可能的实现

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

    ...        

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