08.QUEUES
SYNTAX
DEFINITIONS
QUEUE
a queue is a set of elements of the same type
new elements are added at one end (called the back, rear, or last)
elements are to be deleted from the other end (called the head, front or first)
a queue is First-In-First-Out data structure (FIFO) or Last-In-Last-Out (LILO) concept
QUEUE BASIC OPERATIONS
isEmpty: checks whether the queue is empty
isFull: checks whether the queue is full
front: returns the 1st element of the queue
back: returns the last element of the queue
enqueue: adds a new element to the back of the queue
dequeue: removes the 1st element of the queue
PRIORITY QUEUES
priority queues is where nodes are added to the queue based on the priority
update the class Node to include a new memeber to determine the priority of the node
define a new class PriorityQueue copy of the existing class Queue
update the functions of the class PriorityQueue to take into account the new member priority
update only print, front, back, enqueue, and the copy constructor
all other functions remain similar to the functions of the class Queue
IMPLEMENTATION
UML
VISUALIZATION
SOURCE CODE
HEADER FILE: queue.h
/*################################################
# Name: Stephen Razon
# Student ID:
# Date: 240957NOV24
# Filename: queue.h
# Dependency: N/A
################################################*/
template<class Type>
struct Node
{
Type info;
Node<Type>* next;
};
class Queue{
int selfLength, selfMaxSize;
Node<Type>* selfFirst;
Node<Type>* selfLast;
public:
Queue(int); //constructor
bool isEmpty();
bool isFull();
int queueSize(); //returns the number of nodes in the queue
const void print(); //print the elements of the queue
Type front(); //returns the info of the 1st node
Type back(); //returns the info of the last node
void enqueue(const Type&); //add a new element at the end of the queue
void dequeue(); //remove the element in the front of the queue
void destroyQueue(); //remove all of the element
Queue(const Queue<Type>&); //copy constructor; makesa copy of the current queue
~Queue(); //destructor
};HEADER FILE: queueImplementation.h
/*################################################
# Name: Stephen Razon
# Student ID:
# Date: 240957NOV24
# Filename: queueImplementation.h
# Dependency: queue.h
################################################*/
#include <assert.h>
#include "queue.h"
Queue<Type>::Queue(int maxSize){
selfLength = 0;
selfMaxSize = maxSize;
selfFirst = NULL;
selfLast = NULL;
}
template<class Type>
bool Queue<Type>::isEmpty(){
return selfLength == 0;
}
template<class Type>
bool Queue<Type>::isFull(){
return selfLength == selfMaxSize;
}
template<class Type>
int Queue<Type>::queueSize(){
return selfLength;
}
template<class Type>
const void Queue<Type>::print(){
if(isEmpty())
cout << "The queue is empty, nothing to print\n";
else{
Node<Type>* current = selfFirst;
while(current != NULL){
cout << current->info << "";
current = current->next;
}
cout << "\n";
}
}
template<class Type>
Type Queue<Type>::front(){
asset(selfFirst != NULL);
return selfFirst->info;
}
template<class Type>
Type Queue<Type>::back(){
assert(selfFirst != NULL);
return selfLast->info;
}
template<class Type>
void Queue<Type>::enqueue(const Type& x){
if(isFull())
cout << "Can't insert in a full queue." << endl;
else{
Node<Type>* newNode;
newNode = new Node<Type>;
assert(newNode != NULL);
newNode->info = x;
newNode->next = NULL;
if(selfFirst == NULL){
selfFirst = newNode;
selfLast = newNode;
}
else{
selfLast->next = newNode;
selfLast = newNode;
}
selfLength++;
}
}
template<class Type>
void Queue<Type>::dequeue(){
if(isEmpty())
cout << "Empty queue. No node to delete\n";
else{
Node<Type>* current = selfFirst;
if(selfFirst == selfLast){ //one one node in the queue
delete current;
selfFirst = selfLast = NULL;
}
else{ //more than one node in the queue
selfFirst = selftFirst->next;
delete current;
}
selfLength--;
}
}
template<class Type>
Queue<Type>::Queue(const Queue<Type>& otherQueue){
Node<Type>* current; //pointer to traverse otherQueue
if(selfFirst != NULL)
destroyQueue();
selfMaxSize = otherQueue.selfMaxSize;
current = otherQueue.selfFirst; //current points to the 1st node of otherQueue
while(current != NULL){
enqueue(current->info);
current = current->next;
}
}
template<class Type>
void Queue<Type>::destroyQueue(){
Node<Type>* current
while(selfFirst != NULL){
current = selfFirst;
selfFirst = selfFirst->next;
delete current;
}
selfLast = NULL;
selfLength = 0;
}
template<class Type>
Queue<Type>::~Queue(){
cout << "The queue was destroyed\n";
destroyQueue();
}HEADER FILE: priorityQueue.h
/*################################################
# Name: Stephen Razon
# Student ID:
# Date: 240957NOV24
# Filename: priorityQueue.h
# Dependency: N/A
################################################*/
template<class Type>
struct Node
{
Type info;
int selfPriority;
Node<Type>* next;
};
template<class Type>
class PriorityQueue{
int selfLength, selfMaxSize;
Node<Type>* selfFirst;
Node<Type>* selfLast;
public:
PriorityQueue(int);
bool isEmpty();
bool isFull();
int queueSize();
const void print(); //modified
void front(Type&, int&); //modified
void back(Type&, int&); //modified
void enqueue(const Type&, const int&); //modified
void dequeue();
void destroyQueue();
PriorityQueue(const PriorityQueue<Type>&); //modified
~PriorityQueue();
};HEADER FILE: priorityQueueImplementation.h
/*################################################
# Name: Stephen Razon
# Student ID:
# Date: 240957NOV24
# Filename: priorityQueueImplementation.h
# Dependency: priorityQueue.h
################################################*/
#include <assert.h>
#include "priorityQueue.h"
template<class Type>
const void PriorityQueue<Type>::print(){
if(selfFirst == NULL)
cout << "The queue is empty, nothing to print\n";
else{
Node<Type>* current = selfFirst;
while(current != NULL){
cout << current->info << ", " << current->selfPriority << endl;
current = current->next;
}
}
}
template<class Type>
void PriorityQueue<Type>::front(Type& x, int& p){
assert(selfFirst != NULL);
x = selfFirst->info;
p = selfFirst->selfPriority; //do we really need p?
}
template<class Type>
void PriorityQueue<Type>::back(Type& x, int& p){
assert(selfFirst != NULL);
x = selfLast->info;
p = selfLast->selfPriority; //do we really need p?
}
template<class Type>
void PriorityQueue<Type>::enqueue(const Type& x, const int& p){
if (isFull())
cout << "Can't insert in a full queue." << endl;
else{
Node<Type> *newNode, *current, *prevCurrent;
newNode = new Node<Type>;
assert(newNode != NULL);
newNode->info = x;
newNode->selfPriority = p;
newNode->next = NULL;
if (selfFirst == NULL) //empty queue
selfFirst = selfLast = newNode;
else{
prevCurrent = NULL;
current = selfFirst;
while (current != NULL && current->selfPriority >= p){
prevCurrent = current;
current = current->next;
}
if (current == selfFirst){ //The node has the highest priority and will be inserted at the beginning
newNode->next = selfFirst;
selfFirst = newNode;
}
else if (current == NULL){ //The node has the least priority and will be inserted at the end
selfLast->next = newNode;
slefLast = newNode;
}
else{
newNode->next = prevCurrent->next;
prevCurrent->next = newNode;
}
}
selfLength++;
}
}
template<class Type>
PriorityQueue<Type>::PriorityQueue(const PriorityQueue<Type>& otherQueue){
Node<Type>* current; //pointer to traverse otherQueue
if (selfFirst != NULL)
destroyQueue();
selfMaxSize = otherQueue.selfMaxSize;
current = otherQueue.selfFirst; //current points to the first node of otherQueue
while (current != NULL){
enqueue(current->info, current->selfPriority);
current = current->next;
}
}Last updated