DCO10103 Object-Oriented Programming and Design

different type of containers and ADT

what is java.util.Stack?
what is java.util.Arrays ?

what is java.util.Vector ?

java.lang.Object
  |
  +-java.util.AbstractCollection
        |
        +-java.util.AbstractList
              |
              +-java.util.Vector

is a growable array of objects
an array is a homogenous aggregate (all members must be the same type, fixed size)
a class which contains fields of different type is an example of heterogeneous aggregates
are container that provides basic storage and retrieval
Abstract data type (ADT)
- a set with associate operators
- abstract (mathematical)
- defined by their functional properties, with no concern for the details of their computer representation (information hiding)
for example: ADT List
is defined as a finite sequence of elements of T together with the following operations:
1. initialize the list to be empty;
2. determine whether the list is empty or not;
3. determine whether the list is full or not;
4. find the length of the list;
5. retrieve any node from the list, provided that the list is not empty;
6. store a new node replacing the node at any position in the list, provided that the list is not empty;
7. insert a new node into the list at any position, provided that the list is not full;
8. delete any node from the list, provided that the list is not empty
List Interface and LinkedList Class
ADT Stack
- easiest kind of list to use
- operations observe last-in-first-out order
- primitive operations include
  1. initialize the list to be empty;
  2. determine whether the list is empty or not
  3. determine whether the list is full or not
  4. store a new node at last position in the list
  5. retrieve the last node from the list, provided that the list is not empty

Array implementation of a stack data type

public class Stack {
  private static final int STACKSIZE = 50;
  private int top;	 	
  private int[] items;

  public Stack() {
    items = new int[STACKSIZE];
    top = -1;
  }

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

  public boolean isFull() {
    return(top == STACKSIZE-1);
  }

  public void push(int x) {
    items[++top]=x;	
  }

  public int pop() {
    return(items[top--]);
  }
}

what if number of items exceeds 50?

Implementation of a stack using Vector (version 1)

import java.util.Vector;
public class Stack {
  private Vector items;

  public Stack() {
    items = new Vector();
  }

  public boolean isEmpty() {
    return(items.isEmpty());
  }

  public boolean isFull() {
    return(true);
  }

  public void push(int x) {
    items.add(new Integer(x));	
  }

  public int pop() {
    return( ((Integer) items.remove(items.size())).intValue() );
  }
}

or version 2

import java.util.Vector;
public class Stack extends Vector {

  public boolean isFull() {
    return(true);
  }

  public void push(int x) {
    add(new Integer(x));	
  }

  public int pop() {
    return( ((Integer) remove(size())).intValue() );
  }
}

what if you need a stack to store double or String instead of int ?

Previou page