【算法之旅】基础数据结构之队列

简介: 【算法之旅】基础数据结构之队列

一、概述


计算机科学中,queue 是以顺序的方式维护的一组数据集合,在一端添加数据,从另一端移除数据。习惯来说,添加的一端称为尾,移除的一端称为头,就如同生活中的排队买商品


In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence


先定义一个简化的队列接口


public interface Queue<E> {
    /**
     * 向队列尾插入值
     * @param value 待插入值
     * @return 插入成功返回 true, 插入失败返回 false
     */
    boolean offer(E value);
    /**
     * 从对列头获取值, 并移除
     * @return 如果队列非空返回对头值, 否则返回 null
     */
    E poll();
    /**
     * 从对列头获取值, 不移除
     * @return 如果队列非空返回对头值, 否则返回 null
     */
    E peek();
    /**
     * 检查队列是否为空
     * @return 空返回 true, 否则返回 false
     */
    boolean isEmpty();
    /**
     * 检查队列是否已满
     * @return 满返回 true, 否则返回 false
     */
    boolean isFull();
}


二、链表实现


下面以单向环形带哨兵链表方式来实现队列


e71be22f93e905cd74972989e42b57b6_bcf5f3d4a413475f9c3b0a5901426556.png


58db816bd28601803651b1ca1fd97a70_ccddffa7b26f49489c8ab1307e5ad3fe.png


c6c31101890260bb7f470fbaae8e4f0b_7ae9bea0e36d48b68f42d18ab669e89e.png


代码


public class LinkedListQueue<E>
        implements Queue<E>, Iterable<E> {
    private static class Node<E> {
        E value;
        Node<E> next;
        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }
    private Node<E> head = new Node<>(null, null);
    private Node<E> tail = head;
    private int size = 0;
    private int capacity = Integer.MAX_VALUE;
    {
        tail.next = head;
    }
    public LinkedListQueue() {
    }
    public LinkedListQueue(int capacity) {
        this.capacity = capacity;
    }
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        Node<E> added = new Node<>(value, head);
        tail.next = added;
        tail = added;
        size++;
        return true;
    }
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = head.next;
        head.next = first.next;
        if (first == tail) {
            tail = head;
        }
        size--;
        return first.value;
    }
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return head.next.value;
    }
    @Override
    public boolean isEmpty() {
        return head == tail;
    }
    @Override
    public boolean isFull() {
        return size == capacity;
    }
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = head.next;
            @Override
            public boolean hasNext() {
                return p != head;
            }
            @Override
            public E next() {
                E value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}



三、环形数组实现


好处


对比普通数组,起点和终点更为自由,不用考虑数据移动

“环”意味着不会存在【越界】问题

数组性能更佳

环形数组比较适合实现有界队列、RingBuffer 等


ec2fb8fb3536066aa5d1a41a94521059_35ff018e305a43c9adcb1aeaf4dfa0c6.png


下标计算


例如,数组长度是 5,当前位置是 3 ,向前走 2 步,此时下标为 ( 3 + 2 ) % 5 = 0 (3 + 2)\%5 = 0(3+2)%5=0


af5ede532aeb4b5802677ad43f2104c3_222a62d18b1f4e798d8985022926339d.png


( c u r + s t e p ) % l e n g t h (cur + step) \% length

(cur+step)%length


cur 当前指针位置

step 前进步数

length 数组长度

注意:


如果 step = 1,也就是一次走一步,可以在 >= length 时重置为 0 即可

判断空


eaf16ecaf4b361e15110455e245a7bdc_ea556cf1dc864d06ba3e9507e6a9891f.png


判断满


d8bdf08e25754936ce27c8869d717ee4_74cd5d8174ab4435bdcbb483ddc456ef.png


满之后的策略可以根据业务需求决定


例如我们要实现的环形队列,满之后就拒绝入队

代码


public class ArrayQueue<E> implements Queue<E>, Iterable<E>{
    private int head = 0;
    private int tail = 0;
    private final E[] array;
    private final int length;
    @SuppressWarnings("all")
    public ArrayQueue(int capacity) {
        length = capacity + 1;
        array = (E[]) new Object[length];
    }
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[tail] = value;
        tail = (tail + 1) % length;
        return true;
    }
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E value = array[head];
        head = (head + 1) % length;
        return value;
    }
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return array[head];
    }
    @Override
    public boolean isEmpty() {
        return tail == head;
    }
    @Override
    public boolean isFull() {
        return (tail + 1) % length == head;
    }
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }
            @Override
            public E next() {
                E value = array[p];
                p = (p + 1) % array.length;
                return value;
            }
        };
    }
}



判断空、满方法2


引入 size


public class ArrayQueue2<E> implements Queue<E>, Iterable<E> {
    private int head = 0;
    private int tail = 0;
    private final E[] array;
    private final int capacity;
    private int size = 0;
    @SuppressWarnings("all")
    public ArrayQueue2(int capacity) {
        this.capacity = capacity;
        array = (E[]) new Object[capacity];
    }
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[tail] = value;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E value = array[head];
        head = (head + 1) % capacity;
        size--;
        return value;
    }
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return array[head];
    }
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
    @Override
    public boolean isFull() {
        return size == capacity;
    }
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }
            @Override
            public E next() {
                E value = array[p];
                p = (p + 1) % capacity;
                return value;
            }
        };
    }
}


判断空、满方法3


head 和 tail 不断递增,用到索引时,再用它们进行计算,两个问题


如何保证 head 和 tail 自增超过正整数最大值的正确性


如何让取模运算性能更高


答案:让 capacity 为 2 的幂


public class ArrayQueue3<E> implements Queue<E>, Iterable<E> {
    private int head = 0;
    private int tail = 0;
    private final E[] array;
    private final int capacity;
    @SuppressWarnings("all")
    public ArrayQueue3(int capacity) {
        if ((capacity & capacity - 1) != 0) {
            throw new IllegalArgumentException("capacity 必须为 2 的幂");
        }
        this.capacity = capacity;
        array = (E[]) new Object[this.capacity];
    }
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[tail & capacity - 1] = value;
        tail++;
        return true;
    }
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E value = array[head & capacity - 1];
        head++;
        return value;
    }
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return array[head & capacity - 1];
    }
    @Override
    public boolean isEmpty() {
        return tail - head == 0;
    }
    @Override
    public boolean isFull() {
        return tail - head == capacity;
    }
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }
            @Override
            public E next() {
                E value = array[p & capacity - 1];
                p++;
                return value;
            }
        };
    }
}


@Override
public Iterator<E> iterator() {
    return new Iterator<E>() {
        int p = head;
        @Override
        public boolean hasNext() {
            return p != tail;
        }
        @Override
        public E next() {
            E value = array[p & capacity - 1];
            p++;
            return value;
        }
    };
}
}
目录
打赏
0
0
0
0
66
分享
相关文章
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
113 1
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
17 1
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
20 0
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
4月前
|
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
105 10
 算法系列之数据结构-二叉树
|
4月前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
126 3
 算法系列之数据结构-Huffman树
|
4月前
|
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
115 22
|
5月前
|
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
84 11
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
147 30
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
211 25

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问