Understanding Queuing Model and its Operations

Queue is a data structure modeled after a line of people waiting to be served. Along with stacks, queues are one of the simplest kinds of data structures. In this respect, a queue is like the line of customers waiting to be served by a bank teller. As customers arrive, they join the end of the queue while the teller serves the customer at the head of the queue. As a result, a queue is used when a sequence of activities must be done on a first-come, first-served basis.

Linear Queue real example in Bank Teller

Linear Queue real example in Bank Teller

A queue is defined as a special type of data structure where elements are inserted from one end and elements are deleted from the other end. The end from where the elements are inserted is called rear end’ and the end from where elements are deleted is called front end’.

Queue is a linear ordered list for which all insertions are made at one end of the list; all deletion (and usually all accesses) is made at the other end. (FIFO)

Performance

A straightforward analysis shows that for both these cases, the time needed to add or delete an item is constant and independent of the number of items in the queue. Thus we class both addition and deletion as an O(1) operation. For any given real machine/ operating system/ language combination, addition may take c1 seconds and deletion c2 seconds, but we aren’t interested in the value of the constant, it will vary from machine to machine, language to language, etc. The key point is that the time is not dependent on n – producing O(1) algorithms.

Once we have written an O(1) method, there is generally little more that we can do from an algorithmic point of view. Occasionally, a better approach may produce a lower constant time. Often, enhancing our compiler, run-time system, machine, etc will produce some significant improvement. However O(1) methods are already very fast, and it’s unlikely that effort expended in improving such a method will produce much real gain!

Operations

It has two main operations enqueue and dequeue. Insertion in a queue is done using enqueue function and removal from a queue is done using dequeue function. An item can be inserted at the end (rear’) of the queue and removed from the front (front’) of the queue. It is therefore, also called First-In-First-Out (FIFO) list.

Algorithm to add elements to Queue

procedure addq (item : items);

{add item to the queue q}

begin

    if rear=n then queuefull

    else begin

         rear :=rear+1;

         q[rear]:=item;

    end;

end;{of addq}

 

 

Algorithm to delete elements from queue

procedure deleteq (var item : items);

{delete from the front of q and put into item}

begin

    if front = rear then queueempty

    else begin

         front := front+1

         item := q[front];

    end;

end; {of deleteq}

 Properties

Queue has five properties – capacity stands for the maximum number of elements Queue can hold, size stands for the current size of the Queue, elements is the array of elements, front is the index of first element (the index at which we remove the element) and rear is the index of last element (the index at which we insert the element).

Application of Queues

Queues can be really helpful in simulations of various real time application. A good example can be Simulation at Airport, besides real time simulation, queuing model is also used in networking and data transmission for designing queuing model of networking, in same way it can be used in generation of random numbers, and preparing sample results and function.