A Stack implementation with an Array.

The stack is a list-like structure in which elements may be inserted or removed from only one end. While this restriction makes stacks less flexible than lists, it also makes stacks both efficient (for those operations they can do) and easy to implement. Many applications require only the limited form of insert and remove operations that stacks provide. In such cases, it is more efficient to use the simpler stack data structure rather than the generic list.

Stack is called a “LIFO” list, which stands for “Last-In, First Out.” Note that one implication of the LIFO policy is that stacks remove elements in reverse order of their arrival. The accessible element of the stack is called the top element. Elements are not said to be inserted, they are pushed onto the stack. When removed, an element is said to be popped from the stack.The following Figure shows a sample stack ADT. As with lists, there are many variations on stack implementation. The two approaches are array-based and linked stacks, which are analogous to array-based and linked lists, respectively.

The following diagram is representing stack Push (insert an Element in a stack) and Pop (Removing an element from a Stack) operation.

As I've mentioned before, everything in Java is an object, (since it's an Object Oriented language), so, lets write a stack object!

Array-Based Stacks

public class ArrayStack {
  protected int head[];
  protected int pointer;

  public ArrayStack(int capacity) {
	head = new int[capacity];
	pointer = -1;
  }

  public boolean isEmpty() {
	return pointer == -1;
  }

  public void push(int i) {
	if (pointer + 1 < head.length)
		head[++pointer] = i;
  }

  public int pop() {
	if (isEmpty())
		return 0;
	return head[pointer--];
  }
}

 

As you can see, that's the stack class. The constructor named ArrayStack() accepts an integer. That integer is to initialize the stack to that specific size. If you later try to push() more integers onto the stack than this capacity, it won't work. Nothing is complete without testing, so, lets write a test driver class to test this stack.

 

public class StackTest {

	public static void main(String[] args) {
		ArrayStack s = new ArrayStack(10);
		int i, j;
		System.out.println("Start pushing elements ...");
		for (i = 0; i < 10; i++) {
			j = (int) (Math.random() * 100);
			s.push(j);
			System.out.println("push: " + j);
		}
		while (!s.isEmpty()) {
			System.out.println("pop: " + s.pop());
		}
		System.out.println("Done ;-)");
	}
}

 

It inserts ten random numbers onto the stack, and then pops them off and printing to standard output exactly what it's doing. The output from this program is:

Start pushing elements ...
push: 84
push: 92
push: 99
push: 14
push: 94
push: 3
push: 73
push: 45
push: 22
push: 19
pop: 19
pop: 22
pop: 45
pop: 73
pop: 3
pop: 94
pop: 14
pop: 99
pop: 92
pop: 84
Done ;-)

 

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself