ADTs

1. Queue

-FIFO

We can implement in this way: 

template<typename T>

class Queue {

public:

    void enqueue(const T & item);

    T dequeue();

    T & peek()

    const T & peek() const;

    int numbebrOfItem() const;

};

- In the actual C++ STL library, it has the following functions:

push()

pop()

peek()

2. Stack

- LIFO

We can implement in this way:

template<typename T>

class Stack {

public:

    void push(const T & item);

    T pop();

    T & peek();

    const T & peek() const;

    int numberOfItem() const;

};

In the C++ STL library, it has similar functions as queue.

3. Sets

- Add

- Test if an item is in the set

- Check if the set is empty

- Take the union of two set

- intersect two sets

A variant of this ADT is a multiset. (Also called a bag) It allows the same element to appear multiple times, whereas a true set either has an object or not.

- Set in computer is finite.

- We can implement in this way:

template<typename T>

class Set {

public:

    void add(const T & item);

    bool contains(const T & item) const;

    bool numItems() const;

    void remove(const T & item);

    set<T> intersect(const Set<T> & s) const;

    set<T>unionSets(const Set<T> & s) const;

};

4. Maps

- A map tracks mapping from keys to values.

- We can implement in our ways:

template<typename K, typename V>

class Map {

public:

    void add(const K & key, const V & value);

    const V & lookup(const K & key) const;

    V & lookup(const K & key);

    bool numItems() const;

    void remove(const K & key);

};

- find 

5. Abstract Classes

- We might declare an AbstractSet like this:

template<typename T>

class Set {

public:

    virtual void add(const T & item) = 0;

    virtual bool contains(const T & item) const = 0;

    virtual bool numItems() const = 0;

    virtual void remove(const T & item) = 0;

    virtual set<T> intersect(const Set<T> & s) const = 0;

    virtual set<T>unionSets(const Set<T> & s) const = 0;

};

summary& understanding  after reading <<All of Programming>> Chapter 20