头歌 Java数据结构-队列的应用的参考答案

1. 数组模拟队列

public class ArrayQueue {
    private int[] queue;
    private int front;
    private int rear;
    private int maxSize;

    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        queue = new int[maxSize];
        front = -1;
        rear = -1;
    }

    public boolean isFull() {
        return rear == maxSize - 1;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public void add(int data) {
        if (isFull()) {
            System.out.println("队列已满");
            return;
        }
        rear++;
        queue[rear] = data;
    }

    public int remove() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        front++;
        return queue[front];
    }

    public void show() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }
        for (int i = front + 1; i <= rear; i++) {
            System.out.print(queue[i] + " ");
        }
        System.out.println();
    }
}

2. 链表模拟队列

public class LinkedListQueue {
    private Node front;
    private Node rear;

    public void add(int data) {
        Node node = new Node(data);
        if (rear == null) {
            front = node;
            rear = node;
        } else {
            rear.setNext(node);
            rear = node;
        }
    }

    public int remove() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int data = front.getData();
        front = front.getNext();
        if (front == null) {
            rear = null;
        }
        return data;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public void show() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }
        Node node = front;
        while (node != null) {
            System.out.print(node.getData() + " ");
            node = node.getNext();
        }
        System.out.println();
    }

    private static class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }
}

3. 循环队列

public class CircularQueue {
    private int[] queue;
    private int front;
    private int rear;
    private int maxSize;

    public CircularQueue(int maxSize) {
        this.maxSize = maxSize;
        queue = new int[maxSize];
        front = 0;
        rear = 0;
    }

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

    public boolean isEmpty() {
        return front == rear;
    }

    public void add(int data) {
        if (isFull()) {
            System.out.println("队列已满");
            return;
        }
        queue[rear] = data;
        rear = (rear + 1) % maxSize;
    }

    public int remove() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int data = queue[front];
        front = (front + 1) % maxSize;
        return data;
    }

    public void show() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }
        for (int i = front; i != rear; i = (i + 1) % maxSize) {
            System.out.print(queue[i] + " ");
        }
        System.out.println();
    }
}