Reading
A Queue is a FIFO container, first in first out
think of this as the line at the grocery store the first person to get to the cashier is the first person to leave, all customers that come after line up
in order from the first arrived to the last arrived. Insertions to the list are always at the back of the list and removals are always from the front
we can acomplish similar to how we did a stack but we will need to variables to keep track of
"The index in the array of the front"
and
"The index in the array of the back"
when we want to add we increment the back_index
and when we want to delete we increment the front index
this maybe confusing but imagine and array of 5 elements
the index positions are 0,1,2,3,4
so we start at 0 then 1, then 2, then 3, then 4, then back to 0, then 1, then 2, then 3, then 4 ,then 0
we just keep going forward and looping around
we can use the mod operator along with our capacity like so
capacity =5
front_index=0;
front_index = (front_index+1)%capacity; // now front_index = 1
front_index = (front_index+1)%capacity; // now front_index = 2
front_index = (front_index+1)%capacity; // now front_index = 3
front_index = (front_index+1)%capacity; // now front_index = 4
front_index = (front_index+1)%capacity; // now front_index = 0
front_index = (front_index+1)%capacity; // now front_index = 1
front_index = (front_index+1)%capacity; // now front_index = 2
front_index = (front_index+1)%capacity; // now front_index = 3
front_index = (front_index+1)%capacity; // now front_index = 4
front_index = (front_index+1)%capacity; // now front_index = 0
front_index = (front_index+1)%capacity; // now front_index = 1
front_index = (front_index+1)%capacity; // now front_index = 2
front_index = (front_index+1)%capacity; // now front_index = 3
front_index = (front_index+1)%capacity; // now front_index = 4
front_index = (front_index+1)%capacity; // now front_index = 0
front_index = (front_index+1)%capacity; // now front_index = 1
see how it loops...
we can build a circular queue if we have a front and back index and move them forward..
look at this example
Line at Bank of Springfield has a capacity of 5 people
Queue is empty, lets call ToString()
front_index:0
back_index: 0
capacity:5
empty(): true
full(): false
the front and back index are set to 0
the queue is empty
--------------------------------------------------
Add "Homer" and call ToString()
front_index:0
back_index: 1
capacity:5
empty(): false
full(): false
data[0]: address: 0x559472cf2368 value: Homer
front_index stayed the same
we inserted at data[back_index] // was 0
and incremented back_index to 1
--------------------------------------------------
Add "Marge" and call ToString()
front_index:0
back_index: 2
capacity:5
empty(): false
full(): false
data[0]: address: 0x559472cf2368 value: Homer
data[1]: address: 0x559472cf2388 value: Marge
front_index stayed the same
we inserted at data[back_index] // was 1
and incremented back_index to 2
--------------------------------------------------
Add "Apu" and call ToString()
front_index:0
back_index: 3
capacity:5
empty(): false
full(): false
data[0]: address: 0x559472cf2368 value: Homer
data[1]: address: 0x559472cf2388 value: Marge
data[2]: address: 0x559472cf23a8 value: Apu
front_index stayed the same
we inserted at data[back_index] // was 2
and incremented back_index to 3
--------------------------------------------------
Add "Prinicipal Skinner" and call ToString()
front_index:0
back_index: 4
capacity:5
empty(): false
full(): false
data[0]: address: 0x559472cf2368 value: Homer
data[1]: address: 0x559472cf2388 value: Marge
data[2]: address: 0x559472cf23a8 value: Apu
data[3]: address: 0x559472cf23c8 value: Principal Skinner
front_index stayed the same
we inserted at data[back_index] // was 3
and incremented back_index to 4
--------------------------------------------------
Add "Patty" and call ToString()
front_index:0
back_index: 5
capacity:5
empty(): false
full(): true
data[0]: address: 0x559472cf2368 value: Homer
data[1]: address: 0x559472cf2388 value: Marge
data[2]: address: 0x559472cf23a8 value: Apu
data[3]: address: 0x559472cf23c8 value: Principal Skinner
data[4]: address: 0x559472cf23e8 value: Patty
front_index stayed the same
we inserted at data[back_index] // was 4
and incremented back_index to 5
--------------------------------------------------
the queue is now full so lets start to remove
cashier takes care of Homer
front_index:1
back_index: 5
capacity:5
empty(): false
full(): false
data[1]: address: 0x559472cf2388 value: Marge
data[2]: address: 0x559472cf23a8 value: Apu
data[3]: address: 0x559472cf23c8 value: Principal Skinner
data[4]: address: 0x559472cf23e8 value: Patty
front_index incremented from 0 to 1
--------------------------------------------------
cashier takes care of Marge
front_index:2
back_index: 5
capacity:5
empty(): false
full(): false
data[2]: address: 0x559472cf23a8 value: Apu
data[3]: address: 0x559472cf23c8 value: Principal Skinner
data[4]: address: 0x559472cf23e8 value: Patty
front_index incremented from 1 to 2
--------------------------------------------------
now lets add some people to the line and see it wrap around to the beginning
Add "Selma" and call ToString()
front_index:2
back_index: 0
capacity:5
empty(): false
full(): false
data[2]: address: 0x559472cf23a8 value: Apu
data[3]: address: 0x559472cf23c8 value: Principal Skinner
data[4]: address: 0x559472cf23e8 value: Patty
data[5]: address: 0x559472cf2408 value: Selma
front_index stayed the same
we inserted at data[back_index] // was 5
and incremented back_index to 0
NOTE: you may be wondering if the capacity is 5 why we are using the index 5 , wouldnt the valid indexes be 0 to 4,
this is correct but even though the capacity is 5 we actually added 1 more when we delared the array... we made it capacity+1 as it makes the logic easier if we
alwasy have one empty unused space in the arrray between our front and back
--------------------------------------------------
Add "Groundskeeper Willy" and call ToString()
front_index:2
back_index: 1
capacity:5
empty(): false
full(): true
data[2]: address: 0x559472cf23a8 value: Apu
data[3]: address: 0x559472cf23c8 value: Principal Skinner
data[4]: address: 0x559472cf23e8 value: Patty
data[5]: address: 0x559472cf2408 value: Selma
data[0]: address: 0x559472cf2368 value: Groundskeeper Willy
front_index stayed the same
we inserted at data[back_index] // was 0
and incremented back_index to 1
--------------------------------------------------
what is interesting now is that our back_index is less than our front index
but as long as we keep moving forward everything works.
take a look at this for loop that prints out the values in the array
for (unsigned int loop = front_index; loop != back_index ; loop = (loop+1)%capacity )
{
int position = loop;
oss << "data["<< position <<"]: value: " << data[position] << endl;
}