11. Queue Implementation

 

Queue Implementation

The following Queue class in Java consists of following methods:

1. enqueue(int value): Inserts a data item at the last of the queue.
2. dequeue(): Removes and returns the first data item of the queue.
3. peek(): Returns the first data item of the queue.
4. isEmpty(): Returns true if the queue is empty.
5. isFull(): Returns true if the queue is full.

The data members of Queue class consists:

1. front: Private member to track the first element of the queue.
2. back: Private member to track the last element of the queue.
3. size: Private member to track the maximum capacity of the queue.
4. arr[]: Private array to implement the queue.

Static Implementation

class Queue {

    private int front;

    private int back;

    private int size;

    private int arr[];

    Queue(int size) {

        this.size = size;

        front = -1;

        back = -1;

        this.arr = new int[this.size];

    }

    boolean enqueue(int value) {

        if (back == size - 1)

            return false;

        if (front == -1) {

            front++;

        }

        back++;

        arr[back] = value;

        return true;

    }

    int dequeue() {

        if (front == -1)

            return -1;

        int deleted = arr[front];

        if (front == back) {

            front = -1;

            back = -1;

        } else

            front++;

        return deleted;

    }

    int peek() {

        if (front == -1)

            return -1;

        return arr[front];

    }

    boolean isEmpty() {

        if (front == -1)

            return true;

        return false;

    }

    boolean isFull() {

        if (back == size - 1)

            return true;

        return false;

    }

}

Dynamic Implementation

class Node {

    int data;

    Node next;

    Node(int data) {

        this.data = data;

        next = null;

    }

}

class Queue {

    Node front;

    Node back;

    Queue() {

        this.front = null;

        this.back = null;

    }

    boolean enqueue(int value) {

        Node node = new Node(value);

        if (front == null)

            front = node;

        else

            back.next = node;

        back = node;

        return true;

    }

    int dequeue() {

        if (front == null)

            return -1;

        int deleted = front.data;

        if (front == back) {

            front = null;

            back = null;

        } else

            front = front.next;

        return deleted;

    }

    int peek() {

        if (front == null)

            return -1;

        return front.data;

    }

    boolean isEmpty() {

        if (front == null)

            return true;

        return false;

    }

}

Queue using 2 Stacks

class QueueUsing2Stacks {

    Stack<Integer> stack1 = new Stack<Integer>();

    Stack<Integer> stack2 = new Stack<Integer>();

    void enqueue(int value) {

        stack1.push(value);

    }

    int dequeue() {

        if (stack1.isEmpty() && stack2.isEmpty())

            return -1;

        if (stack2.isEmpty()) {

            while (!stack1.isEmpty())

                stack2.push(stack1.pop());

        }

        return stack2.pop();

    }

}

Queue using Stack

class QueueUsingStack {

    Stack<Integer> stack = new Stack<Integer>();

    void enqueue(int value) {

        stack.push(value);

    }

    int dequeue() {

        if (stack.isEmpty())

            return -1;

        if (stack.size() == 1)

            return stack.pop();

        int x = stack.pop();

        int last = dequeue();

        stack.push(x);

        return last;

    }

}