Push method implementation using Stack and List ADT

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

Solution

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.

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

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!

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

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)

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

(Source)

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

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.

EDIT : You could implement a count method :

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).
By relying on the size() method of the ArrayList that is used to represent the stack.

Hence a possible implementation

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

    ...        

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