Array-Based and Linked stack implementation

In this post we have alreday seen a Array based stack implementation.  

As with the array-based Stack implementation, the Array must be declared of fixed size when the stack is created. In the stack constructor, size serves to indicate this size. Method top acts somewhat like a current position value (because the “current” position is always at the top of the stack),as well as indicating the number of elements currently in the stack.

/** Stack ADT */
public interface Stack<E> {
	/**
	 * Reinitialize the stack. The user is responsible for reclaiming the
	 * storage used by the stack elements.
	 */
	public void clear();

	/**
	 * Push an element onto the top of the stack. @param it The element being
	 * pushed onto the stack.
	 */
	public void push(E it);

	/**
	 * Remove and return the element at the top of the stack. @return The
	 * element at the top of the stack.
	 */
	public E pop();

	/** @return A copy of the top element. */
	public E topValue();

	/** @return The number of elements in the stack. */
	public int length();
}

 

The array-based stack implementation is essentially a simplified version of the array-based list. The only important design decision to be made is which end of the array should represent the top of the stack. One choice is to make the top be at position 0 in the array. In terms of list functions, all insert and remove operations would then be on the element in position 0. This implementation is inefficient,because now every push o rpop operation wil lrequire that all elements currently in the stack be shifted one position in the array,for a cost of Θ(n) if there are n elements. The other choice is have the top element be at position n−1 when there are n elements in the stack.

In other words, as elements are pushed onto the stack, they are appended to the tail of the list. Method pop removes the tail element. In this case, the cost for each push or pop operation is only Θ(1). For the following implementation , top is defined to be the array index of the first free position in the stack. Thus, an empty stack has top set to 0, the first available free position in the array. (Alternatively, top could have been defined to be the index for the top element in the stack, rather than the first free position. If this had been done,the empty list would initialize top as −1.) Methods push and pop simply place an element into, or remove an element from, the array position indicated by top. Because top is assumed to be at the first free position, push first inserts its value into the top position and then increment stop,while pop first decrements top and then removes the top element.

 

Array-based stack class implementation.

/** Array-based stack implementation */
class AStack < E > implements Stack < E > {
  private static final int defaultSize = 10;
  private int maxSize; // Maximum size of stack 
  private int top; // Index for top Object 
  private E [] listArray; // Array holding stack
  
  /** Constructors */
  AStack() {
   this(defaultSize);
  }
  
  @SuppressWarnings("unchecked") // Generic array allocation 
  AStack(int size) { 
	  maxSize = size; 
	  top = 0; 
	  listArray = (E[])new Object[size]; // Create listArray 
  }
  
  /** Reinitialize stack */
  public void clear() {
   top = 0;
  }
  
  /** Push "it" onto stack */
  public void push(E it) {
   assert top != maxSize: "Stack is full";
   listArray[top++] = it;
  }
  
  /** Remove and top element */
  public E pop() {
   assert top != 0: "Stack is empty";
   return listArray[--top];
  }
  
  /** @return Top element */
  public E topValue() {
   assert top != 0: "Stack is empty";
   return listArray[top - 1];
  }
  
  /** @return Stack size */
  public int length() {
   return top;
  }
}

 

Linked stack class implementation

/** Linked stack implementation */
class LStack < E > implements Stack < E > {
  private Link < E > top; // Pointer to first element 
  private int size; // Number of elements
  
  /** Constructors */
  public LStack() {
   top = null;
   size = 0;
  }
  
  public LStack(int size) {
   top = null;
   size = 0;
  }
  
  /** Reinitialize stack */
  public void clear() {
   top = null;
   size = 0;
  }
  
  /** Put "it" on stack */
  public void push(E it) {
   top = new Link < E > (it, top);
   size++;
  }
  
  /** Remove "it" from stack */
  public E pop() {
   assert top != null: "Stack is empty";
   E it = top.element();
   top = top.next();
   size--;
   return it;
  }
  
  /** @return Top value */
  public E topValue() {
   assert top != null: "Stack is empty";
   return top.element();
  }
  
  /** @return Stack length */
  public int length() {
   return size;
  }
}

 

Algorithm 12 core java 12

FOLLOW US ON LinkedIn



Explore Tutu'rself