Abstract Data Types

Abstract Data Type

Definition: behavior defined by a set of value and a set of operations

• Three ADTs: LIST ADT, STACK ADT, QUEUE ADT

Primary Concept of ADT:

• Spaghetti Code

• Modular Code

• Structured Programming

• Object Oriented Programming

LIST ADT

elements of same type arranged in sequential order

Operations:

• get() – Return element at any position

• insert() – Insert element at any position

• remove() – Remove first occurrence

• removeAt() – Remove at specified location

• replace() – Replace element at any position

• size() – Number of elements

• isEmpty() – True if list is empty

• isFull() – True if list is full

STACK ADT

All operations at one end — top of the stack

Operations:

• push() – Insert at top

• pop() – Remove and return top element

• peek() – Return top element without removing

• size() – Number of elements

• isEmpty() – True if stack is empty

• isFull() – True if stack is full

Stack Operations

• Push – Insert into stack

• Pop – Delete from stack

• Top – Insertion and deletion point

QUEUE ADT

insertion at end, deletion at front

Operations:

• enqueue() – Insert at end

• dequeue() – Remove and return first element

• peek() – Return front element without removing

• size() – Number of elements

• isEmpty() – True if queue is empty

• isFull() – True if queue is full

Queue Operations

• AddQ/InsertQ – Insertion

• RemoveQ/DeleteQ – Deletion

• Front – Deletion point

• Rear – Insertion point