队列

[yifanzheng]

队列

队列的结构特点：先进先出。入队时将数据放入队尾，出队时从队列头部取数据。

练习

• 用数组实现队列
• 用链表实现队列
• 实现循环队列

[yifanzheng]

用数组实现队列

public class ArrayQueue {

    private Integer[] datas;
    private int capacity;
    /** 队头下标 */
    private int head;
    /** 队尾下标 */
    private int tail;

    public ArrayQueue(int capacity) {
        this.datas = new Integer[capacity];
        this.capacity = capacity;
        this.head = 0;
        this.tail = 0;
    }

    public boolean enqueue(Integer data) {
        if (tail == capacity) {
            // 队列满了
            if (head == 0) {
                return false;
            }
            // 搬移数据
            for (int i = head; i < tail; i ++) {
                datas[i -head] = datas[i];
            }
            // 重置 head 和 tail 的位置
            tail = tail -head;
            head = 0;
        }
        datas[tail++] = data;
        return true;
    }

    public Integer dequeue() {
        if (head == tail) {
            // 队列已经空了
            return null;
        }
        return datas[head++];
    }
}

[yifanzheng]

用链表实现队列

public class LinkedQueue {

    private Node head;
    private Node tail;

    public void enqueue(Integer data) {
        if (tail == null) {
            Node newNode = new Node(data, null);
            head = newNode;
            tail = newNode;
        } else {
            tail.next = new Node(data, null);
            tail = tail.next;
        }
    }

    public Integer dequeue() {
        if (head == null) {
          return null;
        }
        Integer data = head.data;
        head = head.next;
       // head 如果为空了，说明队列已经空了，需要将 tail 置空
        if (head == null) {
            tail = null;
        }
        return data;
    }

    private class Node {
        private Integer data;
        private Node next;

        public Node(Integer data, Node next) {
            this.data = data;
            this.next = next;
        }

        public Integer getData() {
            return data;
        }
    }
}

[yifanzheng]

实现循环队列

public class CircularQueue {

    private Integer[] datas;
    private int capacity;
    /** 队头下标 */
    private int head;
    /** 队尾下标 */
    private int tail;

    public CircularQueue(int capacity) {
        this.datas = new Integer[capacity];
        this.capacity = capacity;
        this.head = 0;
        this.tail = 0;
    }

    public boolean enqueue(Integer data) {
        // 队列满了
        if ((tail + 1) % capacity == head) {
           return false;
        }
        datas[tail] = data;
        tail = (tail + 1) % capacity;
        return true;
    }

    public Integer dequeue() {
        // 队列为空
        if (head == tail) {
            return null;
        }
        Integer data = datas[head];
        head = (head + 1) % capacity;
        return data;
    }
}