Abstract Data Type implementation in Procedural Programming

Question

I have a question for the more advanced OOP developers here. I am currently a CS student. We learned a Procedural Programming in Java the first semester where ADT was introduced. I understand the theory and the idea of why ADT is good and what are the benefits of it but it seems quite difficult for me to implement it in code. I get confused and lost. In addition to that our exit test was on paper (we had to write around 200 line of code on paper) and I found it difficult. Are there any tips before starting to construct the program? For instance, do you guys already know how many methods and what method what it will return and have as a formal argument before you start to write the code?

Answer 1

You can approach it programming-style.

First, you need to define an interface for the ADT. Just write down its name and what it does.

Example:

ADT: Integer Stack

• void push(int element) - adds an element to the top of stack
• int pop() - removes and returns an element from the top of stack
• int peek() - returns the value of top. no removal of value
• boolean isEmpty() - returns true if the stack is empty
• int size() - returns the number of element in the stack.
• void print() - print all values of stack

Next is you need to decide on its implementation. Since ADT is about storage, it will be good to decide on storage strategy first.

Example:

ADT: Integer Stack

Implementation: Array Integer Stack

• Implements an int stack using Java's built-in array functionality.
• Since array is a static collection, i need to use an integer variable to track "top"

When everything is set, you can now proceed to coding.

public interface IntegerStack {
  void push(int e);
  int pop();
  int peek();
  boolean isEmpty();
  int size();
  void print();
}

public class ArrayIntegerStack implements IntegerStack {
  private static final int INITIAL_TOP_INDEX = -1;

  private int topIndex = INITIAL_TOP_INDEX;
  private int[] stackValue = new int[Integer.MAX_VALUE];

  @Override
  public void push(int element) {
    stackValue[++topIndex] = element;
  }

  @Override
  public int pop() {
    return stackValue[topIndex--];
  }

  @Override
  public int peek() {
    return stackValue[topIndex];
  }

  @Override
  public boolean isEmpty() {
    return INITIAL_TOP_INDEX == topIndex;
  }

  @Override
  public int size() {
    return topIndex + 1;
  }

  @Override
  public void print() {
    for (int i = 0; i <= topIndex; i++) {
      System.out.println(stackValue[i]);
    }
  }
}