Today’s focus was on understanding queues and their variations. I worked on implementing a queue using arrays, followed by creating a circular queue and a deque. Additionally, I tackled problems like reversing the first k elements of a queue and solving the "sliding window maximum" problem using a deque. These exercises deepened my understanding of queue operations and their versatility. Ready to keep the momentum going for Day 10!
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Implement a queue using arrays.
#include <iostream>
using namespace std;
void enqueue(int queue[], int &front, int &rear, int size, int e) {
if (rear == size - 1) {
cout << "Queue has reached its max limit. Please remove elements before enqueueing.\n";
return;
}
else if (front == -1 && rear == -1) {
rear = 0;
front = 0;
}
else {
rear++;
}
queue[rear] = e;
}
void dequeue(int queue[], int &front, int &rear) {
if (front == -1 && rear == -1) {
cout << "Queue is empty, please add elements.\n";
return;
}
else if (front == rear) { // Queue becomes empty
front = -1;
rear = -1;
}
else {
front++;
}
}
void display_queue(int queue[], int front, int rear) {
if (front == -1 && rear == -1) {
cout << "Queue is empty.\n";
return;
}
cout << "The queue is: ";
for (int i = front; i <= rear; i++) {
cout << queue[i] << " ";
}
cout << endl;
}
int main() {
int size;
cout << "Enter max length of queue: ";
cin >> size;
int queue[size];
int front = -1, rear = -1;
enqueue(queue, front, rear, size, 5);
enqueue(queue, front, rear, size, 2);
enqueue(queue, front, rear, size, 9);
enqueue(queue, front, rear, size, 1);
display_queue(queue, front, rear);
dequeue(queue, front, rear);
display_queue(queue, front, rear);
dequeue(queue, front, rear);
display_queue(queue, front, rear);
return 0;
}
This program implements a simple queue using an array. The enqueue function adds an element to the rear of the queue, checking if the queue has reached its maximum size. The dequeue function removes an element from the front, resetting the front and rear to -1 when the queue becomes empty. The display_queue function prints the current elements in the queue from the front to the rear. The main function initializes the queue, performs a series of enqueue and dequeue operations, and displays the queue after each operation. It uses linear indexing, so it does not handle circular behavior.
Q2. Write a program to implement a circular queue.
#include <iostream>
using namespace std;
void enqueue(int cqueue[], int &front, int &rear, int size, int e) {
if ((rear + 1) % size == front) { // Circular queue is full
cout << "Queue has reached its max limit. Please remove elements before enqueueing.\n";
return;
}
if (front == -1 && rear == -1) { // First element insertion
front = 0;
rear = 0;
} else {
rear = (rear + 1) % size; // Move rear in a circular manner
}
cqueue[rear] = e;
}
void dequeue(int cqueue[], int &front, int &rear, int size) {
if (front == -1 && rear == -1) { // Queue is empty
cout << "Queue is empty, please add elements.\n";
return;
}
if (front == rear) { // Queue becomes empty
front = -1;
rear = -1;
} else {
front = (front + 1) % size; // Move front in a circular manner
}
}
void display_cqueue(int cqueue[], int front, int rear, int size) {
if (front == -1 && rear == -1) {
cout << "Queue is empty.\n";
return;
}
cout << "The circular queue is: ";
int i = front;
while (true) {
cout << cqueue[i] << " ";
if (i == rear) break; // Stop when front meets rear
i = (i + 1) % size; // Move i in a circular manner
}
cout << endl;
}
int main() {
int size;
cout << "Enter max length of queue: ";
cin >> size;
size++; // Increase size to differentiate full and empty conditions
int cqueue[size];
int front = -1, rear = -1;
enqueue(cqueue, front, rear, size, 5);
enqueue(cqueue, front, rear, size, 2);
enqueue(cqueue, front, rear, size, 9);
enqueue(cqueue, front, rear, size, 1);
display_cqueue(cqueue, front, rear, size);
dequeue(cqueue, front, rear,size);
display_cqueue(cqueue, front, rear, size);
dequeue(cqueue, front, rear,size);
display_cqueue(cqueue, front, rear, size);
enqueue(cqueue, front, rear, size, 7);
enqueue(cqueue, front, rear, size, 8);
display_cqueue(cqueue, front, rear, size);
return 0;
}
This program implements a circular queue using an array. The enqueue function adds an element to the rear of the queue, ensuring that the rear moves in a circular manner by wrapping around when reaching the array's end. It checks for a full queue condition by comparing the rear's next position with the front. The dequeue function removes an element from the front and moves the front circularly, resetting both pointers when the queue becomes empty. The display_cqueue function traverses and prints elements in a circular manner, starting from the front and stopping at the rear. The main function demonstrates enqueue and dequeue operations, handles the circular behavior, and dynamically displays the queue's state.
Q3. Write a program to implement a deque using arrays.
#include <iostream>
using namespace std;
void enqueue(int deque[], int &front, int &rear, int size, int e, int choice) {
if (rear - front + 1 == size) {
cout << "Deque has reached its max limit. Please remove elements before enqueueing.\n";
return;
}
if (front == -1 && rear == -1) { // First element insertion
front = 0;
rear = 0;
deque[front] = e;
}
else if (choice == 1) { // Insert at the front
if (front == 0) {
for (int i = rear; i >= front; i--) {
deque[i + 1] = deque[i];
}
rear++; // Increment rear as elements are shifted
} else {
front--; // Move front backward
}
deque[front] = e; // Insert the element
}
else if (choice == 2) { // Insert at the rear
rear++;
deque[rear] = e;
}
}
void dequeue(int deque[], int &front, int &rear, int choice) {
if (front == -1 && rear == -1) { // Queue is empty
cout << "Queue is empty, please add elements.\n";
return;
}
else if (front == rear) { // Queue becomes empty after removing the only element
front = -1;
rear = -1;
}
else if (choice == 1) { // Remove from the front
front++;
}
else if (choice == 2) { // Remove from the rear
rear--;
}
}
void display_deque(int deque[], int front, int rear) {
if (front == -1 && rear == -1) {
cout << "Deque is empty.\n";
return;
}
cout << "The deque is: ";
for (int i = front; i <= rear; i++) {
cout << deque[i] << " ";
}
cout << endl;
}
int main() {
int size;
cout << "Enter max length of deque: ";
cin >> size;
int deque[size];
int front = -1, rear = -1;
enqueue(deque, front, rear, size, 5, 2); // Insert at rear
enqueue(deque, front, rear, size, 2, 2); // Insert at rear
enqueue(deque, front, rear, size, 9, 1); // Insert at front
enqueue(deque, front, rear, size, 1, 1); // Insert at front
display_deque(deque, front, rear);
dequeue(deque, front, rear, 1); // Remove from front
display_deque(deque, front, rear);
dequeue(deque, front, rear, 2); // Remove from rear
display_deque(deque, front, rear);
return 0;
}
This program implements a deque (double-ended queue) using an array, where elements can be inserted or removed from both ends. The enqueue function allows elements to be added either at the front or rear based on the choice parameter. If the choice is 1, it inserts at the front, shifting the elements to make room; if the choice is 2, it inserts at the rear. The dequeue function removes elements from either the front or rear, adjusting the front or rear pointers accordingly. The display_deque function prints all elements from the front to the rear. The main function demonstrates insertion and deletion operations at both ends, displaying the deque's state after each operation.
Q4. Solve the "reverse first k elements of a queue" problem.
#include <iostream>
using namespace std;
void enqueue(int queue[], int &front, int &rear, int size, int e) {
if (rear == size - 1) {
cout << "Queue has reached its max limit. Please remove elements before enqueueing.\n";
return;
}
else if (front == -1 && rear == -1) {
rear = 0;
front = 0;
}
else {
rear++;
}
queue[rear] = e;
}
void dequeue(int queue[], int &front, int &rear) {
if (front == -1 && rear == -1) {
cout << "Queue is empty, please add elements.\n";
return;
}
else if (front == rear) { // Queue becomes empty
front = -1;
rear = -1;
}
else {
front++;
}
}
void display_queue(int queue[], int front, int rear) {
if (front == -1 && rear == -1) {
cout << "Queue is empty.\n";
return;
}
cout << "The queue is: ";
for (int i = front; i <= rear; i++) {
cout << queue[i] << " ";
}
cout << endl;
}
void reverse(int queue[],int front,int k){ //reverse function to reverse the first k elements
int beg=front;
int end=front+k-1;
while(beg<end){
swap(queue[beg],queue[end]);
beg++;
end--;
}
}
int main() {
int size,k;
cout << "Enter max length of queue: ";
cin >> size;
int queue[size];
int front = -1, rear = -1;
enqueue(queue, front, rear, size, 5);
enqueue(queue, front, rear, size, 2);
enqueue(queue, front, rear, size, 9);
enqueue(queue, front, rear, size, 1);
enqueue(queue, front, rear, size, 8);
enqueue(queue, front, rear, size, 6);
display_queue(queue, front, rear);
cout<<"Enter the value of k: ";
cin>>k;
reverse(queue,front,k);
display_queue(queue, front, rear);
return 0;
}
This program solves the problem of reversing the first k elements of a queue. The enqueue function inserts elements at the rear of the queue, and the dequeue function removes elements from the front. The reverse function swaps the first k elements of the queue, adjusting the indices to reverse their order. The display_queue function prints the current state of the queue. In the main function, after enqueueing several elements, the user is prompted to input the value of k. The first k elements of the queue are then reversed, and the queue's updated state is displayed.
Q5. Solve the "sliding window maximum" problem using a deque.
#include <iostream>
using namespace std;
void enqueue(int deque[], int &front, int &rear, int size, int e, int choice) {
if (rear - front + 1 == size) {
cout << "Deque has reached its max limit. Please remove elements before enqueueing.\n";
return;
}
if (front == -1 && rear == -1) { // First element insertion
front = 0;
rear = 0;
deque[front] = e;
}
else if (choice == 1) { // Insert at the front
if (front == 0) {
for (int i = rear; i >= front; i--) {
deque[i + 1] = deque[i];
}
rear++; // Increment rear as elements are shifted
} else {
front--; // Move front backward
}
deque[front] = e; // Insert the element
}
else if (choice == 2) { // Insert at the rear
rear++;
deque[rear] = e;
}
}
void dequeue(int deque[], int &front, int &rear, int choice) {
if (front == -1 && rear == -1) { // Queue is empty
cout << "Queue is empty, please add elements.\n";
return;
}
else if (front == rear) { // Queue becomes empty after removing the only element
front = -1;
rear = -1;
}
else if (choice == 1) { // Remove from the front
front++;
}
else if (choice == 2) { // Remove from the rear
rear--;
}
}
void max_element(int deque[],int &front,int &rear,int k){
int max=deque[front];
for(int i=front;i<front+k;i++){
if(deque[i]>max){
max=deque[i];
}
}
cout<<max<<" ";
}
void display_deque(int deque[], int front, int rear) {
if (front == -1 && rear == -1) {
cout << "Deque is empty.\n";
return;
}
cout << "The deque is: ";
for (int i = front; i <= rear; i++) {
cout << deque[i] << " ";
}
cout << endl;
}
int main() {
int size,n,k;
cout<<"Enter max length of deque: ";
cin>>size;
int deque[size];
int front = -1, rear = -1;
cout<<"Enter size of the array: ";
cin>>n;
int arr[n];
cout<<"Enter the elements of the array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<"Enter size of sliding window: ";
cin>>k;
int beg=0;
int end=beg+k;
int j=0;
while(end<=n){
if(front==-1 && rear==-1){
for(int i=beg;i<end;i++){
enqueue(deque,front,rear,size,arr[i],2);
}
}
else{
enqueue(deque,front,rear,size,arr[end-1],2);
dequeue(deque,front,rear,1);
}
max_element(deque,front,rear,k);
beg++;
end++;
}
return 0;
}
This program solves the problem of finding the maximum element in each sliding window of size k in an array using a deque. The enqueue function adds elements to the deque, either at the front or rear, depending on the user's choice, while the dequeue function removes elements from the front or rear. The max_element function finds the maximum value in the deque for the current window of size k. The main logic involves sliding a window across the array by adding new elements to the rear and removing the old ones from the front. After updating the deque for each window, the program prints the maximum element of the window. The process continues until all sliding windows are processed.
Today's practice allowed me to solidify my grasp on queues and their advanced variations. Implementing circular queues, deques, and solving practical problems like the "sliding window maximum" were challenging yet rewarding. Each problem provided valuable insights into queue-based algorithms. Excited to tackle even more complex problems tomorrow. Onward to Day 10!