A queue is a line of persons waiting for their turn at some service counter. The service counter can be a ticketing window of a cinema hall, a railway station, etc. Depending on the type of service provided by the service counter and number of persons interested in service, there could be queues of varying lengths. The service at the service counter is on the first come first serve (FCFS) basis, i.e., in order of their arrival in the queue.

Queue at a bus stop

Suppose that at a service counter, t1 units of time are needed to provide service to a single person and on average a new person arrives at the counter after every t2 units of time. The following possibilities may arise:

  1. If t1<t2, then the service counter will have some free time. Hence, queues will be of limited lengths.
  2. If t1>t2, then the service counter will always be busy. In such a case, a queue will form very quickly and the queue length will explode.
  3. If t1=t2, then, on an average, as a person leaves the service counter, a new person arrives at the service counter. In this case, there exists the possibility of the queue length exploding to infinity.

Queues in Programming

As far as programming is concerned, a queue is a linear list in which insertion can take place at one end of the list, called the rear of the list, and deletion can take place at the other end called the front of the list. This is how a simple FCFS queue works.

In programming jargon, insert and delete operations are known as enqueue and dequeue operations.

An empty queue

Queue after enqueuing

Queue after dequeuing

Operations on Queues

The following are typical operations performed on queues:

  • createqueue(q) — to create queue as an empty queue.
  • enqueue(q,i) — to insert element i in a q.
  • dequeue(q) — to access and remove an element of queue q.
  • peek(q) — to access the first element of the queue q without removing it.
  • isfull(q) — to check whether the queue q is full.
  • isempty(q) — to check whether the queue q is empty.

Array Representation

We use the following declarations in order to represent the queue:

/*Define a queue of capacity 10*/
#define CAPACITY 10
typedef struct
{
    int front;
    int rear;
    int elements[CAPACITY];
} queue;
queue q;

Using this declaration, we can perform the various queue operations.

Types of Queues

Depending on how the array of queue elements is used, queues can be either