欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构-3-队列

程序员文章站 2022-03-14 15:05:39
...

三、队列

1、概念

队列是一种遵循 FIFO(first-in-first-out)的集合数据结构,即最先放到队列中的元素,也是最先被获取到的

它底层可以用数组来实现,也可以用链表来实现。它有2个指针,分别指向头节点和尾节点,添加元素时向后移动尾节点,移除元素时向后移动头节点

2、常用方法

  1. put 添加元素到队列中
  2. take 移出队列的首个元素(向后移动头节点)
  3. peek 取出队列的首个元素(不移动头节点)

3、示例

1)数组队列

class ArrayQueue<T> {
    private final int length;
    private Object[] array;
    private int head; // 指向本次要移出的元素的前一个位置
    private int tail; // 指向本次要添加的元素的前一个位置

    public ArrayQueue(int length) {
        this.length = length;
        this.array = new Object[this.length];
        this.head = -1;
        this.tail = -1;
    }

    public void put(T element) {
        if (isFull()) {
            return;
        }

        this.tail++;
        array[tail] = element;
    }

    public T take() {
        if (isEmpty()) {
            return null;
        }

        this.head++;
        @SuppressWarnings("unchecked")
        T element = (T)array[head];
        if (head == tail) {
            head = -1;
            tail = -1;
        }
        return element;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            return null;
        }
        return (T)array[head + 1];
    }

    public int size() {
        return tail - head;
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        }

        StringBuilder sBuilder = new StringBuilder("[");
        for (int i = head + 1, size = i + size(); i < size; i++) {
            sBuilder.append(array[i]);
            if (i != size - 1) {
                sBuilder.append(", ");
            } else {
                sBuilder.append("]");
            }
        }
        return sBuilder.toString();
    }

    public boolean isFull() {
        return tail == length - 1;
    }

    public boolean isEmpty() {
        return -1 == head && head == tail;
    }

}

2)链表队列

class LinkedQueue<T> {
    private final int length;
    private Node<T> head; // 头节点指向本次可以取出的节点
    private Node<T> tail; // 尾节点指向最后一个节点
    private int size;

    public LinkedQueue(int length) {
        this.length = length;
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void put(T element) {
        if (isFull()) {
            return;
        }

        Node<T> add = new Node<T>(element);
        if (null == head) {
            this.head = add;
        }
        if (null != tail) {
            tail.next = add;
        }
        this.tail = add;
        this.size++;
    }

    public T take() {
        if (isEmpty()) {
            return null;
        }

        T element = head.element;
        if (head == tail) { // 最后一个元素,将尾节点也置为空
            this.tail = null;
        }
        this.head = head.next;
        this.size--;
        return element;
    }

    public T peek() {
        if (isEmpty()) {
            return null;
        }
        return head.element;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        }

        StringBuilder sBuilder = new StringBuilder("[");
        Node<T> node = this.head;
        while (true) {
            sBuilder.append(node.element);
            if (null == node.next) {
                break;
            }
            sBuilder.append(", ");
            node = node.next;
        }
        sBuilder.append("]");
        return sBuilder.toString();
    }

    public boolean isFull() {
        return size == length;
    }

    public boolean isEmpty() {
        return 0 == size;
    }

    private static class Node<T> {
        private final T element;
        private Node<T> next;

        private Node(T element) {
            this.element = element;
        }

        @Override
        public String toString() {
            return (null != element) ? element.toString() : "null";
        }
    }

}

3)循环队列

class CircleQueue<T> {
    private final int length;
    private Object[] array;
    private int head; // 指向队头
    private int tail; // 指向队尾

    public CircleQueue(int length) {
        this.length = length + 1; // 多出一个位置,用于存放上一次取出的元素。更新指针时访问不到它
        this.array = new Object[this.length];
        this.head = 0;
        this.tail = 0;
    }

    public void put(T element) {
        if (isFull()) {
            return;
        }

        array[tail] = element;
        tail = (tail + 1) % length;
    }

    public T take() {
        if (isEmpty()) {
            return null;
        }

        @SuppressWarnings("unchecked")
        T element = (T)array[head];
        head = (head + 1) % length;
        return element;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            return null;
        }

        return (T)array[head];
    }

    public int size() {
        return (tail + length - head) % length;
    }

    public boolean isFull() {
        return (tail + 1) % length == head;
    }

    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        }

        StringBuilder sBuilder = new StringBuilder("[");
        for (int i = head, size = i + size(); i < size; i++) {
            sBuilder.append(array[i % length]);
            if (i != size - 1) {
                sBuilder.append(',').append(' ');
            }
        }
        sBuilder.append(']');
        return sBuilder.toString();
    }

}