Help with Stack Problem

[lykathea]

I am trying to implement a stack where one can push to the front and to the back of the stack. However, my implementation is very slow. Can anyone help me think of a better method? Thank you!

public class Pch11_x1 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

        DoubleStack s = new DoubleStack();

        s.pushFront("b");
        s.pushFront(new Character('c'));
        s.pushBack(new Integer(1));

        for (int i = 0; i < s.getSize() + 1; i++) {
            System.out.println(s.peekFront(i));
        }

        for (int i = 0; i < 30000001; i++) {
            Object t = s.peekFront(0);
            s.popFront(1);
            s.pushBack(t);
        }

        for (int i = 0; i < s.getSize() + 1; i++) {
            System.out.println(s.peekFront(i));
        }

        for (int i = 0; i < 30000001; i++) {
            Object t = s.peekBack(0);
            s.popBack(1);
            s.pushFront(t);
        }

        for (int i = 0; i < s.getSize() + 1; i++) {
            System.out.println(s.peekFront(i));
        }
    }
}

class DoubleStack {

    private Object[] data;
    private int size;
    private final static int INIT_CAPACITY = 16;

    public DoubleStack() {
        data = new Object[INIT_CAPACITY];
        size = 0;
    }

    // push obj onto the front of the list
    public void pushFront(Object obj) {
        if (size == data.length) {
            Object[] newData = new Object[2 * data.length];
            System.arraycopy(data, 0, newData, 0, data.length);
            data = newData;
        }
        data[size] = obj;
        size++;
    }

    // pop n Object's off the front of the list
    public void popFront(int n) {
        if (n < 0) {
            return;
        }
        if (n > size) {
            n = size;
        }
        size -= n;

        return;
    }

    // return the object that is n from the front
    // of the list (sizeing from 0)
    public Object peekFront(int n) {
        if (n < 0) {
            return null;
        } else {
            return data[size - n];
        }
    }

    // push obj onto the back of the list
    public void pushBack(Object obj) {
        if (size == data.length) {
            Object[] newData = new Object[2 * data.length];
            System.arraycopy(data, 0, newData, 0, data.length);
            data = newData;
        }
        Object[] newData = new Object[data.length + 1];
        System.arraycopy(data, 0, newData, 1, data.length);
        data = newData;

        data[0] = obj;

    }

    // pop n Object's off the back of the list
    public void popBack(int n) {
        if (n < 0) {
            return;
        }
        if (n > size) {
            n = size;
        }
        size -= n;

        return;
    }

    // return the object that is n from the back
    // of the list (sizeing from 0)
    public Object peekBack(int n) {
        if (n < 0) {
            return null;
        } else {
            return data[0 + n];
        }
    }

    // return the size of the list
    public int getSize() {
        return size;
    }
}

[BestJewSinceJC]

Can you explain your reason for putting Integers and Characters in the same array? Also why you'd want a "DoubleStack" ?

[lykathea]

I want the stack to take any item and not be limited to a certain type.

I just called it a doublestack. I am trying to create a stack that can be peeked, pushed, and popped from the front of the stack as well as from the back.

[Taywin]

Why do you allow user to pass a number for popping or peeking? When you pop, you always pop the one on the top (or at the bottom in your implementation), and the same is with peek. The only think you need to check when you do pop/peek is the data size must be greater than 0, or you handle the case. The pop should return the object and remove it from the stack while peek should return the value of the object but not do anything with the stack. A user should not be able to pop multiple objects at a time because the user can use a loop to pop the item. Also, you should not do pop and dump the content. You should return the object. This is not really a stack, sorry...

[lykathea]

All I'm trying to figure out is how to push a number to the back of a stack. Maybe I shouldn't have posted my own code. Can anyone suggest a method to do what I am asking, that is, push an item onto the back of a stack?

[Taywin]

It is good that you did post your own code. Don't be offended. No one is perfect. Everyone makes a mistake.

Anyway, because you are using [], you cannot dynamically change anything. You should try ArrayList<Object> if you like. The api for ArrayList can be found here.

[lykathea]

I tried using ArrayList, and I still encounter the same problem. The program just hangs when I start looping with big numbers.

[Taywin]

After implementing it using ArrayList and Object, I found that Object class has no clone() and it is risky to just return the object inside your 'data' (returning reference instead of a clone object which is supposed to be done via peek)...

Speaking of speed, it is of course slow because you are using 30 million loop times. Anything would be slow on Java with that loop size when your implementation is dealing with memory allocation (push, pop). Use much smaller loop times is enough for your testing. Why do you need a huge loop number anyway? If you want that, use C++ or C which is much faster when you want to deal with memory yourself.

If your original code works but slow, then use it; otherwise, the code for your DoubleStack class is what I implemented with ArrayList<Object>.

class DoubleStack {

  private ArrayList<Object> data;
  private int size;
  private final int INIT_CAPACITY = 16;

  public DoubleStack() {
    data = new ArrayList<Object>();
    size = 0;
  }

  // push obj onto the front of the list
  // ignore and display an error message if full
  public void pushFront(Object obj) {
    if (size<INIT_CAPACITY) {
      data.add(0, obj);
      size++;
    }
    else { System.out.println("Stack is full!"); }
  }

  // return null and display error message if stack is empty
  // pop an Object's off the front of the list
  public Object popFront() {
    Object obj = null;
    if (size>0) {
      obj = data.remove(0);
      size--;
    }
    else { System.out.println("Stack is empty!"); }

    return obj;
  }

  // return a string of the object that is n from the front
  // return null if n is not between 0 to size-1
  public String peekFront(int n) {
    if (n<0 || n>(size-1)) {
      return null;
    }
    else {
      return data.get(n).toString();
    }
  }

  // push obj onto the back of the list
  // ignore and display an error message if full
  public void pushBack(Object obj) {
    if (size<INIT_CAPACITY) {
      int last = data.size();
      data.add(last, obj);
      size++;
    }
    else { System.out.println("Stack is full!"); }
  }

  // return null and display error message if stack is empty
  // pop an Object's off the back of the list
  public Object popBack() {
    Object obj = null;
    if (size>0) {
      obj = data.remove(size-1);
      size--;
    }
    else { System.out.println("Stack is empty!"); }

    return obj;
  }

  // return a string of the object that is n from the back
  // return null if n is not between 0 to size-1
  public String peekBack(int n) {
    if (n<0 || n>(size-1)) {
      return null;
    }
    else {
      return data.get(size-n).toString();
    }
  }

  // return the size of the list
  public int getSize() {
    return size;
  }


  // return a string of class information
  // Override toString() method of any class it may
  // extend from
  @Override
  public String toString() {
    String out = "Size: "+size+"\n";
    for (int i=0; i<size; i++) {
      out += i+" -> "+data.get(i).toString()+"\n";
    }
    return out;
  }
}

[lykathea]

Thank you very much for your help Taywin. I appreciate it. If there is no way to speed it up for big loop numbers, then I will mark this as answered, as the ArrayList implementation is much better than my original.

Thanks again.