Recursive function to reverse an array implementation of a queue in Java

Farenhyte 0
Viewed 36
import java.util.Scanner;

class ed {
    int fr, r;
    int q[];
    int n;

    ed(int x) {
        n = x;
        fr = -1;
        r = -1;
        q = new int[n];
    }

    void enque(int n) {
        int val = n;
        while (r < n-1) {
            if (r==n-1) {
                System.out.println("Overflow");
                break;
            }
            else if (fr==-1 && r==-1) {
                fr=0;
                r=0;
                q[r] = val;
            }
            else {
                r += 1;
                q[r] = val;
            }
        }
    }
    void deque() {
        if (fr==-1 && r==-1) {
            System.out.println("Underflow");
        }
        else if (fr==r) {
            fr=-1;
            r=-1;
        }
        else {
            fr += 1;
        }
    }
    void reverse(int[] q) {
        int a = q[0];
        deque();
        reverse(q);
        enque(a);
    }
    void printq() {
        for (int i = fr; i<=r; i++) {
            System.out.print(q[i] + " ");
        }
    }
}

public class q1 {

    static Scanner f = new Scanner (System.in);
    public static void main(String[] args) {
        
        int n = f.nextInt();
        ed que = new ed(n);
        for (int i=0; i<n; i++) {
            int x = f.nextInt();
            que.enque(x);
        }
        // que.deque();

        // que.printq();
        que.reverse(que.q);

    }
}

My aim is to reverse a queue (Array) using a recursive function, but in VS Code, the loop is running infinite times and I'm not getting a chance to see the error. I'd like to know my mistake, and any improvement is highly appreciated. The class ed contains a constructor which initializes the array and the front, rear values. Enque method adds an element to the queue at the rear, deque method removes the front element. Reverse method takes an array input (queue), stores the foremost element in the variable a, deques it, calls itself, then enques it at the back. VS Code is showing the error at line 48 (reverse(q), when it calls itself) but it's not showing the error as it's so far up.

queue data-structures java recursion arrays
1 Answers

A lot of things are not going the right way in your queue implementation using arrays. Like, in enque function, you can fill values from rear = 0 to rear = n - 1, because you have n positions available in the q array.

Your code was too long, unstructured, and a bit messy with no proper variable names, So, I didn't read it any further.

But one thing I can make out is that you need to read how to implement a queue using the array.

Now, coming to queue reversal using the recursion part. Your approach was correct, you just missed out the base case condition.

Steps for reversing queue:

  1. Your queue has some elements, we get the first element out of the queue.
  2. Then, we assume I have a recursive function that reverses the rest of the queue.
  3. In this reversed queue, I just have to push that first element to the back.

And coming to the base case, each time queue size is decreasing by 1, so at the end, the queue will become empty then we don't have to do anything, just return. THUS STOPPING THE RECURSION (which you missed).

enter image description here

Here, is my implementation if you need some reference:

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;

class Queue {
    private int front, rear, capacity;
    private int queue[];
 
    Queue(int c) {
        front = rear = 0;
        capacity = c;
        queue = new int[capacity];
    }
    
    int size() {
        return rear - front;
    }
 
    void enqueue(int data) { 
        if (capacity == rear) {
            System.out.printf("Queue is full.\n");
            return;
        }
        else {
            queue[rear] = data;
            rear++;
        }
    }
 
    void dequeue() {
        if (front == rear) {
            System.out.printf("Queue is empty.\n");
            return;
        }
        else {
            for (int i = 0; i < rear - 1; i++) {
                queue[i] = queue[i + 1];
            }
            if (rear < capacity)
                queue[rear] = 0;
 
            rear--;
        }
    }
    
    int front() {
        if (front == rear) {
            System.out.printf("\nQueue is Empty.\n");
            return -1;
        }
        return queue[front];
    }
 
    void print() {
        int i;
        if (front == rear) {
            System.out.printf("Queue is Empty.\n");
            return;
        }
 
        for (i = front; i < rear; i++) {
            System.out.printf(" %d, ", queue[i]);
        }
        System.out.println("");
        return;
    }
}


class GFG {
    static Scanner scanner = new Scanner(System.in);
    
    public static void reverseQueue(Queue queue) {
        if (queue.size() == 0) {
            return;
        }
        
        int frontElement = queue.front();
        queue.dequeue();
        reverseQueue(queue);
        queue.enqueue(frontElement);
    }
    
    public static void main (String[] args) {
        int queueSize = scanner.nextInt();
        
        Queue queue = new Queue(queueSize);
        for (int i = 0; i < queueSize; i++) {
            int element = scanner.nextInt();
            queue.enqueue(element);
        }
        
        queue.print();
        reverseQueue(queue);
        queue.print();
    }
}

You can comment if anything is wrong, or need more clarification.

sachuverma0
Related