/*
 Written by: Iurii Tatishchev
 =================================
   Queue template
*/
#ifndef QUEUE_ADT_H
#define QUEUE_ADT_H

template<class T>
class Queue {
private:
    // Structure for the stack nodes
    struct QueueNode {
        T value;             // Value in the node
        QueueNode *next;     // Pointer to next node
    };

    QueueNode *front;        // Pointer to the first node
    QueueNode *rear;         // Pointer to the last node
    int length;              // Number of nodes in the queue

public:
    Queue() { front = rear = nullptr; length = 0; }  // Constructor
    ~Queue();                                        // Destructor

    // Queue operations
    bool isEmpty() { return length == 0; }

    bool push(T);

    T pop();

    T peek() { return front->value; }

    T peekRear() { return rear->value; }

    int getLength() { return length; }
};

/*
  Member function push: inserts the argument into the queue
*/
template<class T>
bool Queue<T>::push(T item) {
    QueueNode *newNode; // Pointer to a new node

    // Allocate a new node and store item there.
    newNode = new QueueNode;
    if (!newNode)
        return false;
    newNode->value = item;
    newNode->next = nullptr;

    // Update links and counter
    if (!front) // front is NULL: empty queue
        front = newNode;
    else
        rear->next = newNode;

    rear = newNode;
    length++;

    return true;
}

/*
  Member function deletes the value at the front
  of the queue and returns it.
  Assume queue has at least one node
*/
template<class T>
T Queue<T>::pop() {
    // Save item to return.
    T item = front->value;

    // Save pointer to old front to delete it
    QueueNode* oldFront = front;

    // Set front to next node and delete old front
    front = front->next;
    delete oldFront;

    // Update length
    length--;

    return item;
}

/*
   Destructor
*/
template<class T>
Queue<T>::~Queue() {
    while (front != nullptr) {
        QueueNode* nextNode = front->next;
        delete front;
        front = nextNode;
    }
}

#endif