Question

I need a method that takes two parameters, one is Queue and other is int n, then I want to use stack and/or queue to reverse the order of n elments in Queue instance. I don't want to use recursion. I want the reverse class with method taking queue and n as parameters and a main method. I want stack class with array implementation with push and pop methods and Queue class with linkedlist implementation with methods deQueue and enQueue . I need a stack class with raw array Also need time and space complexity of the algorithm.  

For example: n=4 Original

Queue Contents: 1 3 6 7 2 1 390

New Queue Contents: 1 3 6 7 9 3 1 2

Answer 1

public class StackADT {

    private int top;
    private int items[];
    private int max;

    public StackADT(int n) {
        this.max = n;
        top = 0;
        items = new int[n];
    }

    public boolean isEmpty() {
        return top == 0;
    }

    public boolean isFull() {
        return top == max;
    }

    public void push(int item) {
        if (isFull()) throw new IllegalArgumentException();
        else items[top++] = item;
    }

    public int pop() {
        if (isEmpty()) throw new IllegalArgumentException();
        else return items[--top];
    }

    public int size() {
        return top;
    }
}

public class QueueADT {

    private int size;
    private int[] arr;

    public QueueADT(int n) {
        size = 0;
        arr = new int[n];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == arr.length;
    }

    public void enQueue(int value) {
        if (isFull()) throw new IllegalArgumentException();
        else arr[size++] = value;
    }

    public int deQueue() {
        if (isEmpty()) throw new IllegalArgumentException();
        int result = arr[0];
        for(int i = 0; i < size-1; i++) {
            arr[i] = arr[i+1];
        }
        return result;
    }

    public int getSize() {
        return size;
    }

}

public class RevereseQueue {

    // time and space complexity both are O(n)
    public void reverse(QueueADT queue) {
        StackADT stack = new StackADT(queue.getSize());
        while (!queue.isEmpty()) {
            stack.push(queue.deQueue());
        }
        while (!stack.isEmpty()) {
            queue.enQueue(stack.pop());
        }
    }

}