EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Queue in Data Structure
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Queue in Data Structure

By Savi JaggaSavi Jagga

Queue in Data Structure

Introduction to Queue in Data Structure

It is a type of linear data structure which follow the first in first out(FIFO) approach. This means the element that is inserted first will be removed first. The queue is said to have 2 ends, one from where the element is inserted is known as the REAR end, and the end where the element is deleted is known as FRONT. In the queue, one end (REAR) is always used to enqueue, and the other (FRONT) is used to dequeue. The queue data structure is similar to the queue at the bus stand where the passenger who comes first will board the bus first.

Queue Data Structure4

How to Create a Queue in Data Structure?

The queue can be created using below 2 data structures.:

1. Using Array

In this representation, an array is declared with N number of elements capacity and 2 indices FRONT and REAR are maintained. In the case of insertion and deletion of elements in the queue, indices are updated accordingly.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Example: Let the Queue of 7 elements

Queue Data Structure3

Here FRONT =0 and REAR =4. In case an element is inserted, REAR becomes REAR+1, i.e. 5 and element is inserted at Queue[5] position.

2. Using the Linked List

Sometimes the number of elements in the queue is not specified in the start; thus, a linked list represents a queue of elements. In this case, a structure is created having an integer key and a pointer as its elements. And 2 such structure variables are created to point the front and queue element of the array.

integer key and a pointer

In case of inserting a new element in the queue REAR end of the queue is updated to point to the new location.

All in One Data Science Bundle(360+ Courses, 50+ projects)
Python TutorialMachine LearningAWSArtificial Intelligence
TableauR ProgrammingPowerBIDeep Learning
Price
View Courses
360+ Online Courses | 50+ projects | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (86,527 ratings)

REAR end

Structure of Linked List Node:

Struct QNode
{ int key;
QNode* next;
}
QNode *FRONT * REAR;

Here key consists of the elements present in the Queue and next represent the pointer to that element.

How to Insert an Element in a Queue?

Insertion in a queue occurs at the REAR end of the queue. This process is also known as enqueue.

Algorithm: Following is the algorithm for inserting an element in a queue.

  1. Check if a queue is full, FRONT = REAR+1. or (REAR= MAXSIZE of QUEUE and FRONT =0) then OVERFLOW exists thus exit.
  2. Else if FRONT =REAR =-1 then REAR=FRONT=0.
  3. Else REAR = REAR +1 and QUEUE[REAR] = Item.

Explanation: In the above algorithm, it is checked if the queue is full or not by checking If FRONT =REAR +1 or FRONT =0 and REAR = MAX. In this case, the Item can not be inserted into the Queue. Otherwise, if there is no element in the queue, both FRONT and REAR are incremented to 0 and the Item is inserted at the REAR end.

How to Delete an Element in a Queue?

Deletion in a queue occurs at the FRONT end. Thus in case FRONT < 0, indicates there is no element in the queue. Such a situation is known as underflow. To delete an element from a queue, one should also see FRONT of the queue has that value must contain that value. If not, then it needs to be updated after reading the value from the FRONT, it needs to be updated. There are 3 possible situations in case of a queue.

  • FRONT == REAR !=0: This indicates there is only one element in the array. Thus after deletion is performed, FRONT will become 0.
  • FRONT = MAX(Queue): Then FRONT will be equal =1, if deletion is performed.
  • FRONT = FRONT +1.

Algorithm: Following is the algorithm for deletion in a queue.

  1. Check if FRONT < 0, if there is an underflow situation in the queue, then exit.
  2. Item := Queue[FRONT].
  3. If FRONT = REAR then set FRONT =REAR=NULL. Else if FRONT = MAXSIZE(QUEUE) then set FRONT =0;
  4. SET FRONT=FRONT+1.
  5. Exit.

Explanation: First, the underflow situation is checked, then the variable Item is checked to become a front element of the queue. Now in case FRONT =REAR of the queue, both will become NULL after deletion of the element. Otherwise if FRONT = Max capacity of the queue then FRONT is updated as 0. Otherwise, FRONT is updated to FRONT+1.

Applications of Queue in a Data Structure

The queue is used in situations where we need a process to run in First in First Out order. It is beneficial to apply queue data structure in situations where data need not transfer synchronously.

Breadth-First Search: This is one of the traversal method used to traverse the nodes of a tree. Here a queue is maintained of the adjacent nodes of the current node that needs to be traversed before going to the next level of depth.

Single Shared Resources: The queue is used to maintain the order in which a single resource needs to be provided to various requesting processes. Operating systems also use a queue for maintaining the processes that need to be pulled for execution from its waiting states such as priority queues.

MM1 Queue: This is a queuing model that is being used to model various real-world situations. Following are ways to categorize its usage:

  • A single Server is available.
  • A non-empty queue has an exponential distribution of its service time with rate mu per minute.
  • A queue has an inter-arrival time also has an exponential distribution of lambda per minute.

Conclusion

The queue data structure is a linear type of data structure that is used to store the elements. In this data structure elements are stored in the FIFO technique. A queue data structure used an array or linked list during its implementation. Insertion in queue occurs at the REAR end, and deletion from queue occurs at the FRONT end. This type of data structure is used for serving various requests by a single shared resource.

Recommended Articles

This is a guide to Queue in Data Structure. Here we discuss how to create a queue in a data structure along with insert, delete an element in a queue and its application, etc. You may also look at the following articles to learn more-

  1. Arrays in Data Structure
  2. Data Structure Interview Questions
  3. Else if Statement in R
  4. Guide to Queue in C#
Popular Course in this category
All in One Data Science Bundle (360+ Courses, 50+ projects)
  360+ Online Courses |  1500+ Hours |  Verifiable Certificates |  Lifetime Access
4.7
Price

View Course

Related Courses

Oracle DBA Database Management System Training (2 Courses)4.9
SQL Training Program (7 Courses, 8+ Projects)4.8
0 Shares
Share
Tweet
Share
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2022 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

SPSS, Data visualization with Python, Matplotlib Library, Seaborn Package

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more