QUEUE ASSIGNMENT

NEHA DAS

MCA SEM 1

ROLL NO = 44

1. Write code in C++ to create a queue class using a linked list. Implement methods for enqueue,
dequeue, front, and isEmpty.

class Node{
public:
int data;
Node* next;
Node(int element){
data = element;
next = NULL;
}
};

class QueueUsingLL{
private:
Node* front;
Node* rear;
public:
QueueUsingLL(){
front = NULL;
rear = NULL;
}
bool isEmpty(){
if(front==NULL && rear==NULL) return true;
return false;
}
int Front(){
if(this->isEmpty()){
return -1;
}
return front->data;
}
void enqueue(int element){
Node* temp = new Node(element);
if(this->isEmpty()){
front = temp;
}else rear->next = temp;
rear = temp;
 return;
}
int dequeue(){
if(this->isEmpty()) return -1;
else if(front!=NULL && front==rear){
//single element
rear = NULL;
}
Node* temp = front;
int element = temp->data;
front = front->next;
delete temp;
return element;
}
};

2. Implement a circular queue using an array. Include methods for enqueue, dequeue, front, and
isEmpty.

class CircularQueueUsingArr{
private:
int front;
int rear;
int size;
int* arr;
public:
CircularQueueUsingArr(int _size){
front = -1;
rear = -1;
size = _size;
arr = new int[size];
}
bool isEmpty(){
if(front==-1) return true;
return false;
}
int getFront(){
if(this->isEmpty()) return -1;
return arr[front];
}
void enqueue(int element){
int temp = rear;
rear++;
if(rear == size) rear = 0;
if(front == rear){
//if queue is full
 rear = temp;
cout<<"queue is full. can't enqueue further"<<endl;
return;
}
if(this->isEmpty()) front = 0;
arr[rear] = element;
}
int dequeue(){
if(this->isEmpty()) return -1;
int element = arr[front];
if(front == rear){
// single element
front = -1;
rear = -1;
}else{
front++;
if(front==size) front = 0;
}
return element;
}
};

3. Write C++ program to design a queue using two stacks for operations (enqueue, dequeue, front).

class QueueUsingStack{
private:
stack<int> s1;
stack<int> s2;
public:
QueueUsingStack(){
cout<<"queue created."<<endl;
}
void enqueue(int element){
while(![Link]()){
[Link]([Link]());
[Link]();
}
[Link](element);
while(![Link]()){
[Link]([Link]());
[Link]();
}
}
int dequeue(){
if([Link]()){
cout<<"queue is empty, can't dequeue."<<endl;
return -1;
}
 int top = [Link]();
[Link]();
return top;
}
int front(){
if([Link]()) return -1;
int top = [Link]();
return top;
}

};

4. Programming in C++ for a priority queue using a linked list and an array.

Priority Queue using a Linked List

#include <iostream>

using namespace std;

struct Node

int data;

int priority;

Node *next;

};

// Function to create a new node

Node *newNode(int d, int p)

Node *temp = new Node();

temp->data = d;

temp->priority = p;

temp->next = nullptr;

return temp;

}
// Function to check if the list is empty

bool isEmpty(Node *head)

return head == nullptr;

// Function to insert a new node into the priority queue

Node *enqueue(Node *head, int d, int p)

Node *temp = newNode(d, p);

if (isEmpty(head) || head->priority < p)

temp->next = head;

head = temp;

else

Node *start = head;

while (start->next != nullptr && start->next->priority >= p)

start = start->next;

temp->next = start->next;

start->next = temp;

return head;

// Function to remove the highest priority node

Node *dequeue(Node *head)

