Abstract Data type provides only usage details of how a function or data type or data structure can be used by client and hiding implementation details from outside world, i.e., user only need know how a data type or class used, details like how it is implemented, which algorithm used in implementing the operations, how data/variables will be organized in memory are hidden.
To understand Abstract Data type(ADT), consider an example of CAR, a driver or a user only need to know what happen when he/she push accelerator, break and in which direction car goes when steering rotated. It’s not user concern how all parts (pulleys, gears, wires, bearing, engine, cylinders, pistons etc.) works together to move a car.
Why Abstract data Type?
The concept of Abstract data type related to Data abstraction in programming which separates the interface and implementation of program from user.
ADT is important part of Object-Oriented programming, an ADT implemented by specific data types or data structures in many programming languages in a formal specification. ADTs are often implemented as modules or methods declaring procedures of how an interface of operations used, sometimes with comments defining the constraints.
Some commonly used ADTs proved useful in many applications, are Container, List, Set, Multiset, Stack, Queue, Priority queue, Map, Multi-map, Graph, Tree, Double-ended queue, priority queue.
All ADTs may not be necessarily equivalent. For example, stack may or may not have a count operation for number of items pushed in and not yet popped.
Let’s study some of this ADTs briefly. All will be explained in detail separately in different post soon
List ADT
A list is an abstract data type that contains elements of same type arranged in sequential or linear order(same value may occur more than once). List ADT implemented as doubly linked list and following are its operations.
- begin() and end(): iterator pointing to first and last element of the list.
- front() and back(): return first and last element from a non- empty list.
- push_back(i) and push_front(i): push element i from back and front in to a list.
- Emplace(position, element): insert element at given position in a list.
- Emplace_back() and emplace_front(): insert element at back and front of the list.
- Unique(): This work only on sorted list deleting first occurrence repeated element.
- size(): Return the number of elements the list contain.
- isEmpty(): Return true if the list is empty, otherwise false.
- isFull(): Return true if the list is full, otherwise false.
Queue ADT
A Queue is a First-in first-out data structure contains elements of same type arranged in linear order. Operations takes place at both ends, new element added from rear end and old element deleted at front.
Operations can be performed on queue ADT are:
- enqueue(i): Insert an element i at rear end of the queue.
- dequeue(): Delete and return the front element from the queue, error if empty.
- size(): Return the number of elements queue contain.
- isEmpty(): Return true if the queue is empty, otherwise false.
- isFull(): Return true if the queue is full, otherwise false.
- First(): return first or oldest element without deleting it, if empty causes undefined behavior
- Back(): return last or newest inserted element without deleting it, if empty causes undefined behavior
Double-ended queue ADT
Double-ended queue also termed as deque is an abstract data type is a sequence container with dynamic sizes that can be expanded or contracted on both ends i.e. elements can be added or removed from head(front) and tail(rear).
- Assign(i,v): Assign ith number of times the value v to deque.
- push_front() and push_back(): insert element at the front and back of deque.
- pop_back() and pop_front(): Remove element from back and front of the deque.
- insert(position, element): Insert elements at given position in deque.
- Clear(): remove all elements from deque making its size to 0.
Stack ADT
Stack is a linear order ADT with LIFO(Last In First Out) structure where element inserted and removed from that rear or top only. Following operations can be performed:
- push(): Insert an element at top/end of the stack.
- pop(): Extract and return the element from top of the stack if not empty.
- top(): – Return the top element from stack without removing it, if stack not empty.
- size(): Return the number of elements stack contain or 0 if empty.
- isEmpty(): Return true if stack is empty, otherwise return false.
- isFull(): Return true if stack is full, otherwise return false.v
- s1.swap(s2): Swap contents of stack s11 with stack s2.
Map ADT
Maps are associative containers that store elements in combination of a key value and a mapped value. All key value are unique and are used to identify elements whose main content is the mapped value.
Following operation of maps:
- insert(key, value): insert elements according to key value. If key already exist it does not replace older one.
- erase(key): Erase elements at given key position.
- size(): Returns the number of elements the map contain.
- max_size(): Returns the maximum number of elements the map can hold.
- empty(): Returns true if map is empty else false.
Sets ADT
Sets are associative containers in which elements has to be unique. The value cannot be modified once it is added to set, it is possible to remove and add the modified value of the elements. In sets elements are associated with key.
- insert(): Insert element in to set, if element already exist gets ignored.
- erase(): remove given element from set.
- begin() & end(): return first and last element in set.
- swap(): Swap content of two sets of same type.
- clear(): Clear all the elements from set.
- empty(): Test n return true if set is empty else return false.
Please inform us if anything incorrect or want to share more information about the topic in comments.