Queue is First In First Out, FIFO.
This means that Nodes are processed in order. They get in line, and each node is taken care of in the order added (or received).
In order to do this, we have a first and a last pointer. The first pointer points to the beginning of the list, which represents the next node to be processed and removed first.
The last pointer points to the end of the list, which represents the newest node that comes in, and thus, must wait its turn for the list to process and remove it.
The first pointer points to the node TO BE processed and thus removed.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
int removeFromFirst() { if(!isEmpty()) { Node * toRemove = first; first = first->pNext; int value = toRemove->iData; toRemove->pNext = nullptr; toRemove->iData = -1; return value; } return -1; } |
The last pointer points to the position where new, incoming nodes come in.
|
1 2 3 4 5 6 7 8 9 10 11 |
void insertLast(int data) { if(last == nullptr) { first = last = new Node(data, nullptr); } else { last->pNext = new Node(data, nullptr); last = last->pNext; } } |
