CS210 Lab: Queues


Prelab Questions:

For a review of relevant topics click here.

Highlights of This Lab:

Lab Exercise:


Click the little computer above for a detailed description.
For this excercise you will be asked to simulate the flow of customers through a check-out line in a store.

1. Definition of a Queue

A Queue is "an abstract data type in which elements are added to the rear and removed from the front; a 'first in, first out' (FIFO) structure."
(C++ Plus Data Structures, page 226)

The main difference between a queue and a stack is that elements in a queue are put on the bottom and taken off the top (remember, in a stack, elements put on the top and taken off the top). For an everyday queue example, consider a line of customers at a bank waiting to be served. Each new customer gets in line at the rear. When the teller is ready to help a new customer, the customer at the front of the line is served. This is a queue--the first customer in line is the first one served.

1.1 Applications of a Queue

In general, queues are often used as "waiting lines". Here are a few examples of where queues would be used:

1.2 Typical Operations of a Queue

     
  • clear()
  •   Removes all the elements from a queue
         
  • bool isEmpty
  •   Determines whether the queue is empty
         
  • bool isFull
  •   Determines whether the queue is full
         
  • enqueue(ItemType item)
  •   Adds an item to the rear of the queue
         
  • ItemType dequeue()
  •   Removes front item from the queue and returns it
         
  • showStructure()
  •   Outputs the elements of a queue

    2. Application: Using Queues for Simulations

    The following section outlines an algorithm for simulating the flow of customers through a check-out line. Later, in the lab exercise, you will be given a chance to add code to complete this program.

    Waiting is the critical element of queues. The objective of a queuing system is to utilize the servers (the tellers, CPU, operators, and so on) as fully as possible, while keeping the wait time within a reasonable limit.

    So, in real life, how does a company determine the optimal compromise between the number of servers and the wait time? One way is through experience. The company tries out different numbers of servers and sees how things work out. There are two problems with this approach: 1) it takes too long, and 2) it is too expensive. A better approach is to use a computer simulation of the tellers, customers, and wait time. This approach uses queues.

    2.1 The Algorithm

    We can use a queue to simulate the flow of customers through a check-out line in a store. In this simulation we will have the following details: We can simulate the flow of customers through the line during a time period n minutes long using the following algorithm:
    Initialize the queue to empty.
    for ( minute = 0 ; minute < n ; ++minute )
    {
    	if the queue is not empty, then remove the customer at the front of the queue.
    	Compute a random number k between 0 and 3.
    	If k is 1, then add one customer to the line. 
    	If k is 2, then add two customers to the line.
    	Otherwise (if k is 0 or 3), do not add any customers to the line.
    }
    
    In addition, the algorithm will keep track of the following:

    2.2 Operations on the Queue for the Check-out Line Simulation

    Given a time of 5 minutes, the following demonstrates the operations on the queue:

    minute queue
    isempty?
      k   queue operations corresponding diagram
    0 yes   no dequeue (empty queue)
    1 enqueue(0)
    1 no    
      dequeue
    2 enqueue(1)
    enqueue(1)
    2 no    
      dequeue
    2 enqueue(2)
    enqueue(2)
    3 no    
      dequeue
    1 enqueue(3)
    4 no    
      dequeue
    0 no enqueue (k=0)

    Notice that the data in the node is the time (minute) that the "customer" joined the line. This data is used to compute the wait time of a customer.


    3. Lab Exercise


    Test Plan for "Check-out Line" Simulation Program
    Time (minutes) Total Number of
    Customers Served
    Average Wait Longest Wait
    30      
    60      
    120      
    480      

    When you are finished your program should:

    1. Take a number of minutes to run and output the number of customers served, average wait time per customer, and the longest wait time any customer encountered

    A sample output could look like this:

    Example output that shows a 22 customers served, average wait 1.6, longest wait 3

    4. Postlab Exercises

    For postlab exercices, click here.


    © Copyright: Department of Computer Science, University of Regina.