【数据结构与算法 | 基础篇】单向循环链表实现队列

简介: 【数据结构与算法 | 基础篇】单向循环链表实现队列

1. 前言

我们可以使用单向循环链表来实现队列.队列的特点是FIRST IN FIRST OUT.从队头删除节点,从队尾增加节点.

本文实现了从队头添加元素,从队尾删除元素.


2. 实现

自定义的Queue接口.

public interface Queue<E> {
    //向队伍插入值, 插入成功返回true, 否则返回false
    boolean offer(E value);
    //对队头获取值, 但不移除
    E poll();
    //从队头获取值, 并移除队头
    E peek();
    //判断队伍是否为空
    boolean isEmpty();
 
}

实现部分 :

public class LInkedListQueue<E> implements Queue<E>, Iterable<E>{
    private static class Node<E> {
        E value;
        Node<E> next;
        public Node(E value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
    //head指针指向队头
    Node<E> head;
    //tail指针指向队尾
    Node<E> tail;
    //队伍的实际长度
    int size;
    //队伍最大容量
    int capacity = Integer.MAX_VALUE;
    Node<E> dummy;
    public LInkedListQueue() {
        //初始化哨兵节点, 其next指针指向自身
        dummy = new Node(null, null);
        dummy.next = dummy;
        tail = dummy;
        head = dummy;
    }
    public LInkedListQueue(int capacity) {
        this();
        this.capacity = capacity;
    }
    @Override
    public boolean offer(E value) {
        Node p = new Node(value, head);
        tail.next = p;
        size++;
        //移动尾指针, 使尾指针指向尾节点
        tail = p;
        if(size > capacity) {
            return false;
        }
        return true;
    }
 
    @Override
    public E poll() {
        //如果队列为空, 则返回null
        if(isEmpty()) {
            return null;
        }
        E value = head.next.value;
        return value;
    }
 
    @Override
    public E peek() {
        //如果队列为空, 则返回null
        if(isEmpty()) {
            return null;
        }
        E value;
        //如果队列只有一个元素,
        if(head.next == tail) {
            value = head.next.value;
            head.next = null;
            tail = head;
            size--;
        } else {
            value = head.next.value;
            head.next = head.next.next;
        }
        return value;
    }
 
    @Override
    public boolean isEmpty() {
        //只有当head, tail指针都指向哨兵节点时, 此时队伍为空
        return head == tail;
    }
 
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = dummy.next;
            @Override
            public boolean hasNext() {
                return p != head;
            }
 
            @Override
            public E next() {
                E value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}

单元测试 :

public class LInkedListQueueTest {
    @Test
    public void test() {
        LInkedListQueue<Integer> queue = new LInkedListQueue<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        queue.offer(6);
//        for (Integer element : queue) {
//            System.out.println(element);
//        }
        System.out.println(queue.poll());
        //1
        System.out.println(queue.peek());
        //1
        System.out.println(queue.poll());
        //2
    }
 
}
相关文章
|
5天前
|
Python
数据结构===队列
数据结构===队列
|
8天前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
13 0
|
1天前
|
机器学习/深度学习 算法 C语言
【C/数据结构与算法】:10道链表经典OJ
【C/数据结构与算法】:10道链表经典OJ
7 1
|
1天前
|
算法
【C/数据结构和算法】:栈和队列
【C/数据结构和算法】:栈和队列
6 1
|
7天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
8 1
|
8天前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
14 2
|
11天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
|
1天前
|
存储 算法 前端开发
【C/数据结构与算法】:链表的实现(单向链表+双向链表)
【C/数据结构与算法】:链表的实现(单向链表+双向链表)
5 0
|
4天前
|
缓存 调度
栈和队列的区别
栈和队列的区别
7 0
|
5天前
|
存储 算法 Java
Java数据结构与算法:线性数据结构之链表
Java数据结构与算法:线性数据结构之链表