[数据结构与算法]队列-线性表-数据结构和算法(Java)

1 队列简介

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。 [1]

2 队列实现

这么我使用基于链表的方式实现最基础的队列，如果想要看基于数组的实现方式，可自行查阅相关文档或者留言。

2.1 API

• 队列接口：public interface Queue extends Iterable

• 基于链表的队列实现：public class LinkQueue<E> implements Queue<E>

  • 成员变量

  • 访问控制和类型	名称	描述
    private Node<E>	first	队头
    private Node<E>	last	队尾
    private int	size	队列元素个数

  • 成员方法API其他方法和Queue接口相同

2.2 代码实现

public class LinkQueue<E> implements Queue<E>, Serializable {

    /**
     * 队头
     */
    private Node<E> first;

    /**
     * 队尾
     */
    private Node<E> last;

    /**
     * 队列元素个数
     */
    private int size;

    public LinkQueue() {
    }

    /**
     * 元素入队(队尾）
     * @param e 元素
     */
    @Override
    public void offer(E e) {
        Node<E> l = last;
        last = new Node<>(e, null);
        if (first == null) {
            first = last;
        } else {
            l.next = last;
        }
        size++;
    }

    /**
     * 查看队头元素
     * @return  队头元素
     */
    @Override
    public E peek() {
        if (first == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        return first.item;
    }

    /**
     * 队头元素出队
     * @return  队头元素
     */
    @Override
    public E poll() {
        if (first == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        Node<E> f = first;
        E item = f.item;
        first = f.next;
        f.item = null;
        if (first == null) {
            last = null;
        } else {
            f.next = null;
        }
        size--;
        return item;
    }

    /**
     * 判断队列是否为空
     * @return {@code true} 队列为空时，否则
     *         {@code false}
     */
    @Override
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * 返回队列元素个数
     * @return  队列元素个数
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 节点类
     * @param <E>   泛型
     */
    private static class Node<E> {
        E item;
        Node<E> next;

        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }

    @Override
    public Iterator<E> iterator()  {
        return new LinkedIterator(first);
    }

    @Override
    public String toString() {
        Iterator<E> it = iterator();
        if (! it.hasNext()) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e);
            if (! it.hasNext()) {
                return sb.append(']').toString();
            }
            sb.append(',').append(' ');
        }
    }

    /**
     * 迭代器
     */
    private class LinkedIterator implements Iterator<E> {
        private Node<E> current;

        public LinkedIterator(Node<E> first) {
            current = first;
        }

        @Override
        public boolean hasNext()  { return current != null;                     }

        /**
         * 基于队列只在队头删除元素的特点，这里不实现
         */
        @Override
        public void remove()      { throw new UnsupportedOperationException();  }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E item = current.item;
            current = current.next;
            return item;
        }
    }
}

3 后记

? 如果小伙伴什么问题或者指教，欢迎交流。

?QQ:806797785

??源代码仓库地址：https://gitee.com/gaogzhen/algorithm

参考：

[1]百度百科.队列[EB/OL].2018-08-15/2022-11-02.

[2][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法：第4版[M].北京：人民邮电出版社，2012.10