103 lines
2.0 KiB
C++
103 lines
2.0 KiB
C++
/*
|
|
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
|
|
|