Introduction

  • Queue is an abstract data structure.

Definition

  • A queue is another special kind of list, where new items are inserted at one specific end called the REAR end and delete an existing item at the other end called the FRONT end.

Features/Characteristics/Property

  • A queue works on the principle of FIFO(first in first out)/FCFS(first come first  serve)/LILO (Last in last out).
  • A queue is open at both its ends.

Operations in Queue

  • The basic operations in queue are –
(i) enqueue : When a new element is inserted at the rear end of the queue is called enqueue.
(ii) dequeue : When an existing element is removed/deleted from the front end of the queue is called dequeue.
(iii) peek() − Gets the element at the front of the queue without removing it.
(iv) isfull() − Checks if the queue is full.
(v) isempty() − Checks if the queue is empty.

Representation/Implementation of Queue

  • As in stack, a queue can also be implemented as Arrays and Linked-list.

Types of Queue

There are following types of queue used specifically in various operations –

(a) Simple/Normal Queue (b) Circular Queue (c) Deque [Double Ended Queue] (d)  Priority Queue (e) Hybrid Queue

(c) Deque [Double Ended Queue]
  • Deque is an extension/modified form of queue (to do some specific job), which provides insertion and deletion of items at both ends of the queue as per need. This data structure is called deque.
  • A deque provides four operations – 
    • enqueue-front : insertion of element at front.
    • dequeue-front : deletion of element at front.
    • enqueue-rear : insertion of  element at rear.
    • dequeue-rear : deletion of element at rear.
  • There are two variations/category of deque. They are –
    (i) Input Restricted Deque (IRD)
    (ii) Output Restricted Deque (ORD)
    • An Input restricted deque is a deque, which allows insertions at one end but allows
      deletions at both ends of the list.
    • An output restricted deque is a deque, which allows deletions at one end but allows
      insertions at both ends of the list.
(d)  Priority Queue
  • A priority queue is a collection of elements such that each element has been assigned a
    priority value such that the order in which elements are deleted and processed.
  • A priority queue follow certain rules during its processing. These are – 
     – An element of higher priority value is processed first before any element of lower
       priority.
    – Two elements with same priority are processed according to the order in which they             were added to the queue i.e. FCFS algorithm is followed.
  • A prototype of a priority queue is time sharing system.
  •  An efficient implementation for the Priority Queue is to use heap, which in turn can be
    used for sorting purpose.

Advantages

Disadvantages

Uses/Applications

 438 total views,  1 views today


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.