From charlesreid1


Stack interface:

  • size() - get the number of elements currently in the stack
  • isEmpty() - returns true if stack is empty
  • push() - add the given item to the top of the stack
  • pop() - remove the top item in the stack and return it
  • peek() - return reference to top item in stack, but do not remove it

Link to code

Link to code:

Selections from code

Resize array method:

        /** Resize the array: O(n). */
        private void resize(int newcap) {
                Object[] newdata = new Object[newcap];
                int i = 0;
                for(Object o : data) {
                        newdata[i] = o;
                data = newdata;

Then the add method is modified to check if the array needs to be doubled:

        /** Push an object onto the top of the stack: O(1). */
        public void push(Object o) {
                // Check if full
                if(capacity==data.length) {
                // Increment and set
                data[capacity++] = o;

Likewise, the pop method checks if we need to reduce the array size:

        /** Pop an object from the top of the stack: O(1). */
        public Object pop() throws Empty {
                        throw new Empty("Popping an empty stack.");

                // Remove item from end of array
                // (top of stack)
                Object o = data[capacity-1];
                data[capacity-1] = null;

                // Check if one quarter empty
                if(capacity<=(data.length/4)) {
                return o;