`
午刀十
  • 浏览: 34826 次
  • 性别: Icon_minigender_1
  • 来自: 厦门
社区版块
存档分类
最新评论

队列及优先级队列

阅读更多
    队列,与栈相反,先进先出:
/**
 * 
 * @Desc This class use to provide a queue which first in first out
 * @author xujp1 
 * @version Revision: 1.00 Date: Feb 17, 2012
 */
class Queue
{

    private final long[] queArray;
    private int          nItem;
    private int          front;
    private int          rear;
    private final int    maxSize;

    public Queue(int s)
    {
        maxSize = s;
        queArray = new long[maxSize];
        front = 0;//队头,删除数据从队头开始
        rear = -1;//队尾,新数据插入队尾
        nItem = 0;//队列的数量
    }

    public void insert(long item)
    {
        if(rear == maxSize - 1)
            rear = -1;
        queArray[++rear] = item;
        nItem++;
    }

    public long remove()
    {
        long temp = queArray[front++];
        if(front == maxSize)
            front = 0;
        nItem--;
        return temp;
    }

    public void showAll()
    {
        if(nItem == 0)
        {
            System.out.println("THERE HAVE NOT DATA");
        }
        else
            if(nItem == 1)
            {
                System.out.println(queArray[rear]);
            }
            else
            {
                if(front > rear)
                { //队尾在队头后面,则先依次输出队头,再依次输出队尾
                    for(int i = front; i < maxSize; i++)
                    {
                        System.out.println(queArray[i]);
                    }
                    for(int j = 0; j <= rear; j++)
                    {
                        System.out.println(queArray[j]);
                    }
                }
                else
                    if(front < rear)
                    { //队尾在对头后面,则依次输出
                        for(int i = front; i <= rear; i++)
                        {
                            System.out.println(queArray[i]);
                        }
                    }
            }
    }

    public boolean isEmpty()
    {
        return (nItem == 0);
    }

    public boolean isFull()
    {
        return (nItem == maxSize);
    }

    public int size()
    {
        return nItem;
    }

    public long peakFront()
    {
        return queArray[front];
    }
}

    优先级队列:
/**
 * 优先级队列与队列唯一的区别是优先级队列内部数据项有序
 * 
 * @Desc This class use to create PriorityQ class
 * @author xujp1 
 * @version Revision: 1.00 Date: Feb 20, 2012
 */
class PriorityQ
{

    private final long[] priorityQ;
    private final int    maxSize;
    private int          nItem;

    public PriorityQ(int s)
    {
        maxSize = s;
        priorityQ = new long[maxSize];
        nItem = 0;
    }

    //remove和insert方法实现在插入后队列即有序
    public long remove()
    {
        return priorityQ[--nItem];
    }

    public void insert(long s)
    {
        int j;
        if(nItem == 0)
        {
            priorityQ[nItem] = s;
        }
        else
        {
            for(j = nItem - 1; j >= 0; j--)
            {
                if(priorityQ[j] < s)
                {
                    priorityQ[j + 1] = priorityQ[j];
                }
                else
                    break;
            }
            priorityQ[j + 1] = s;

        }
        nItem++;
    }

    //下面的remove2和insert2主要以remove2实现优先级队列
    public long remove2()
    {
        int min = 0;
        long minData;
        for(int i = 1; i < nItem; i++)
        {
            min = priorityQ[min] < priorityQ[i] ? min : i;
        }
        minData = priorityQ[min];
        for(int j = min; j < nItem - 1; j++)
        {
            priorityQ[j] = priorityQ[j + 1];
        }
        nItem--;
        return minData;
    }

    public void insert2(long s)
    {
        priorityQ[nItem++] = s;
    }

    public boolean isEmpty()
    {
        return (nItem == 0);
    }
}


注:以上代码均出自《Java数据结构和算法中文第二版》
分享到:
评论

相关推荐

    队列及优先级队列的std=C99结构方法声明

    队列及优先级队列的std=C99结构方法声明,固定内存大小,构造函数时申请最大内存空间,不支持动态内存申请。优先级队列的比较函数需要另外明细

    队列及优先级队列的std=C99结构方法实现

    队列及优先级队列的std=C99结构方法实现,固定内存大小,构造函数时申请最大内存空间,不支持动态内存申请。优先级队列的比较函数需要另外明细

    多队列动态优先级的调度C实现算法

    本文将深入探讨“多队列动态优先级的调度C实现算法”,这是一种优化资源分配,提高系统效率的方法。 多队列调度算法基于一个核心概念:将待处理的任务分配到多个独立的队列中,每个队列代表一种特定的优先级或任务...

    10.链式队列以及优先级队列应用.ppt

    10.链式队列以及优先级队列应用.ppt

    队列的应用:优先级队列

    使用顺序存储实现优先级队列,展示优先级队列和普通队列的区别之处。

    priority queue优先级队列

    算法中优先级队列问题...用堆排序的算法来做的例子

    优先队列是一种重要的数据结构,它结合了队列和优先级的特性,使得元素能够按照优先级的高低进行出队操作

    优先队列(Priority Queue)是一种抽象数据类型,它类似于常规的队列或栈,但每个元素都有一定的优先级。在优先队列中,元素的出队顺序不是按照它们进入队列的顺序,而是根据它们的优先级来确定。具有高优先级的元素...

    c语言实现优先级队列

    用c语言实现的,简单易懂,希望对大家有用。

    多级反馈队列算法 静态优先级优先算法

    当一个进程被调度运行时,它从最高优先级队列开始,如果在规定的时间内未完成,它会被降级到下一个较低优先级的队列。这种设计使得短进程能够快速得到执行,而长进程不会无限制地占据处理器,保证了系统响应时间和...

    优先级队列

    优先级队列是一种特殊的数据结构,它在许多高级算法和数据处理中扮演着核心角色。在计算机科学中,我们通常使用优先级队列来解决那些需要处理具有不同优先级任务的问题。与普通队列遵循“先进先出”(FIFO)原则不同...

    基于 kotlin Channel 的优先级异步任务队列

    TaskPriority 优先级的标准如下: TaskPriority.LOW 当优先级相同 按照插入次序排队 默认优先级是 TaskPriority.DEFAULT 任务 任务种类可分为 2 种,分别是 执行时间不确定 的任务和 执行时间确定 的任务。执行...

    数据结构课设——小大根交替堆实现的双端优先级队列及应用

    数据结构课设——小大根交替堆实现的双端优先级队列及应用 小大根交替堆是一种特殊的堆结构,它可以同时满足大根堆和小根堆的性质。在本文中,我们将对小大根交替堆实现的双端优先级队列进行详细的分析和设计。 ...

    优先级队列cpp文件PriorityQueue.cpp

    优先级队列cpp文件PriorityQueue.cpp

    一个用堆实现的优先级队列

    优先级队列是一种特殊的数据结构,它按照优先级顺序存储元素,最高优先级的元素总是在队列的前端。在计算机科学中,堆通常被用来实现优先级队列。堆是一种完全二叉树,其中每个父节点的值都大于或等于(最大堆)或...

    优先级队列(堆实现)

    优先级队列是一种特殊的线性数据结构,它在处理元素时遵循特定的优先级规则,通常最高优先级的元素会被最先处理。在Java中,优先级队列是通过`java.util.PriorityQueue`类来实现的,它基于一个二叉堆(Binary Heap)...

    毕业设计MATLAB_优先级队列.zip

    标题中的“毕业设计MATLAB_优先级队列.zip”表明这是一个关于MATLAB编程的毕业设计项目,主题聚焦在实现优先级队列。优先级队列是一种特殊的数据结构,其中每个元素都有一个关联的优先级,队列按照优先级的高低进行...

Global site tag (gtag.js) - Google Analytics