Tuesday, February 17, 2015

Sorting a queue with the help of another queue

class Queue {
        int capacity = -1, front = -1, rear = -1;
        int[] queue = null;

        Queue(int size) {
                capacity = size;

                queue = new int[size];
        }

        boolean isEmpty() {
                return front == -1;
        }

        boolean isFull() {
                return  (rear+1)%capacity == front;
        }

        int getSize() {
                return (front>rear) ? (capacity - front + rear + 1) : ( (front == -1) ? 0 : rear - front + 1 ) ;
        }

        int peek() {
                if(isEmpty()) {
                        System.out.println("Queue is empty");

                        return -1;
                }

                return queue[front];
        }

        void enQueue(int data) {
                if(isFull()) {
                        System.out.println("Queue is full");

                        return;
                }

                rear = (rear+1)%capacity;

                if(front == -1)
                        front = rear;

                queue[rear] = data;
        }

        int deQueue() {
                if(isEmpty()) {
                        System.out.println("Queue is already empty");

                        return -1;
                }

                int data = queue[front];

                if(front == rear)
                        front = rear = -1;
                else
                        front = (front+1)%capacity;

                return data;
        }

        void print() {
                int tempFront = front;

                if(tempFront == -1) {
                        System.out.println("Queue is empty.");

                        return;
                }

                while(tempFront != rear) {
                        System.out.print(queue[tempFront] + ", ");
                        tempFront = (tempFront+1)%capacity;
                }

                System.out.println(queue[tempFront]);
        }
}





class SortQueue {
        static public void sortQueue(Queue q) {
                if(q.isEmpty())
                        return;

                Queue tempQ = new Queue(q.getSize());

                int qData = q.deQueue();

                tempQ.enQueue(qData);

                while(q.getSize() != 0) {
                        qData = q.peek();

                        while(tempQ.getSize() != 0 && qData < tempQ.peek())
                                q.enQueue(tempQ.deQueue());

                        tempQ.enQueue(q.deQueue());
                }

                //tempQ.enQueue(qData);

                while(!q.isEmpty())
                        tempQ.enQueue(q.deQueue());

                int sortedData = tempQ.deQueue();

                sortQueue(tempQ);

                System.out.print(sortedData + ", ");
        }

        static public void main(String[] args) {
                Queue q = new Queue(5);
                q.enQueue(3); q.enQueue(5); q.enQueue(2); q.enQueue(1); q.enQueue(4);

                q.print();

                sortQueue(q);

                System.out.println();
        }
}

No comments:

Post a Comment