Let us recall the Node class from last time.

// define our Node class
class Node{
	private:
		int data;
		Node* next;
	public:
		// default constructor, set things to zero and null
		Node(){
			data = 0;
			next = nullPtr;
		}
		// a constructor that only recieves the integer part
		Node(int d){
			data = d;
			next = nullPtr;
		}
		// a constructor that recieves both parts
		Node(int d, Node* n){
			data = d;
			next = n;
		}
		// let's implement a destructor
		~Node(){
			delete next;
		}
		
		// data getter
		int getData(){
			return data;
		}
		// next getter (to get the pointer to the next node)
		Node* getNext(){
			return next;
		}
		// set data
		void setData(int d){
			data = d;
		}
		// set next node
		void setNext(Node* n){
			next = n;
		}
}

Queue

• Image
• goes by FIFO (First In First Out) or LILO (Last In Last Out)
• You add to the back, take from the front
• We need two pointers (one at the front, and one at the back)
  • head or front (pointing to the first node)
  • tail or rear (pointing to the last node)
• We can have two operations
  1. enqueue() → adds a new element at the tail of the queue
  2. dequeue() → retrieves the element at the head of the queue

class Queue(){
	private:
		// the pointer to the head and tail
		Node* head;
		Node* tail;

	public:
		// constructor
		Node(){
			head = nullptr;
			tail = nullptr;
		}
		// destructor
		~Node(){
			// the delete Node function will recursively delete everything (even tail)
			delete head;
		}

		// enque function
		void enqueue(){
			Node* p = new Node(3);
			// check if head (and therefore tail) are null (empty queue)
			if (head == nullptr){
				head = p;
				tail = p;
			}
			else{
				tail->setNext(p);
				tail = p;
			}
		}

		// deque function
		int dequeue(){
			// if our queue is empty
			if (head == nullptr)
				return -1;
			// secure our head
			Node* p = head;
			// readjust head
			head = head->getNext();
			// secure integer we want to return
			int data = p->getData();
			// we sever the link
			p->setNext(nullptr);
			// delete p and return data
			delete p;
			// make sure if the head == null after this (we have emptied our queue)
			// we don't want to keep tail dangling, so we put tail to null.
			if (head == nullptr)
				tail = nullptr;
			return data;
		} 
}

What happens when we enqueue(3)?

1. Create a new node with data value 3 pointing to NULL.
2. Relink the queue, so the next of the tail points to our new node.
3. Readjust the tail pointer to point to our new node.

What happens if queue empty?

• this means that head is NULL and tail is NULL
• the second step will fail because tail is not pointing to any Node object
• therefore, we have to add an if statement to check if the queue is empty