Implementing a Stack in Java - Part 2

Let’s add a peek function to our stack. The peek function will return the element that is currently on the top of the stack without removing it from the stack. If our stack is empty is will return null.

Our peek function looks as follows:

public T peek() {
     if(head == null)
          return null;
     return head.data;
}

Add a function to return the current size of the stack. It simply returns the value contained in the size variable.

public int getSize() {
     return size;
}

Add a function to clear all the items from our stack. This function simply needs to set the head to null and the size to 0. If the head is already equal to null then it doesn’t need to do anything.

public void clear() {
	if(head != null) {
		head = null;
		size = 0;
	}
}

Add a function to return a string containing the items in our stack in order. Our function definition looks as follows:

public String toString() {

}

First let’s declare a StringBuilder to build our string. It is typically good practice to use a StringBuilder to build a string.

    StringBuilder s = new StringBuilder();

Let’s append “[]” to our string so that the result will be contained within brackets. At the end of the function we will also return to String version of our StringBuilder via toString().

    s.append("[");
    //add code to add the contents of the stack to the StringBuilder
    s.append("]");
    return s.toString();

Check to make sure the head of our stack is not equal to null. If our head is equal to null then there is nothing to add to the string since our stack is empty.

    if(head != null) {
		
    }

Next for each element in the stack we want to add its data to our StringBuilder. We’ll do this be iterating through the stack starting with our head. As long as our the current element of the stack is not the last element in the stack we will append a comma and a space to the StringBuilder. This enhances readability. First lets add the code to iterate through each element in the stack. To do this we set a temporary variable n to the head of the stack. Then while the n value is not equal to null we set it to the next node in the stack.

    	Node<T> n = head;
	while(n != null) {
            //add code to add the current element to the StringBuilder here.
	    n = n.next;
	}

Add code to append the value of the current element to the StringBuilder:

	s.append(n.data);
	if(n.next != null)
		s.append(", ");

The finished function is as follows:

public String toString() {
	StringBuilder s = new StringBuilder();
	s.append("[");
	if(head != null) {
		Node<T> n = head;
		while(n != null) {
			s.append(n.data);
			if(n.next != null)
				s.append(", ");
			n = n.next;
		}
	}
	s.append("]");
	return s.toString();
}

Our finished Stack class looks as follows:

public class MyStack<T> {
	private class Node<U> {
		public U data;
		public Node<U> next;
		public Node(U data) {
			this.data = data;
			next = null;
		}
	}
	private Node<T> head;
	private int size;
	public MyStack() {
		head = null;
		size = 0;
	}
	public void add(T data) {
		Node<T> newNode = new Node<T>(data);
		if(head == null) {
			head = newNode;
		} else {
			newNode.next = head;
			head = newNode;
		}
		size++;
	}
	public T peek() {
		if(head == null)
			return null;
		return head.data;
	}
	public T pop() {
		if(head == null)
			return null;
		T result = head.data;
		head = head.next;
		size--;
		return result;
	}
	public int getSize() {
		return size;
	}
	public void clear() {
		if(head != null) {
			head = null;
			size = 0;
		}
	}
	public String toString() {
		StringBuilder s = new StringBuilder();
		s.append("[");
		if(head != null) {
			Node<T> n = head;
			while(n != null) {
				s.append(n.data);
				if(n.next != null)
					s.append(", ");
				n = n.next;
			}
		}
		s.append("]");
		return s.toString();
	}
}

Data Structures

Implementing a Stack in Java - Part 2

RECENT POSTS