A Stack Class in Java

What is a Stack?

In English, a stack is a pile of objects. In Computer Science, a stack is a linear collection which allows adding or removing elements from the same end (the top).

Stack elements are processed in a last in, first out (LIFO) manner. In contrast, a queue is a collection where elements are processed in a first in, first out (FIFO) manner. Note that, stacks and queues have restrictions on how the elements can be accessed.

Stacks have many applications in programming. An important example is the function-call stack. When a function (or method) is called, the system puts the status of the function into a stack; and when the function returns, the status is removed. The status information usually includes: parameters and local variables, returning points of the function, etc.

LIFO vs. FIFO

Consider the following accounting example comparing LIFO and FIFO. Suppose we bought 5 identical computers at prices: $400, $400, $500, $500, $600; and then we sold 3 of them for $800 each. What is the profit? What is the value of the inventory?

The answer depends on which computers were sold. Although the computers are physically identical, their accounting values are different. The following are different calculations using FIFO and LIFO accounting.

Design and Implement a Stack Class

Here we design a Stack class which holds generic objects. It has the following attributes and methods:

• int count: the number of elements
• T[] data: the array storage for elements
• void push(T e): adds one element
• T pop(): removes one element
• boolean isEmpty(): checks emptyness
• int size(): returns the number of elements

The implementation in Java is as below.

import java.util.Arrays;
public class Stack <T>
{
	private int	count;
	private T[]	data;

	public Stack()
	{
		data = (T[]) new Object[8];
		count = 0;
	}

	void expandCapacity()
	{
		data = Arrays.copyOf(data, data.length * 2);
	}

	void push(T e)
	{
		if (count == data.length)
			expandCapacity();
		data[count++] = e;
	}

	T pop() throws Exception
	{
		if (count <= 0)
		{
			throw new Exception("stack empty");
		}
		count--;
		return data[count];
	}

	boolean isEmpty()
	{
		return count == 0;
	}

	int size()
	{
		return count;
	}

	public static void main(String[] args) throws Exception
	{
		Stack<String> s = new Stack<String>();
		s.push("Alice");
		s.push("Bob");
		s.push("Carl");
		s.push("Dave");

		while (!s.isEmpty())
			System.out.println(s.pop());
	}
}

Using Stacks

Consider the problem of converting a decimal number to its binary representation. In the following we give two solutions: one using recursion and the other one using a stack.

import java.util.Scanner;
public class Binary
{
	// Using recursion
	public static void convertRecursion(int n)
	{
		if (n == 0)
			return;
		convertRecursion(n / 2);
		System.out.print(n % 2);
	}

	// Using stack
	public static void convertStack(int n) throws Exception
	{
		Stack<Integer> s = new Stack<Integer>();
		while (n > 0)
		{
			s.push(n % 2);
			n /= 2;
		}
		while (!s.isEmpty())
			System.out.print(s.pop());
	}

	public static void main(String[] args) throws Exception
	{
		Scanner scan = new Scanner(System.in);
		System.out.println("Type in an integer:");
		int n = scan.nextInt();
		System.out.println("Binary representation (recursion): ");
		convertRecursion(n);
		System.out.println("Binary representation (stack): ");
		convertStack(n);
	}
}

Related Posts

• A Queue Class in Java
• A Dynamic Array Class in Java

Comments

comments