StacksQueues/Java/ArrayStack

ArrayStack

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: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/stacks/ArrayStack.java

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;
                        i++;
                }
                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) {
                        resize(capacity*2);
                }
                // 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 {
                if(capacity<=1){
                        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;
                capacity--;

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