使用堆栈和列表ADT推送方法实现

Question

我将如何去编写ADT使用列表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，则专用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）。

方法指定插入位置必须所有数组元素的权利从插入

(Source)

复制您必须检查是否同样使用自己someList实现时成立。但是，如果向列表尾部添加元素（或删除最后一个元素），则需要遍历整个列表（例如对于单个链接列表，因此为O（n）），然后添加/删除第一个元素应该在O（1）中。

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

编辑：您可以实现一个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(); 
    } 
}