Queue

Queue

Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.

A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops.

Queue Representation

As we now understand that in queue, we access both ends for different reasons. The following diagram given below tries to explain queue representation as data structure −

As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and Structures. For the sake of simplicity, we shall implement queues using one-dimensional array.

What is Queue?

  • Queue is a linear data structure where the first element is inserted from one end called REAR and deleted from the other end called as FRONT.
  • Front points to the beginning of the queue and Rear points to the end of the queue.
  • Queue follows the FIFO (First - In - First Out) structure.
  • According to its FIFO structure, element inserted first will also be removed first.
  • In a queue, one end is always used to insert data (enqueue) and the other is used to delete data (dequeue), because queue is open at both its ends.
  • The enqueue() and dequeue() are two important functions used in a queue.

Working of Queue

Queue operations work as follows:

Two pointers FRONT and REAR

FRONT track the first element of the queue

REAR track the last element of the queue

initially, set value of FRONT and REAR to -1

  • Enqueue Operation

  1. Check if the queue is full
  2. For the first element, set the value of FRONT to 0
  3. Increase the REAR index by 1
  4. Add the new element in the position pointed to by REAR

  • Dequeue Operation

  1. Check if the queue is empty
  2. Return the value pointed by FRONT
  3. Increase the FRONT index by 1
  4. For the last element, reset the values of FRONT and REAR to -1

Applications of queue

Due to the fact that queue performs actions on first in first out basis which is quite fair for the ordering of actions. There are various applications of queues discussed as below.

1.  Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.

2.  Queues are used in asynchronous transfer of data (where data is not being transferred at the same rate between two processes) for eg. pipes, file IO, sockets.

3.  Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.

4.  Queue are used to maintain the play list in media players in order to add and remove the songs from the play-list.

5. Queues are used in operating systems for handling interrupts.

Operations on Queue

Following are the basic operations performed on a Queue.

Complexity

Popular posts from this blog

DATA STRUCTURES-II

 UNIT – I  Tree: Header nodes, Threads, Binary search trees, Searching, Insertion and deletion in aBinary search tree , AVL search trees, Insertion and deletion in AVL search tree , m-waysearch tree, Searching, Insertion and deletion in an m-way search tree , B-trees, Searching,Insertion and deletion in a B-tree, B+tree , Huffman’s algorithm , General trees.  UNIT – II  Graphs: Warshall’s algorithm for shortest path , Dijkstra algorithm for shortest path , Operations on graphs , Traversal of graph , Topological sorting .  UNIT – III  Sorting: Internal & external sorting , Radix sort , Quick sort , Heap sort , Merge sort . Searching: Liner search, binary search, merging , Comparison of various sorting and searching algorithms on the basis of their complexity .  UNIT – IV  Files: Physical storage devices and their characteristics , Attributes of a file viz fields, records,Fixed and variable length records, Primary and secondary keys , Clas...
Read more

DATA STRUCTURES FOR BCA

UNIT – I  Introduction: Elementary data organization, Data Structure definition , Data type vs. data structure , Categories of data structures, Data structure operations, Applications of data structures, Algorithms complexity and time-space tradeoff, Big-O notataion.   Strings: Introduction, Storing strings, String operations, Pattern matching algorithms.  UNIT – II  Arrays: Introduction, Linear arrays, Representation of linear array in memory, address calculations, Traversal, Insertions, Deletion in an array, Multidimensional arrays, Parallel arrays, Sparse arrays.  Linked List: Introduction, Array vs. linked list, Representation of linked lists in memory, Traversal, Insertion, Deletion, Searching in a linked list, Header linked list, Circular linked list, Two-way linked list, Threaded lists, Garbage collection, Applications of linked lists.  UNIT – III  Stack: Introduction, Array and linked representation of stacks, Operations on stacks, Ap...
Read more

DATA STRUCTURES FOR B.TECH

DATA STRUCTURES Unit 1: Introduction :   Basic Terminologies:   C oncept of Data Structure, Choice of right Data Structure , Algorithms , how to design and develop algorithm, Complexity of algorithm.   Operations: insertion, deletion, traversal etc,   Analysis of an Algorithm. Searching:  Linear Search and Binary Search Techniques and their complexity analysis. Unit 2: Stacks  and  Queues : Stack  and  its  operations: Algorithms and their complexity analysis, Applications of Stacks: Expression       Conversion and evaluation -corresponding algorithms and complexity analysis. queue, Types of Queue: Simple  Queue, Circular Queue, Priority Queue ; Operations on each types of Queues: Algorithms and their analysis.   Unit 3 : Linked Lists:      Singly   linked  lists: Representation in memory, Algorithms of several operations:...
Read more