datastructures4QueueImpl

1package pkg3datastructures;2 3/*4 * datastructures4QueueImpl.java5 * --------------6 * FIFO queue as a circular buffer (ring buffer) and a quick demo of a deque.7 *8 * COMPLEXITY: enqueue/dequeue O(1); circular buffer avoids shifting elements.9 * WHEN TO USE: BFS, scheduling, producer/consumer buffers, streaming windows.10 */11public class datastructures4QueueImpl {12 13    // Fixed-capacity circular queue14    static class CircularQueue {15        private final int[] data;16        private int head = 0, tail = 0, count = 0;17 18        CircularQueue(int capacity) { data = new int[capacity]; }19 20        boolean enqueue(int v) {21            if (isFull()) return false;22            data[tail] = v;23            tail = (tail + 1) % data.length;   // wrap around24            count++;25            return true;26        }27        Integer dequeue() {28            if (isEmpty()) return null;29            int v = data[head];30            head = (head + 1) % data.length;31            count--;32            return v;33        }34        Integer peek() { return isEmpty() ? null : data[head]; }35        boolean isEmpty() { return count == 0; }36        boolean isFull() { return count == data.length; }37        int size() { return count; }38    }39 40    public static void main(String[] args) {41        CircularQueue q = new CircularQueue(3);42        System.out.println("enqueue 1,2,3: " + q.enqueue(1) + "," + q.enqueue(2) + "," + q.enqueue(3));43        System.out.println("enqueue 4 (full): " + q.enqueue(4));44        System.out.println("dequeue: " + q.dequeue() + " peek: " + q.peek());45        System.out.println("enqueue 4 now fits: " + q.enqueue(4));   // wraps to freed slot46        StringBuilder out = new StringBuilder();47        while (!q.isEmpty()) out.append(q.dequeue()).append(' ');48        System.out.println("drain order (FIFO): " + out.toString().trim());49 50        // java.util.Deque can act as both queue and stack51        java.util.Deque<Integer> dq = new java.util.ArrayDeque<>();52        dq.offerFirst(1); dq.offerLast(2); dq.offerFirst(0);53        System.out.println("deque front-to-back: " + dq);54    }55}