真正的数据结构和算法【4】

队列 Queue

队列的特点就是先进先出

队列的实现方式数组或者链表

应用范围比较广:

  • 打印机
  • 存储内容
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package queue;

/**
 * @author Zen
 * @version 1.0: Queue.java, v 0.1 2019/05/12 10:15 Zen Exp $
 */
public class Queue {
    private int maxsize;
    private int arr[];
    private int front;
    private int rear;
    private int size;

    public Queue(int m){
        maxsize = m;
        arr = new int[maxsize];
        front = 0;
        rear = -1;
        size = 0;
    }

    public void insert(int value){
        arr[++rear] = value;
        size ++;
        display();
    }
    public int delete(){
        int a = arr[front++];
        size --;
        display();
        return  a;
    }

    public void display(){
        for(int i = front ; i <=rear;i++){
            System.out.print(arr[i]+ "  ");
        }
        System.out.println("当前在队列中数据量为:"+size);
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package queue;

/**
 * @author Zen
 * @version 1.0: QueueApp.java, v 0.1 2019/05/12 10:23 Zen Exp $
 */
public class QueueApp {
    public static void main(String[] args) {
        Queue queue = new Queue(100);
        queue.insert(10);
        queue.insert(20);
        queue.insert(30);
        queue.insert(40);
        queue.insert(50);
        queue.insert(60);
        queue.insert(70);
        queue.insert(80);
        queue.insert(90);
        queue.insert(100);
        System.out.println("进队列完成");
        queue.delete();
        queue.delete();
        queue.delete();
        queue.delete();
        queue.delete();
        queue.delete();
        queue.delete();
    }
}

优先级队列

优先级队列介绍

双端队列(两端都可以进出)

优先级队列:
实际上是对数据插入时进行排序,再进行队列的处理。

这段代码刚开始写的时候想不太通,因为,我认为队列就是要用上前后节点指针的。
但是,实际上,封装这样的一个队列,只需要功能对外暴露的时候能实现先进先出就行了。
然后内部的元素,在使用数组时,用的最多的也就是下标和个数了,其实有这两个大部分问题都能解决。

/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package queue;

/**
 * @author Zen
 * @version 1.0: PriorityQueue.java, v 0.1 2019/05/12 11:31 Zen Exp $
 */
public class PriorityQueue {
    private int [] arr;
    private int maxsize;
    private int size;

    public PriorityQueue(int s){
        maxsize = s;
        arr = new int[maxsize];
        size = 0;
    }

    public void insert(int value){
        int j;
        if(size == 0){
            arr[size++] = value;
            display();
        }else{
            for(j = size-1 ; j >= 0;j--){
                if(value > arr[j]){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+1] = value;
            size++;
            display();
        }
    }
    public int remove(){
        display();
        return arr[--size];
    }
    public void display(){
        for(int i = 0;i < size ;i++){
            System.out.print(arr[i]+ "  ");
        }
        System.out.println("当前队列中元素为:"+size+"个");
    }

}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package queue;

/**
 * @author Zen
 * @version 1.0: PriorityQueueApp.java, v 0.1 2019/05/12 11:55 Zen Exp $
 */
public class PriorityQueueApp {
    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue(100);
        queue.insert(10);
        queue.insert(200);
        queue.insert(30);
        queue.insert(40);
        queue.insert(50);
        queue.insert(60);
        queue.insert(70);
        queue.insert(80);
        queue.insert(90);
        queue.insert(100);
        System.out.println("进队列完成");
        queue.remove();
        queue.remove();
        queue.remove();
        queue.remove();
        queue.remove();
        queue.remove();
        queue.remove();
    }
}

本文链接:

https://heyzen.club/index.php/Coder/295.html
1 + 1 =
快来做第一个评论的人吧~