使用 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 个选择，adding/removing 个元素在列表的末尾或前面。

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

您已选择 add/remove 他们在列表的末尾。我不知道 add 方法必须做什么，但是如果它 returns 一个代表 a/the 新堆栈的新 someList，那么私有 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 的这个实现中，我们是 pushing/popping 个来自列表尾部的 adding/removing 个元素的堆栈元素（更准确地说是 arrayList）。这是与 java 的 arrayList 一起使用的理想选择，因为将元素添加到列表的尾部或删除最后一个元素在 O(1)[=77= 中].

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

(Source)

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

在这种情况下，您应该更改 stack ADT 的实现，以便 someList 的前面现在代表 TOS，列表的尾部代表堆栈的末尾。因此 push/pop 将在列表的前面处 add/remove 个元素。

编辑：您可以实施 count 方法：

通过明确记住堆栈上有多少元素（即你有一个 size 字段，每个 push() 递增，每个 递减成功 pop()（即对于每个 pop() 当 size > 0 然后递减 size）。

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

因此可能实现

public class Stack { private List<String> stack = new ArrayList<String>(); ... public int count() { return stack.size(); } }

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

Push method implementation using Stack and List ADT

java

stack

list

adt