Queue

Examples of queues :

  1. bank tailer

  2. Supermarket cashier

We will use a queue ADT that can be used to solve problems that involve waiting or ordering elements in time order , based on first in first out order (FIFO).

For example in the bank problem , variables can be :

  1. The number of available tellers.

  2. Average time spent by the customer at the teller .

  3. Number of available tellers.

Operations of a queue:

  1. Add element to the back of the queue (joiner)

  2. Remove an elemnt from the front of the queue (leaver).

  3. Retrieve the value at the front of the queue .

  4. IsEmpty

  5. IsFull

Array - Based Representaion

We use 2 pointers :

  1. front - points to the element at the head of the queue

  2. rear -  points to the element at the back of the queue

When an element is removed from the queue , the front pointer is incremented.

When an element is added to the queue , the rear pointer is incremented.

 

 

Problem : Rigthward drift

Due to the fixed size of the array , consecutive deletes would result in a reduction in its size. In the above figure, it has an array with 6 locations . After 2 delete operations , front is advanced and the available locations are reduced to 4. The locations 0 and 1 are not useable anymore.

 

 

Solution (1) : Shift array elements after each deletion OR when the array is full and space needs to be allocated .

Solution (2) : Circular queue , The front and rear rotate around the end of the array . Shifting would not be necessary .

 

 

But how can we know if the array is empty or have reached its maximum size ? Since the rear pointer is moving around the array , we would not be able to determine the these 2 conditions using it. So we will use a counter .

 

 

Pointer - Based Representation

We we a circular list and pointer pointing to the last node called rear.

fig 6.5 +6.6

 

Simulating the operations of a shop

 

Our variables (estimated time) :

 

E-Customer entry interval

S-Customer shopping time

P-Service time at the cashier's desk

T - Clock

R - simulation run time

 

T=0

Loop

T++

(1) if(T%E ==0) // time has come to accept new customer

  1. A new customer joins the shopqueue,

  2. The value of T is added to the queue

(2) if(T == front of shoppqueue +S) // customer at the front of the shop queue has finished shopping

  1. Remove from shopqueue

  2. The value (front of shopqueue+S) to the cashierqueue

(3) if(T==front of cashierqueue+P) // customer at the front of the cashierqueue has finished shopping

  1. Remove from cashierqueue

Display shopqueue

Display cashierqueue

 

Until(T==R)

 

Print the number of customers that shopped

Print the highest length of cashier queue

 

Random numbers could be used to obtain more realistic values for the variables , thus resulting in more realistic simulation results.

 

Queuing and Priorities

 

We use a priority queue. If priority have fixed numbers , such as having different 4 priorities , then a suitable solution would be to have 4 different queues , one for each priority level.