a header file that includes Queues and Stacks Implementations

datastructure.h

#ifndef DATASTRUCTURE_H
#define DATASTRUCTURE_H
// a condition to avoid including this header file twice
#include <iostream>
#define MAX 100 
using namespace std;

struct Person {
    char *firstName;
    char *lastName;
    int age;
};
// Person structure to store 
// last name, first name and age 

void printPerson(Person p) {
    cout << "first name: " << p.firstName << ", last name: " << p.lastName << ", age: " << p.age << endl;
}
// Print person information

class LinkedList {
    // Linked list class
    // to hide the way the data structure is built from the user
public:
    // Node structure to store person data

    struct Node {
        Person person;
        Node *next;
    };

    typedef Node *PNode;
    // defining a pointer to node type 

    void init() {
        head = NULL;
    }
    // initialize by making the head point to NULL

    LinkedList() {
        init();
    }
    // at Linkedlist object created, we initialize the list  

    void traverse_forward() {
        cout << "-------------------------------------------------" << endl;
        PNode iterator = head;
        while (iterator != NULL) {
            // check if current iterator isn't NULL, (hasn't reached the end of
            // list).
            printPerson(iterator->person);
            // print person details
            iterator = iterator ->next;
            // point to the next cell
        }
        cout << "-------------------------------------------------" << endl;
    }

    void traverse_backward() {
        cout << "-------------------------------------------------" << endl;
        traverse_backward_recursive(head);
        cout << "--------------------------------------------------" << endl;
    }
    // traverse functions are independent on the child class (queue or stack ...)
    // so they are implemented in LinkedList class and inherited to its children

protected:
    PNode head;
    // make this field visible only to subclasses
private:

    void traverse_backward_recursive(PNode list) {
        if (list != NULL) {
            traverse_backward_recursive(list->next);
            printPerson(list->person);
        }
    }
    // this function is used by the traverse_backward funtion
    // so it should be hiden from children
};

class Stack : public LinkedList {
    // extend the LinkedList
public:

    Stack() : LinkedList() {
        // call the parent constructor LinkedList() and therefore also init() 
    }

    void push(Person p) {
        PNode node = new Node;
        node->person = p;
        node->next = head;
        head = node;
    }
    // Push the person structure to the stack
    // The person added is the new head

    Person pop() {
        if (head != NULL) {
            PNode node = head;
            head = head->next;
            Person val = node->person;
            delete node;
            return val;
        } else {
            cout << "Stack is empty" << endl;
        }
    }

    // Pop the person structure from the stack
    // the item to pop is the head because it's the last person in
};

class StackArray {
    Person persons[MAX];
    typedef Person * StackPointer;
    int top;
    StackPointer st;
public:

    StackArray() {
        init();
        st = persons;
        top = 0;
    }

    void init() {
        top = 0;
    }

    void push(Person p) {
        (0 + top++)st = p;
    }
    Person pop() {
        if (top != 0) {
            return (0 + --top)st;
        }
    }

    bool isEmpty() {
        return top == 0;
    }

    void traverse_forward() {
        cout << "-------------------------------------------------" << endl;

        for (int i = 0; i < top; i++) {
            printPerson(persons[i]);

        }
        cout << "-------------------------------------------------" << endl;
    }

    void traverse_backward() {
        cout << "-------------------------------------------------" << endl;
        for (int i = top - 1; i >= 0; i--) {
            printPerson(persons[i]);
        }
        cout << "--------------------------------------------------" << endl;
    }
    // Pop the person structure from the stack
    // the item to pop is the head because it's the last person in
};

class Queue : public LinkedList {
    // extend the LinkedList
public:

    Queue() : LinkedList() {
        // Call the parent constructor
        tail = NULL;
        // Set the tail to be NULL
    }

    void enqueue(Person p) {
        PNode node = new Node;
        node->next = NULL;
        node->person = p;
        if (tail != NULL) {
            tail->next = node;
            tail = node;
        } else {
            head = tail = node;
        }
    }
    // Enqueues is to add a new person to the tail of the list

    Person dequeue() {
        if (head != NULL) {
            PNode element = head;
            Person p = head->person;
            head = head->next;
            delete element;
            return p;
        } else {
            cout << "can't dequeue, queue is empty" << endl;
        }
    }
    // Dequeue is to return the value contained in the head of the list
    // to achieve FIFO
private:
    PNode tail;
    // hide this field from the user.
    // doesn't need to know how the data structure is implemented
};
#endif /* DATASTRUCTURE_H */