Hey y’all! Today on the ninth day of this challenge I’ll be solving five problems related to queue. You can checkout my github repository, I upload the solutions there as well. Let’s begin solving today’s questions :)
1. To implement queue using arrays.
Implementing a queue in c++ can be done using the STL, but we’ll implement it from scratch using classes so that we learn the implementation and logic behind it. Queue is a linear data structure in which an element can be added from the “front“ and deleted from “rear“. It follows the FIFO (First-In-First-Out) principle. It is similar to queues in real life, like when we are buying tickets. Let’s see the code on how to implement it.
Code:
// To impelement queue using array
#include<iostream>
using namespace std;
#define MAX 100
class queue{
int arr[MAX];
int front,rear;
public:
queue(){
front=-1;
rear=-1;
}
void enqueue(int data){
if(front==-1 && rear==-1){
front++;
rear++;
arr[rear]=data;
}
else if(rear==MAX-1){
cout<<"Queue is full"<<endl;
}
else{
rear++;
arr[rear]=data;
}
}
void dequeue(){
if(front==-1 && rear==-1){
cout<<"Queue is empty"<<endl;
}
else if(front==rear){
front=-1;
rear=-1;
}
else{
front++;
}
}
void display(){
if(front==-1 && rear==-1){
cout<<"Queue is empty"<<endl;
}
else{
for(int i=front;i<=rear;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}
}
};
int main(){
queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
cout<<"Queue is: ";
q.display();
q.dequeue();
q.dequeue();
q.dequeue();
cout<<"Queue is: ";
q.display();
}
Output:
2. To implement a circular queue.
A circular queue is a data where the last position connects to the first position, forming a circle. It solves the problem of unused space in a regular linear queue when elements are dequeued (removed).
Code:
#include <iostream>
using namespace std;
#define MAX 100
class circular_queue {
int front, rear;
int arr[MAX];
public:
circular_queue() {
front = -1;
rear = -1;
}
void enqueue(int data) {
if ((rear + 1) % MAX == front) {
cout << "Queue is full" << endl;
} else if (front == -1 && rear == -1) {
front = rear = 0;
arr[rear] = data;
} else {
rear = (rear + 1) % MAX;
arr[rear] = data;
}
}
void dequeue() {
if (front == -1 && rear == -1) {
cout << "Queue is empty" << endl;
} else if (front == rear) {
front = rear = -1;
} else {
front = (front + 1) % MAX;
}
}
void display() {
if (front == -1 && rear == -1) {
cout << "Queue is empty" << endl;
} else {
int i = front;
while (i != rear) {
cout << arr[i] << " ";
i = (i + 1) % MAX;
}
cout << arr[rear] << endl;
}
}
};
int main() {
circular_queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
cout << "Queue is:" << endl;
q.display();
q.dequeue();
cout << "Queue after one dequeue:" << endl;
q.display();
return 0;
}
Output:
3. Solve the "first non-repeating character in a stream of characters" problem using a queue.
Code:
The "first non-repeating character in a stream" problem can be solved using a queue by maintaining a queue of characters and a frequency map. As characters come in, add them to the queue and update their frequency. If the character at the front of the queue has appeared more than once, dequeue it; the first character with a frequency of 1 is the first non-repeating character.
// To find the "first non-repeating character in a stream of characters" problem using a queue.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void firstNonRepeatingCharacter(string s){
queue<char> q;
vector<int> freq(26,0);
for(int i=0;i<s.length();i++){
q.push(s[i]);
freq[s[i]-'a']++;
while(!q.empty()){
if(freq[q.front()-'a']>1){
q.pop();
}
else{
cout<<q.front()<<" ";
break;
}
}
if(q.empty()){
cout<<-1<<" ";
}
}
cout<<endl;
}
int main(){
string s="aabc";
firstNonRepeatingCharacter(s);
return 0;
}
Output:
4. Implement a priority queue using a heap.
A priority queue is a special type of queue where:
Elements are processed based on their priority, not just the order in which they are added.
The element with the highest priority (or sometimes the lowest, depending on implementation) is removed first.
Let’s see how to implement it.
Code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class PriorityQueue {
private:
vector<int> heap;
void heapifyUp(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (heap[index] > heap[parent]) {
swap(heap[index], heap[parent]);
index = parent;
} else {
break;
}
}
}
void heapifyDown(int index) {
int size = heap.size();
while (true) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < size && heap[left] > heap[largest]) {
largest = left;
}
if (right < size && heap[right] > heap[largest]) {
largest = right;
}
if (largest != index) {
swap(heap[index], heap[largest]);
index = largest;
} else {
break;
}
}
}
public:
void enqueue(int value) {
heap.push_back(value);
heapifyUp(heap.size() - 1);
}
void dequeue() {
if (heap.empty()) return;
heap[0] = heap.back();
heap.pop_back();
heapifyDown(0);
}
int peek() {
if (!heap.empty()) return heap[0];
throw runtime_error("Priority queue is empty");
}
bool empty() {
return heap.empty();
}
};
int main() {
PriorityQueue pq;
pq.enqueue(10);
pq.enqueue(30);
pq.enqueue(20);
cout << "Priority Queue (Max-Heap): ";
while (!pq.empty()) {
cout << pq.peek() << " ";
pq.dequeue();
}
return 0;
}
Output:
5. To solve sliding window maximum problem using deque.
The sliding window maximum problem asks you to find the maximum element in a "window" of fixed size that slides over an array or list of numbers. We can use a “deque”, which is a double-ended-queue. It allows us to add and remove elements from both front and rear. Let’s see how to do it.
Code:
// To solve sliding window maximum problem using deque.
#include <iostream>
#include <deque>
using namespace std;
void slidingWindowMaximum(int arr[], int n, int k) {
deque<int> dq;
for (int i = 0; i < k; i++) {
while (!dq.empty() && arr[i] >= arr[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
}
for (int i = k; i < n; i++) {
cout << arr[dq.front()] << " ";
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
while (!dq.empty() && arr[i] >= arr[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
}
cout << arr[dq.front()] << endl;
}
int main() {
int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
slidingWindowMaximum(arr, n, k);
return 0;
}
Output:
This was all for today, these problems related to queue definetely helped me think about solutions in which we can implement a queue. See you tomoorrow ✨✨✨