Abstract Data Types

Abstract Data Types

A specification for a group of values and the operations on those values that is defined conceptually and independently of any programming language

Defining ADT in an interface

Make an interface with the abstract methods as the operations that can be done to that ADT

ADT Stack

This ADT organizes its entries according to the order in which they were added (the newest entry is at the top, the oldest entry is at the bottom). You typically cannot search for a particular entry in a stack. LAST-IN-FIRST-OUT

Top entry in a stack

The newest item among the items currently in a stack

Operation "push"

The operation that adds an entry to a stack

Operation "pop" (pull)

The operation that removes an entry from the stack

Operation "peek" (getTop) for stack

The operation that retrieves the top entry of the stack without removing it

Implementation of a stack in an array

The last occupied element in the array should be the top entry in the stack because this makes it easier to pop an element from the stack (no need to shift elements). Once your remove an element from the array, you can set it to be null.

ADT Set

A collection of entries that does not have to be in any particular order but cannot have duplicates

ADT Queue

Basically a waiting line. FIRST-IN-FIRST-OUT. The item added most recently is at the back of a queue (or at the back of the waiting line). The queue has no search operation

Removing entries from Stack and Queue

STACK: the entries will be in REVERSE chronological order (beginning with the most recent and ending with the first item added to the stack)
QUEUE: the entries will be in chronological order, beginning with the first item added to the queue

Operation "enqueue" (put)

The operation that adds an entry to a queue

Operation "dequeue" (get)

The operation that removes an entry from a queue

Operation "getFront"

The operation that retrieves the queue's front entry without changing the queue in any way

Implementation of a queue in an array

The front element is the first element in the array. When adding an element, add it to the index to the right of the previous back element. When removing, remove the front element. When adding and removing, don't move the other elements. When the queue section is at the end, wrap around the array as if it was a circular array.

ADT Priority Queue

Organizes objects according to their priorities. You can make anything be a symbol for the priority (like integers). Perhaps use compareTo to compare the priorities of different objects

Operation "add(T newEntry)"

The operation that adds the newEntry into the priority queue

Operation "remove"

The operation that removes and retrieves the item with the highest priority

Operation "peek" for priority queue

The operation that retrieves the item with the highest priority

Implementation of a priority queue in an array

The entry with the highest priority should occur at the end of the array, so removing it would leave the other entries in their present places

ADT Map

A Map is an interface that represents a collection of entries that consists of keys and their values, where each key is associated with a single value.

ADT Heap

A COMPLETE binary tree in which every node's value is smaller than its children's' values (This means that the root has always the smallest value)

Implementation of a heap in an array

Leave index zero empty. In index 1, place the root. Keep on going through the heap from left to right and going to the level beneath when you went through the rightmost node in the level