使用堆栈和列表ADT的推送方法实现 [英] Push method implementation using Stack and List ADT

问题描述

如何使用列表ADT为堆栈ADT编写push的实现?假设我要推送到堆栈的顶部，是否需要创建一个临时列表并执行某些操作以将前一个头部添加到尾部?

How would I go about writing an implementation of push for the stack ADT using list ADT? Assuming i'm pushing to the top of stack, would I have to create a temp list and do something to add the previous head to the tail?

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); 
}

推荐答案

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

What is important in the implementation of the stack ADT, is where you are going to add the new elements you push and where you are going to delete elements you pop. Obviously push(someElement); pop(); should leave the stack unchanged.

因此，我们有2个选择，在列表的末尾或最前面添加/删除元素.

So we have 2 choices, adding/removing elements at the end of the list or in the front.

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

您已选择在列表的末尾添加/删除它们. 我不知道add方法有什么作用，但是，如果它返回一个表示新堆栈的新someList，则专用stack字段应分配此新创建的堆栈！

You've chosen to add/remove them at the end of the list. I don't know what the add method has to do, however if it returns a new someList which represents a/the new stack, then the private stack field should get this newly created stack assigned!

请注意，如果add的目的是更改当前磁头(用此值替换当前TOS(=堆栈顶部))，则可以简单地将其编写为以下内容

Note that if the purpose of add is to change the current head (replace current TOS (= Top Of Stack) by this one), then you could simply write it as follow

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并使用泛型).

I've implemented the stack ADT for String's. I leave it as a simple exercise to change it to your needs (using someList instead of List and using generics).

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();
...

这是在测试用例期间堆栈的变化方式.

This is how the stack is changing during the test case.

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)中.

Note that in this implementation of the stack ADT we are pushing/popping elements from the stack by adding/removing elements from the list's tail (more precisely arrayList). Which is ideal for use with java's arrayList because adding an element to the tail of the list, or removing the last element, is in O(1).

指定插入位置的方法必须将所有数组元素从插入位置复制到右侧

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

(源)

在使用自己的someList实现时，您将必须检查相同的条件是否成立.但是，如果将元素添加到列表的末尾(或删除最后一个元素)要求您遍历整个列表(例如，单个链接列表就是这种情况，因此为O(n))，则添加/删除第一个元素应该在O(1)中.

You will have to check if the same holds when using your own someList implementation. However, if adding an element to the tail of the list (or removing the last element) requires you to traverse the whole list (which is the case for e.g. a single linked list, hence O(n)), then adding/removing the first element should be in O(1).

在这种情况下，您应该更改stack ADT的实现，以使someList的开头现在表示TOS，列表的结尾表示堆栈的末尾.因此，push/pop将随后在列表的前中添加/删除元素.

In that case you should change the stack ADT's implementation so that the front of someList is now representing the TOS and the tail of the list is representing the end of the stack. Hence push/pop will then add/remove elements at the front of the list.

您可以实现count方法:

• 通过明确地记住堆栈中有多少个元素(即，您有一个size字段，您为每个push()递增，而为每个成功 pop()递减(即对于每个pop()，当size > 0然后递减size).

• By explicitly remembering how many elements are on the stack (i.e. you have a size field that you increment for every push() and decrement for every successful pop() (i.e. for every pop() when size > 0 then decrement size).

依靠用于表示堆栈的ArrayList的size()方法.

By relying on the size() method of the ArrayList that is used to represent the stack.

可以实施

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

    ...        

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

这篇关于使用堆栈和列表ADT的推送方法实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！