4.队列-java

知识前提

利用数组实现

普通队列
优化队列
循环队列

利于优化

利用链表实现
普通链表队列

不易优化

队列二要素:入队,出队

头结点:

  • 删除指定位置元素
  • 判断队列是否为空

尾结点:

  • 指定新元素的插入位置
  • 通过尾结点判断队列是否满了,如果满了,就禁止插入
  • 判断队列是否为空

顺序队列

基础队列

public class Queue {
    int n = 0;
    String[] items;
    int head;
    int tail;

    public Queue(int capacity) {
        n = capacity;
        items = new String[capacity];
    }

    public boolean enqueue(String item) {
        //如果队列满
        if (tail == n) return false;
        items[tail++] = item;
        return true;
    }

    public String dequeue() {
        if (head == tail) return null;
        return items[head++];
        
    }

    public static void main(String[] args) {
        Queue a = new Queue(10);
        a.enqueue("10");
        a.enqueue("20");
        String dequeItem = a.dequeue();
        System.out.println(dequeItem.equals("10"));
        a.enqueue("30");
        System.out.println(a.items[a.head].equals("20"));
        System.out.println(a.items[a.tail - 1].equals("30"));
        
    }
}

加入数据迁移的队列

上一种队列会越用越小,就需要对数据进行迁移,实现队列的自动整理。

public class Queue {
    private String[] items;
    private int n = 0;
    private int head = 0;
    private int tail = 0;

    public tmp(int capacity) {
        n = capacity;
        items = new String[n];
    }

    public boolean enqueue(String item) {
        if (tail == n) {
            if (head == 0) return false;
            for (int i = head; i < tail; ++i) {
                items[i-head] = items[i];
            }
            tail -= head;
            head = 0;
        }
        items[tail] = item;
        ++tail;
        return true;
    }

    public String dequeue() {
        if (head == tail)
            return null;
        return items[head++];
    }

    public static void main(String[] args) {
        Queue a = new Queue(3);
        a.enqueue("10");
        a.enqueue("20");
        a.enqueue("30");
        boolean result = a.enqueue("40");
        System.out.println(!result);
        String dequeItem = a.dequeue();
        System.out.println(dequeItem.equals("10"));
        a.enqueue("30");
        System.out.println(a.items[0].equals("20"));
        System.out.println(a.items[2].equals("30"));

    }
}

链式队列

public class Queue {
    Node head = null;
    Node tail = null;
    public void enqueue(String item) {
        if (tail == null) {
            Node newNode = new Node(item);
            head = newNode;
            tail = newNode;
        }else {
            tail.next = new Node(item);
            tail = tail.next;
        }
    }

    public String dequeue() {
        if (head == null) return null;
        String value = head.data;
        head = head.next;
        return value;
    }

    public static void main(String[] args) {
        Queue a = new Queue();
        a.enqueue("10");
        a.enqueue("20");
        a.enqueue("30");
        String dequeItem = a.dequeue();
        System.out.println(dequeItem == "10");
        System.out.println(a.head.data == "20");
        System.out.println(a.head.next.data == "30");

    }

    public static class Node {
        String data;
        Node next = null;
        public Node(String data) {
            this.data = data;
        }

    }

}

循环队列

public class Queue {
    int n = 0;
    String[] items;
    int head = 0;
    int tail = 0;

    public Queue(int capacity) {
        n = capacity;
        items = new String[capacity];

    }

    public boolean enqueue(String item) {
        if ((tail + 1) % n == head)
            return false;
        items[tail] = item;
        tail = (tail + 1) % n;
        return true;

    }

    public String dequeue() {
        if (head == tail)
            return null;
        String value = items[head];
        head = (head + 1) % n;
        return value;
    }

    public static void main(String[] args) {
        Queue a = new Queue(3);
        a.enqueue("10");
        a.enqueue("20");
        boolean result = a.enqueue("30");
        // 循环队列需要空出一格
        System.out.println(!result);
        String dequeItem = a.dequeue();
        a.enqueue("30");
        System.out.println(a.items[2] == "30");
        result = a.enqueue("10");
        System.out.println(result == false);

    }

}

阻塞队列

入队和出队可以等待

并发队列

支持多线程的阻塞队列

老师您好,今天刚刚看了列表的视频,发现链式队列中出队的一个小问题,嘻嘻:

链式队列的出队 , 当队列中只有一个元素的时候 , head指向该元素的next , 也就是None
如果这里不修改tail , 则出现的问题就是 : head指向了 None , tail 还是指向出队了的该元素 .
这个是不是需要修改出队代码 , 变更 head 之后 , 再去判断 self.head 是否为 None , 为 None 则变更 self.tail 也为 None.

代码:

    def de_queue(self):
        if not self.head:
            return None
        value = self.head
        self.head = self.head.next
        if not self.head:  # 如果没有这个if判断,当队列元素唯一时出队, head指向None,tail指向该元素,这个是不是不对.
            self.tail = None
        return value