{
 if (isEmpty(head))

cout << "Queue is empty!\n";

return nullptr;

Node *temp = head;

head = head->next;

delete temp;

return head;

// Function to display the priority queue

void display(Node *head)

if (isEmpty(head))

cout << "Queue is empty!\n";

return;

Node *temp = head;

while (temp != nullptr)

cout << "Data: " << temp->data << " | Priority: " << temp->priority << endl;

temp = temp->next;

int main()

Node *pq = nullptr;

 pq = enqueue(pq, 10, 2);

pq = enqueue(pq, 20, 1);

pq = enqueue(pq, 30, 3);

cout << "Priority Queue:\n";

display(pq);

pq = dequeue(pq);

cout << "\nAfter Dequeue:\n";

display(pq);

return 0;

Priority Queue using an Array

#include <iostream>

using namespace std;

#define MAX 100

struct PriorityQueue
{

int data[MAX];

int priority[MAX];

int size;

PriorityQueue()

size = 0;

// Function to insert a new element

void enqueue(int d, int p)

if (size == MAX)

cout << "Queue is full!\n";

return;

data[size] = d;

priority[size] = p;

size++;

// Function to remove the element with the highest priority

void dequeue()

if (size == 0)

cout << "Queue is empty!\n";

return;

}
 int highestPriority = priority[0];

int idx = 0;

// Find the element with the highest priority

for (int i = 1; i < size; i++)

if (priority[i] > highestPriority)

highestPriority = priority[i];

idx = i;

// Remove the highest priority element

for (int i = idx; i < size - 1; i++)

data[i] = data[i + 1];

priority[i] = priority[i + 1];

size--;

// Function to display the priority queue

void display()

if (size == 0)

cout << "Queue is empty!\n";

return;
 }

for (int i = 0; i < size; i++)

cout << "Data: " << data[i] << " | Priority: " << priority[i] << endl;

};

int main()

PriorityQueue pq;

[Link](10, 2);

[Link](20, 1);

[Link](30, 3);

cout << "Priority Queue:\n";

[Link]();

[Link]();

cout << "\nAfter Dequeue:\n";

[Link]();

return 0;

}
5. Code for a function to reverse the contents of a queue using recursion.

#include <iostream>
#include <queue>
using namespace std;

void reverseQueue(queue<int>& q){

if([Link]()) return;
int curr = [Link]();
[Link]();
reverseQueue(q);
[Link](curr);
return;
}

int main(){
queue<int> q;
[Link](10);
[Link](20);
[Link](30);

cout<<"Queue before reversal: "<<endl;

while(![Link]()){
cout<<[Link]()<<" ";
[Link]();
}
cout<<endl;

[Link](10);
 [Link](20);
[Link](30);

reverseQueue(q);

cout<<"Queue after reversal: "<<endl;

while(![Link]()){
cout<<[Link]()<<" ";
[Link]();
}
cout<<endl;

return 0;
}

OUTPUT:

Queue before reversal:

10 20 30

Queue after reversal:

30 20 10

6. Write C++ code to create a stack using a queue and implement the required operations (push, pop,
top).

class StackUsingQueue{
queue<int> q;
public:
StackUsingQueue(){
cout<<"Stack is created."<<endl;
}
void push(int element){
int currSize = [Link]();
[Link](element);
int i = 0;
while(i<currSize){
int front = [Link]();
[Link]();
[Link](front);
i++;
}
}
int pop(){
if([Link]()){
 cout<<"Stack is empty, can not pop."<<endl;
return -1;
}
int top = [Link]();
[Link]();
return top;
}
int top(){
if([Link]()){
cout<<"Stack is empty, can not pop."<<endl;
return -1;
}
return [Link]();
}
};

7. Write code in C++ to return the k-th largest element at any point using a priority queue.

#include <iostream>
#include <queue>
using namespace std;

int kthLargest(int* arr, int size, int k){

priority_queue<int> pq;
for(int i = 0;i<size;i++){
[Link](arr[i]);
}
int ans = [Link]();
[Link]();
for(int i = 1;i<k;i++){
ans = [Link]();
[Link]();
}
return ans;
}

int main(){
int arr[] = {5,3,9,2,4,0,8};
cout<<kthLargest(arr, 7, 3)<<endl;
cout<<kthLargest(arr, 7, 5)<<endl;
return 0;
}

OUTPUT:
5