Queues in data structure

​

Queues

A Queue is an ordered collection of items from which items may be deleted at one end (called the ‘front’ of the queue) and into which items may be inserted at the other end (called the ‘rear’ of the queue). Since the first element inserted into a queue is the first element to be removed. For this reason a queue is sometimes called a FIFO (First-In, First-Out) list or a FCFS (First-Come, First-Serve) basis.

Example of a queue abound in the real world.

  • A line at a bank or at a bus stop
  • a queue is a checkout line at a supermarket cash register.
  • Another perhaps more relevant example of a queue can be found in a time sharing computer system where many users share the system simultaneously. Since such a system typically has single central processing unit (called the processor) and one main memory, these resources must be shared by allowing one user’s program to execute for a short time, followed by the executing of another user’s program, etc., until there is a return to the execution of the initial user’s program. The user programs that are waiting to be processed form a waiting queue. This queue may not operate on a strictly first-in, first-out basis, but on some complex priority scheme based on such factors as what compiler is being used, the execution time required, the number of print lines desired, etc. The resulting queue is sometimes called ‘priority queue’.
  • A final example of a queue is the line of cars waiting to proceed in some fixed direction at an intersection of streets. The deletion of a car corresponds to the first car in the line passing through the intersection, while an insertion to the queue consists of a car joining the end of the line of existing cars waiting to proceed through the intersection.

Algorithms for the insertion of an element to and the deletion of an element from a queue. The vector is assumed to consist of a large number of elements, enough to be sufficient to handle the variable-length property of a queue. The vector representation of a queue requires pointers ‘f’ and ‘r’ which denote the positions of its front and rear elements, respectively.

An algorithm for inserting an element in a queue is given as follows:

Procedure QINSERT (Q, F, R, N, Y)

Given F and R, pointers to the front and rear elements of a queue, a queue Q consisting of N elements, and an element Y, this procedure inserts Y at the rear of the queue. Prior to the first invocation of the procedure, F and R have been set to -1

Queues


1. [Overflow?]
     if R = N then
          Write('OVERFLOW')
          return
2. [Increment rear pointer]
    R = R + 1
3. [Insert element]
     Q[R] = Y
4. [Is front pointer properly set?]
     if f=-1 then
          f=0
5. [Finished]
      return

Algorithm for deleting an element into a Queue:

Function QDELETE(Q, F, R) Given F and R, the pointer to the front and rear elements of a queue, respectively, and the queue Q to which they correspond, this function deletes and returns the last element of the queue. Y is a temporary variable.


1. [Underflow?]
     if F=-1 then
          Write('UNDERFLOW')
          return 0;   (0 denotes an empty queue)
2. [Delete element]
     Y = Q[F]
3. [Queue empty]
     if F=R then
          F=R=-1
     else
          F = F + 1 (increment front pointer)
4. [Return element]
     return (Y)

The above algorithms cab be very wasteful of storage if the front pointer F never manages to catch up to the rear pointer R.

CIRCULAR QUEUE:

A more suitable method of representing a queue, which prevents an excessive use of memory, is to arrange the elements Q[0],Q[1]…Q[n-1] in a circular fashion with Q[0] following Q[n-1].

Trace of insertion and deletion of elements in a circular queue

An algorithm for inserting an element in a Circular queue is given as follows:

Procedure CQINSERT (Q, F, R, N, Y)

Given F and R, pointers to the front and rear elements of a circular queue, a queue Q consisting of N elements, and an element Y, this procedure inserts Y at the rear of the queue. Initially, F and R are set to -1


1. [Reset Rear Pointer]
     if R = N-1 then
          R = 0
     else R = R + 1
2. [Overflow?]
    if F = R then
          Write('Overflow')
          return
3. [Insert element]
     Q[R] = Y
4. [Is front pointer properly set?]
     if f=-1 then
          f=0
5. [Finished]
      return

Algorithm for deleting an element into a Circular Queue: Function CQDELETE(Q, F, R, N)

Given F and R, the pointer to the front and rear elements of a circular queue, respectively, and the queue Q consisting of N elements, this function deletes and returns the last element of the queue. Y is a temporary variable.


1. [Underflow?]
     if F=-1 then
          Write('UNDERFLOW')
          return 0;   (0 denotes an empty queue)
2. [Delete element]
     Y = Q[F]
3. [Queue empty]
     if F=R then
          F=R=-1
          return (Y)
4. [Increment front pointer]
      if F = N-1 THEN
          F=0
     else
          F = F + 1
     return(Y)
     

DEQUE (Double-Ended Queue) :

DEQUE is a linear list in which insertions and deletions are made to or from either end of the structure.

There are two variations of a deque, namely, the input-restricted deque and the Output-restricted deque. The input-restricted deque allows insertions at only one end, while and output-restricted deque permits deletions from only one end.

Priority Queue:

A priority queue is composed of several independent queues, each having a certain priority associated with it. The elements to be inserted into the queue possess their own priority. The priority of an element decides which queue it should enter into. Priority queues are used in applications like job scheduling within the operating system. A priority queue with three levels of priority is shown in below :

Let Queue 1 denote highest priority queue and Queue 3 denote lowest priority. When an element is enqueued, it is inserted into the queue of the corresponding priority level. When an element has to be dequeued, the element from the highest priority queue is removed first. If the elements of lower priority levels have to be removed, the queues of higher priorities should all be empty.

A Priority Queue in which we can insert elements or remove element from any position based on some property (such as priority of the task to be processed).

Ascending Priority Queue: An ascending priority queue is a collection of items into which items can be inserted arbitrarily and from which only the smallest item can be removed.

Descending Priority Queue: An ascending priority queue is a collection of items into which items can be inserted arbitrarily and from which only the largest item can be removed.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s