[go: up one dir, main page]
Scribd
Upload
27 views10 pages

Queue

Uploaded by

f2023065259
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
27 views10 pages

Queue

Uploaded by

f2023065259
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 10

University of Management and Technology,

Lahore Campus

Lab- 10 Manual
Lab Instructor: Sameer Ahmed
Department of Software Engineering
Email: Sameer_ahmed@umt.edu.pk
What is a Queue in DSA?

A queue is a linear data structure that adheres to the First In, First Out (FIFO) principle. This principle
dictates that the element added first to the queue will be the first one to be removed, akin to a queue of
people waiting in line at a bank or a ticket counter. The FIFO concept ensures that the order of
processing remains consistent with the order of arrival, making queues an essential structure for many
real-world applications.

Advantages of a Queue

1. Maintains the order of elements (FIFO).


2. Efficient for managing tasks where order matters.
3. Flexible implementation using arrays, linked lists, or libraries.

Uses:

Queues are widely utilized in scenarios where items need to be processed sequentially. For
instance:

 Task Scheduling (CPU Scheduling): In operating systems, queues manage tasks by


scheduling processes for execution based on their arrival times.
 Handling Requests: Queues are used to manage requests in various systems, such as
printer requests in a print queue and input/output buffers that handle data transfer
between different parts of a computer system.
 Real-Time Data Streaming: In real-time data streaming, queues buffer incoming data
before processing, ensuring that data is handled in the order it arrives.

Structure of a Queue:

A queue typically comprises the following components:


 Front: A pointer that indicates the first element in the queue (the oldest element).
 Rear: A pointer that indicates the last element in the queue (the newest element).
 Size: The total number of elements currently present in the queue.

Implementation:

Queues can be implemented using various data structures, including:

1. Arrays: Fixed-size arrays can be used to implement queues, although this method can be
limited by the array's capacity.
2. Linked Lists: Linked lists provide a dynamic implementation of queues, allowing for
flexible resizing and efficient memory usage.
3. STL (Standard Template Library) in C++: The std::queue container in C++ STL
offers a built-in implementation of queues, providing a convenient and efficient way to
manage queue operations.

Operations on a Queue:

Several fundamental operations can be performed on a queue:

1. Enqueue (Insertion): This operation adds an element to the rear of the queue, increasing
its size.
2. Dequeue (Deletion): This operation removes an element from the front of the queue,
decreasing its size.
3. Front: This operation allows access to the first element in the queue without removing it,
providing a peek at the oldest element.
4. IsEmpty: This operation checks whether the queue is empty, returning a boolean value.
5. Size: This operation retrieves the total number of elements currently in the queue,
providing insight into the queue's occupancy.

These components and operations make queues a versatile and essential data structure in computer
science, used to manage and process data in a structured and orderly manner.

#include <iostream>
using namespace std;

class Que {
int front, rear, size;
int* queue; // Pointer to dynamically allocated array

public:
// Constructor to initialize the queue with a dynamic
size
Que(int s) {
size = s;
front = -1;
rear = -1;
queue = new int[size]; // Dynamically allocate
memory for the queue
}

// Destructor to free dynamically allocated memory


~Que() {
delete[] queue; // Free the dynamically allocated
memory
}
// Check if the queue is empty
bool isEmpty() {
return (front == -1 || front > rear); // Queue is empty
if front is -1 or front > rear
}

// Check if the queue is full


bool isFull() {
return (rear == size - 1); // Queue is full if rear
reaches the last index
}

// Enqueue function to add an item to the queue


void enque(int item) {
if (isFull()) { // Check if queue is full
cout << "Queue is full" << endl;
}
else if (front == -1 && rear == -1) { // If the queue is
empty
front++;
rear++;
queue[rear] = item;
} else {
rear++;
queue[rear] = item;
}
}

// Dequeue function to remove an item from the queue


int deque() {
if (isEmpty()) { // Check if queue is empty
cout << "Queue is empty" << endl;
return -1; // Return -1 if queue is empty
} else {
int temp = queue[front]; // Get the front item
front++; // Move front pointer forward
return temp; // Return the dequeued item
}
}

// Display function to show the elements of the queue


void display() {
if (isEmpty()) { // Check if queue is empty
cout << "The queue is empty" << endl;
} else {
for (int i = front; i <= rear; i++) { // Loop through
the queue
cout << queue[i] << " "; // Display each element
}
cout << "\n";
}
}
};
int main() {
int size;
cout << "Enter the size of the queue: ";
cin >> size;

// Create a queue with user-defined size


Que q(size);

q.enque(1);
q.display();
q.enque(2);
q.display();
q.enque(3);
q.display();
q.enque(4);
q.display();
q.deque();
q.display();
q.deque();
q.display();
q.deque();
q.display();
q.deque();
q.display();
q.deque();
q.display();

return 0;
}
Tasks:

You are required to implement a queue data structure in C++ using a dynamic array. Your task is
to write a user-defined program that performs the following operations on the queue. The menu
should offer five options: Insert, Delete, Display, Peek, and Exit.

The operations to be implemented are:

1. Enqueue: Add an element to the rear of the queue.


2. Dequeue: Remove and return the element from the front of the queue.
3. Display: Display all elements in the queue from front to rear.
4. Peek: Return the front element without removing it from the queue.
5. isEmpty: Check if the queue is empty. Return true if the queue is empty, otherwise
return false.
6. isFull: Check if the queue is full. Return true if the queue is full, otherwise return
false.

Menu Options:

Your program should display a menu with the following options:

1. Insert: Enqueue an element into the queue.


2. Delete: Dequeue an element from the queue.
3. Display: Show all elements in the queue.
4. Peek: Display the front element of the queue without removing it.
5. Exit: Exit the program.

You might also like