Queues are linear data structures that follow the First-In-First-Out (FIFO) principle, making them essential for scenarios like scheduling and buffering. Today’s problems introduced various queue implementations and applications.
1. Implement a Queue Using Arrays
Queues can be built using arrays to support operations such as enqueue, dequeue, and peek. The challenge involves handling the dynamic nature of queue pointers effectively.
import java.util.Scanner;
class Queue{
static int[] que = new int[50];
static int count = 0;
public static void Enqueue(int num){
if(count == que.length)
System.out.println("Queue is already full");
else{
count++;
que[count-1] = num;
Peek();
}
}
public static void Dequeue(){
if(count==0)
System.out.println("Queue is already empty!!");
else{
for(int i=0; i<count-1; i++){
que[i]=que[i+1];
count--;
}
}
}
public static void Peek(){
if(count==0)
System.out.println("Queue is empty!!!");
else
System.out.println("First Element is: "+que[count-1]);
}
}
public class QueueImplementation{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("What action do you want to perform:\n1. Enqueue\n2. Dequeue\n3. Peek");
int num = sc.nextInt();
switch(num){
case 1:
System.out.print("Enter the number you want to Insert: ");
Queue.Enqueue(sc.nextInt());
break;
case 2:
Queue.Dequeue();
break;
case 3:
Queue.Peek();
break;
default:
System.out.println("Invalid Input!!!!");
break;
}
}
}
}
2. Implement a Circular Queue
A circular queue is a special type of queue where the last position is connected to the first position to form a circle, efficiently using memory in fixed-size arrays.
import java.util.Scanner;
class Queue{
static int[] que = new int[50];
static int front = 0;
static int rear = 0;
static int count = 0;
public static void Enqueue(int num){
if(count == que.length-1)
System.out.println("Queue is already full");
else if(rear == que.length-1){
rear=0;
que[rear] = num;
count++;
}else if (count == 0){
que[front] = num;
count++;
}else{
rear++;
que[rear] = num;
count++;
}
Front();
Rear();
}
public static void Dequeue(){
if(count == 0)
System.out.println("Queue is already empty!!");
else if(front==que.length-1){
front = 0;
count--;
}else{
front++;
count--;
}
Front();
Rear();
}
public static void Front(){
if(count == 0)
System.out.println("Queue is empty!!!");
else
System.out.println("First Element is: "+que[front]);
}
public static void Rear(){
if(count == 0)
System.out.println("Queue is empty!!!");
else
System.out.println("Last Element is: "+que[rear]);
}
}
public class CircularQueueImplementation{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("What action do you want to perform:\n1. Enqueue\n2. Dequeue\n3. Front\n4. Rear");
int num = sc.nextInt();
switch(num){
case 1:
System.out.print("Enter the number you want to Insert: ");
Queue.Enqueue(sc.nextInt());
break;
case 2:
Queue.Dequeue();
break;
case 3:
Queue.Front();
break;
case 4:
Queue.Rear();
break;
default:
System.out.println("Invalid Input!!!!");
break;
}
}
}
}
3. Implement a Deque Using Arrays
A deque (double-ended queue) allows insertion and deletion of elements from both ends. Using arrays, this problem involved efficiently managing both ends of the queue without wasting space.
import java.util.Scanner;
public class DequeUsingArrays {
private int[] deque;
private int front, rear, size;
private static final int CAPACITY = 50;
public DequeUsingArrays() {
deque = new int[CAPACITY];
front = -1;
rear = -1;
size = 0;
}
public boolean isFull() {
return size == CAPACITY;
}
public boolean isEmpty() {
return size == 0;
}
public void insertFront(int value) {
if (isFull()) {
System.out.println("Deque is full! Cannot insert element at the front.");
return;
}
if (front == -1) {
front = 0;
rear = 0;
} else {
front = (front - 1 + CAPACITY) % CAPACITY;
}
deque[front] = value;
size++;
}
public void insertRear(int value) {
if (isFull()) {
System.out.println("Deque is full! Cannot insert element at the rear.");
return;
}
if (rear == -1) {
front = 0;
rear = 0;
} else {
rear = (rear + 1) % CAPACITY;
}
deque[rear] = value;
size++;
}
public void deleteFront() {
if (isEmpty()) {
System.out.println("Deque is empty! Cannot remove element from the front.");
return;
}
front = (front + 1) % CAPACITY;
size--;
}
public void deleteRear() {
if (isEmpty()) {
System.out.println("Deque is empty! Cannot remove element from the rear.");
return;
}
rear = (rear - 1 + CAPACITY) % CAPACITY;
size--;
}
public int getFront() {
if (isEmpty()) {
System.out.println("Deque is empty!");
return -1;
}
return deque[front];
}
public int getRear() {
if (isEmpty()) {
System.out.println("Deque is empty!");
return -1;
}
return deque[rear];
}
public void display() {
if (isEmpty()) {
System.out.println("Deque is empty!");
return;
}
System.out.print("Deque: ");
int i = front;
for (int j = 0; j < size; j++) {
System.out.print(deque[i] + " ");
i = (i + 1) % CAPACITY;
}
System.out.println();
}
public static void main(String[] args) {
DequeUsingArrays deque = new DequeUsingArrays();
Scanner sc = new Scanner(System.in);
while (true) {
System.out.println("What action do you want to perform:\n1. Insert Rear\n2. Insert Front\n3. Delete Front\n4. Delete Rear\n5. Display");
int num = sc.nextInt();
switch(num){
case 1:
System.out.print("Enter element you want to insert:");
deque.insertRear(sc.nextInt());
break;
case 2:
System.out.print("Enter element you want to insert:");
deque.insertFront(sc.nextInt());
break;
case 3:
deque.deleteFront();
break;
case 4:
deque.deleteRear();
break;
case 5:
deque.display();
break;
default:
System.out.println("Invalid Operation!!!");
break;
}
}
}
}
4. Reverse First K Elements of a Queue
This problem requires reversing the first kkk elements of a queue while maintaining the order of the remaining elements. A combination of stack and queue operations is used to achieve the reversal of the first kkk elements, which demonstrates how multiple data structures can interact.
import java.util.*;
public class ReverseFirstKElements {
static class MyQueue {
int[] queue;
int front, rear, size;
int capacity;
MyQueue(int capacity) {
this.capacity = capacity;
this.queue = new int[capacity];
this.front = 0;
this.rear = -1;
this.size = 0;
}
void enqueue(int element) {
if (size == capacity) {
System.out.println("Queue is full!");
return;
}
rear = (rear + 1) % capacity;
queue[rear] = element;
size++;
}
int dequeue() {
if (size == 0) {
System.out.println("Queue is empty!");
return -1;
}
int value = queue[front];
front = (front + 1) % capacity;
size--;
return value;
}
boolean isEmpty() {
return size == 0;
}
boolean isFull() {
return size == capacity;
}
void display() {
if (size == 0) {
System.out.println("Queue is empty!");
return;
}
System.out.print("Queue: ");
for (int i = 0; i < size; i++) {
System.out.print(queue[(front + i) % capacity] + " ");
}
System.out.println();
}
}
public static void reverseFirstKElements(MyQueue queue, int k) {
if (queue.isEmpty() || k <= 0 || k > queue.size) {
System.out.println("Invalid operation.");
return;
}
Deque<Integer> stack = new ArrayDeque<Integer>();
for (int i = 0; i < k; i++) {
stack.push(queue.dequeue());
}
while (!stack.isEmpty()) {
queue.enqueue(stack.pop());
}
int remaining = queue.size - k;
for (int i = 0; i < remaining; i++) {
queue.enqueue(queue.dequeue());
}
queue.display();
}
public static void main(String[] args) {
MyQueue queue = new MyQueue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
System.out.println("Original queue:");
queue.display();
reverseFirstKElements(queue, 3);
}
}
5. Sliding Window Maximum Using a Deque
This problem involves finding the maximum element in every contiguous subarray of size k. A deque can efficiently manage the elements to solve this in O(n) time.
import java.util.*;
public class SlidingWindowMaximum {
public static List<Integer> maxSlidingWindow(int[] nums, int k) {
List<Integer> result = new ArrayList<>();
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
result.add(nums[deque.peekFirst()]);
}
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter number of array: ");
int count = sc.nextInt();
int[] nums = new int[count];
System.out.println("Enter the elements of array: ");
for(int i=0; i<count; i++)
nums[i] = sc.nextInt();
System.out.print("Enter the value of k: ");
int k = sc.nextInt();
List<Integer> maxValues = maxSlidingWindow(nums, k);
System.out.println("Sliding window maximums: " + maxValues);
}
}
Reflection
Queues are versatile structures with various real-world applications, from process scheduling to data streaming. Today’s challenges highlighted how their extensions, such as circular queues and deques, can optimize problem-solving. Excited to tackle more advanced problems next! 🚀