CsitLabs
  • CSIT Labs
  • 1st Semester
    • Digital Logics
      • Lab 1
      • Lab 2
      • Lab 3
      • Lab 4
      • Lab 5
      • Lab6
    • IIT
    • Physics Lab Report Formet
  • 2nd Semester
    • Algorithms used in Discrete Structure class
    • Microprocessor
      • 8085 Microprocessor
        • Arithmetic and Logical Instruction Set
        • Branching Instruction Set
        • Data Transfer and Instruction Set
        • Multiply, Divide and Memory Block Operations
        • Rotate Instruction Set
        • Subroutine, Stack and BCD Conversion](Subroutine_Stack_BCD_Conversion
      • 8086 Microprocessor
        • Basic Arithmetic
        • Practice Programs for 8086 Microprocessor
        • String Processing
    • Object Oriented Programming using C++
      • File Access Pointers
      • Standard Exceptions in C++
    • Statistics-I
  • 3rd Semester
    • Computer Architecture
      • Practical labs
    • Computer Graphics
      • Practial
      • Simulation of Two Dimensional Transformation
      • Scan Conversion Algorithm
    • Data Structures and Algorithms
      • Array methods (Introduction)
      • Stack
      • Queue
      • Recursion
      • Linked List
      • Sorting Algorithms
      • Searching and Hashing Algorithms
      • Trees and Graphs
      • Lab practice
    • Numerical Method Labs
      • Lab practice
    • Statistics-II Labs
      • Confidence interval of mean assuming normal distribution
      • One Sample T test
      • Two Sample T test
      • Regression Analysis
      • Two Sample T test
      • Design_of_Experiment
        • CRD (Completely Randomized Design)
        • RBD (Randomized Block Design)
        • RBD (Randomized Block Design)
      • Non-parametric_test
        • Binomial Test
        • Cochran Q test
        • Kolmogorov-Smirnov one sample test
        • Run test
        • Friedman-F_test
          • Friedman F test
          • Friedman F test
        • Kruskal-Wallis-H_test
          • Kruskal Wallis H test
          • Kruskal Wallis H test
        • Mann-Whitney-U_test
          • Mann Whitney U test
          • Mann Whitney U test
        • Median_test
          • Median Test
          • Median Test
        • Wilcoxon-Matched-pair_signed_rank_test
          • Wilcoxon Matched pair signed rank test
          • Wilcoxon Matched pair signed rank test
  • 4th Semester
    • Artificial Intelligence
    • Computer Networks
      • Networking commands in CMD
    • DBMS Lab
    • Operating System
      • Linux Commands
    • Theory of Computation
      • Lab 1 (DFA)
      • Lab 2 (NFA)
  • 5th Semester
    • Cryptography
    • Design and Analysis of algorithms
    • Multimedia
      • Animation Creation with Blender
      • FL Studio - Simple Effect Creation
      • Macromedia FreeHand - Logo Creation
      • Audio Mixing
      • Adobe Photoshop - ID Card Creation
      • Video Editing with Adobe Premiere Pro
    • Simulation & Modeling
      • Lab 1: Random Number Generation
    • System Analysis and Design
    • Web Technology
      • Lab Assignment – I (HTML)
      • Lab Assignment – II (CSS)
      • Lab Assignment – III (JavaScript and XML)
      • Lab Assignment – IV (PHP)
      • Web Technology
        • php
          • Database connection using PHP and MySQL
          • Login form
          • Login form
  • 6th Semester
    • Compiler Design and Construction
    • NET Centric Computing
      • Class Codes
        • Authentication and Authorization in ASP.NET
        • C# Basics
      • Lab Codes
        • Practical 1
        • Practical 2
          • Number Operations Web App
          • User Registration Form
          • User Registration Console App
        • Practical 3
          • Authentication and Authorization (Claims, Roles and Policies)
          • Client side state management in ASP.NET
          • Entity Framework Core
          • Form Validation
            • React form validation
          • HTML Tag Helpers
          • MVC demonstration
          • Razor Syntax
          • Server Side State Management in ASP.NET
      • Self Projects
        • Do while programs
        • Role playing game battle challenge
        • Project overview
        • Authentication
          • wwwroot
            • lib
              • jquery-validation
                • The MIT License (MIT)
  • 7th Semester
    • Advanced Java Programming
      • Class Codes
        • Unit1-6&8
          • javafx-sdk-21.0.1
            • legal
              • javafx.graphics
                • Independent JPEG Group (IJG) JPEG v9e
                • Mesa 3-D Graphics Library v21.0.3
              • javafx.media
                • Microsoft DirectShow Samples v156905
                • GNU Glib v2.72.0
                • GStreamer v1.20.1
                • LibFFI v3.4.4
              • javafx.web
                • IBM International Components for Unicode (ICU4C) v73.1
                • xmlsoft.org: libxml2 v2.10.4
                • xmlsoft.org: libxslt v1.1.35
                • WebKit Open Source Project: WebKit v616.1
          • src
            • main
              • java
                • Unit 1: Programming in Java
                  • 2. Concepts and Topics
                • Unit 2: User Interface Components with Swing
                • Unit 3: Event Handling
                • Unit 4: Database Connectivity
                • Unit 5: Network Programming
                • Unit 6: GUI with JavaFX
        • Unit7
          • src
            • main
              • webapp
                • index
      • Lab Codes
        • Lab
          • src
            • main
              • java
                • Practical 1
                • Practical 2
                • Practical 3
                • Practical 4
                • Practical5
    • Data warehouse and Data mining
  • docs
    • Contributor Covenant Code of Conduct
Powered by GitBook
On this page
  • Basic Operations of Queue
  • Programs:
  • Working of Linear Queue
  • Enqueue Operation
  • Dequeue Operation
  • Circular Queue Data Structure
  • Circular increment in circular queue
  • How Circular Queue Works
  • Circular Queue Operations
  • Enqueue Operation
  • Dequeue Operation

Was this helpful?

  1. 3rd Semester
  2. Data Structures and Algorithms

Queue

PreviousStackNextRecursion

Last updated 8 months ago

Was this helpful?

A queue is a useful data structure in programming. It is similar to the ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the ticket.

Queue follows the First In First Out (FIFO) rule - the item that goes in first is the item that comes out first.

Basic Operations of Queue

A queue is an object (an abstract data structure - ADT) that allows the following operations:

  • Enqueue: Add an element to the end of the queue

  • Dequeue: Remove an element from the front of the queue

  • IsEmpty: Check if the queue is empty

  • IsFull: Check if the queue is full

  • Peek: Get the value of the front of the queue without removing it

Programs:

Working of Linear 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

  • check if the queue is full

  • for the first element, set the value of FRONT to 0

  • increase the REAR index by 1

  • add the new element in the position pointed to by REAR

Dequeue Operation

  • check if the queue is empty

  • return the value pointed by FRONT

  • increase the FRONT index by 1

  • for the last element, reset the values of FRONT and REAR to -1

Circular Queue Data Structure

A circular queue is the extended version of a regular queue where the last element is connected to the first element. Thus forming a circle-like structure.

Circular increment in circular queue

The circular queue solves the major limitation of the normal queue. In a normal queue, after a bit of insertion and deletion, there will be non-usable empty space.

  • Limitation of the regular Queue

    Here, indexes 0 and 1 can only be used after resetting the queue (deletion of all elements). This reduces the actual size of the queue.

How Circular Queue Works

Circular Queue works by the process of circular increment i.e. when we try to increment the pointer and we reach the end of the queue, we start from the beginning of the queue.

Here, the circular increment is performed by modulo division with the queue size. That is,

    if REAR + 1 == 5 (overflow), REAR = (REAR + 1)%5 = 0 (start of queue)

Circular Queue Operations

The circular queue work as follows:

  • two pointers FRONT and REAR

  • FRONT track the first element of the queue

  • REAR track the last elements of the queue

  • initially, set value of FRONT and REAR to -1

Enqueue Operation

  • check if the queue is full

  • for the first element, set value of FRONT to 0

  • circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would be at the start of the queue)

  • add the new element in the position pointed to by REAR

Dequeue Operation

  • check if the queue is empty

  • return the value pointed by FRONT

  • circularly increase the FRONT index by 1

  • for the last element, reset the values of FRONT and REAR to -1

  • However, the check for full queue has a new additional case:

Case 1: FRONT = 0 && REAR == SIZE - 1

Case 2: FRONT = REAR + 1

The second case happens when REAR starts from 0 due to circular increment and when its value is just 1 less than FRONT, the queue is full.

Linear Queue
Circular Queue
Priority Queue