The Algorithms logo
The Algorithms
AboutDonate

Queues

P
package com.thealgorithms.datastructures.queues;

/**
 * This implements Queues by using the class Queue.
 *
 * A queue data structure functions the same as a real world queue. The elements
 * that are added first are the first to be removed. New elements are added to
 * the back/rear of the queue.
 */
class Queue {

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Max size of the queue
     */
    private int maxSize;
    /**
     * The array representing the queue
     */
    private int[] queueArray;
    /**
     * Front of the queue
     */
    private int front;
    /**
     * Rear of the queue
     */
    private int rear;
    /**
     * How many items are in the queue
     */
    private int nItems;

    /**
     * init with DEFAULT_CAPACITY
     */
    Queue() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * Constructor
     *
     * @param size Size of the new queue
     */
    Queue(int size) {
        maxSize = size;
        queueArray = new int[size];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    /**
     * Inserts an element at the rear of the queue
     *
     * @param x element to be added
     * @return True if the element was added successfully
     */
    public boolean insert(int x) {
        if (isFull()) {
            return false;
        }
        // If the back of the queue is the end of the array wrap around to the front
        rear = (rear + 1) % maxSize;
        queueArray[rear] = x;
        nItems++;
        return true;
    }

    /**
     * Remove an element from the front of the queue
     *
     * @return the new front of the queue
     */
    public int remove() {
        if (isEmpty()) {
            return -1;
        }
        int temp = queueArray[front];
        front = (front + 1) % maxSize;
        nItems--;
        return temp;
    }

    /**
     * Checks what's at the front of the queue
     *
     * @return element at the front of the queue
     */
    public int peekFront() {
        return queueArray[front];
    }

    /**
     * Checks what's at the rear of the queue
     *
     * @return element at the rear of the queue
     */
    public int peekRear() {
        return queueArray[rear];
    }

    /**
     * Returns true if the queue is empty
     *
     * @return true if the queue is empty
     */
    public boolean isEmpty() {
        return nItems == 0;
    }

    /**
     * Returns true if the queue is full
     *
     * @return true if the queue is full
     */
    public boolean isFull() {
        return nItems == maxSize;
    }

    /**
     * Returns the number of elements in the queue
     *
     * @return number of elements in the queue
     */
    public int getSize() {
        return nItems;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = front;; i = ++i % maxSize) {
            sb.append(queueArray[i]).append(", ");
            if (i == rear) {
                break;
            }
        }
        sb.replace(sb.length() - 2, sb.length(), "]");
        return sb.toString();
    }
}

/**
 * This class is the example for the Queue class
 *
 * @author Unknown
 */
public class Queues {

    /**
     * Main method
     *
     * @param args Command line arguments
     */
    public static void main(String[] args) {
        Queue myQueue = new Queue(4);
        myQueue.insert(10);
        myQueue.insert(2);
        myQueue.insert(5);
        myQueue.insert(3);
        // [10(front), 2, 5, 3(rear)]

        System.out.println(myQueue.isFull()); // Will print true

        myQueue.remove(); // Will make 2 the new front, making 10 no longer part of the queue
        // [10, 2(front), 5, 3(rear)]

        myQueue.insert(7); // Insert 7 at the rear which will get 0 index because of wrap around
        // [7(rear), 2(front), 5, 3]

        System.out.println(myQueue.peekFront()); // Will print 2
        System.out.println(myQueue.peekRear()); // Will print 7
        System.out.println(myQueue); // Will print [2, 5, 3, 7]
    }
}