时间戳

首页 > 技术文章 > java实现队列

java实现队列

y3596597 2017-05-10 19:28 原文

   队列（queue）

        队列 是一种先进先出的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

      优先队列(priority queue),普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除，具有最高级先出 (largest-in，first-out)的行为特征。

用数组实现顺序队列的实现：

package test;

public class Queue {
    // 数组
    private long[] arr;
    
    // 最大空间
    private int maxSize;
    
    // 有效元素大小
    private int elems;
    
    // 队头
    private int font;
    
    // 队尾
    private int end;
    public Queue(){}
    public Queue(int maxSize) {
        this.maxSize = maxSize;
        arr = new long[maxSize];
        elems = 0;
        font = 0;
        end = -1;
    }
    
    // 插入数据
    public void insert(long value) {
        arr[++end] = value;
        elems++;
    }
    
    // 移除数据
    public long remove() {
        elems--;
        return arr[font++]; 
    }
    
    // 是否为空
    public boolean isEmpty() {
        return (elems == 0);
    }
    
    // 是否满了
    public boolean isFull() {
        return (end == maxSize - 1);
    }
    
    // 返回有效元素大小
    public int size() {
        return elems;
    }
}

测试：

    @Test
    public void fun1() {
        Queue queue = new Queue(5);
        queue.insert(4);
        queue.insert(9);
        queue.insert(7);
        System.out.println("删除数据:"+queue.remove()+"队列大小:"+queue.size());
        System.out.println("是否已满:"+queue.isEmpty());
    }

链式队列：

package test;

import java.io.Serializable;

public class LinkQueue<T> {

    // 定义一个内部类Node，Node实例代表链队列的节点。
    private class Node {

        private T data;// 保存节点的数据
        private Node next;// 指向下个节点的引用

        // 无参数的构造器
        public Node() {
        }

        // 初始化全部属性的构造器
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node front;// 保存该链队列的头节点

    private Node rear;// 保存该链队列的尾节点

    private int size;// 保存该链队列中已包含的节点数

    public LinkQueue() {// 空链队列，front和rear都是null
        front = null;
        rear = null;
    }

    public LinkQueue(T element) {// 只有一个节点，front、rear都指向该节点
        front = new Node(element, null);
        rear = front;
        size++;
    }

    public int size() {
        return size;
    }

    public void insert(T element) {// 如果该链队列还是空链队列
        if (front == null) {
            front = new Node(element, null);
            rear = front;// 只有一个节点，front、rear都指向该节点
        } else {
            Node newNode = new Node(element, null);// 创建新节点
            rear.next = newNode;// 让尾节点的next指向新增的节点
            rear = newNode;// 以新节点作为新的尾节点
        }
        size++;
    }

    public T remove() {// 出对
        Node oldFront = front;
        front = front.next;
        oldFront.next = null;
        size--;
        return oldFront.data;
    }

    public T peek() {// 返回队列顶元素，但不删除队列顶元素
        return rear.data;
    }

    public boolean isEmpty() {// 判断顺序队列是否为空队列
        return size == 0;
    }

    public void clear() {// 清空顺序队列
        // 将front、rear两个节点赋为null
        front = null;
        rear = null;
        size = 0;
    }

    public String toString() { // 链队列为空链队列时
        if (isEmpty()) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder("[");
            for (Node current = front; current != null; current = current.next) {
                sb.append(current.data.toString() + ", ");
            }
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();
        }
    }
}

测试:

    @Test
    public void fun2() {
        LinkQueue lq = new LinkQueue();
        lq.insert("sds");
        lq.insert("sdfsa");
        Integer in = 3;
        lq.insert(in);
        lq.insert("我");
        System.out.println("插入的数据:"+lq.toString());
        System.out.println("删除的数为:"+lq.remove());
    }

 

 将值大小作为优先级，实现优先队列：

package test;

public class PriorityQueue {
    // 数组
    private long[] arr;
    
    // 最大空间
    private int maxSize;
    
    // 有效元素大小
    private int elems;
    
    
    public PriorityQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new long[maxSize];
        elems = 0;
    }
    
    // 插入数据
    public void insert(long value) {
        int i;
        for (i = 0;  i < elems; i++) {
            if(value < arr[i]) {
                break;
            }
        }
        
        for(int j = elems; j > i;j--){
            arr[j] = arr[j - 1];
        }
        arr[i] = value;
        elems++;
    }
    
    // 移除数据
    public long remove() {
        long value = arr[elems - 1];
        elems--;
        return value;
    }
    
    // 是否为空
    public boolean isEmpty() {
        return (elems == 0);
    }
    
    // 是否满了
    public boolean isFull() {
        return (elems == maxSize);
    }
    
    // 返回有效元素大小
    public int size() {
        return elems;
    }
}

测试：

    @Test
    public void fun() {
        PriorityQueue pq = new PriorityQueue(10);
        pq.insert(30);
        pq.insert(45);
        pq.insert(15);
        pq.insert(2);
        pq.insert(1);

        while (!pq.isEmpty()) {
            long value = pq.remove();
            System.out.print(value + " ");
        }
    }

 

推荐阅读