队列和优先队列

忘是亡心i 2022-08-08 14:43 278阅读 0赞

# 队列 #

队列是一种特殊的[线性表][Link 1]，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素成为出队。因为队列只允许在一段插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）[线性表][Link 1]。

顺序队列，循环队列。

以数组为例进行队列的实现

队列数据结构：

typedef struct queue
    {
            int queuesize;   //数组的大小
            int head, tail;  //队列的头和尾下标
            int *q;          //数组头指针
    }Queue;

队列初始化

void InitQueue(Queue *q)
    {
            q->queuesize = 8;
            q->q = (int *)malloc(sizeof(int) * q->queuesize); //分配内存
            q->tail    = 0;
            q->head = 0;
    }

进队列

void EnQueue(Queue *q, int key)
    {
            int tail = (q->tail+1) % q->queuesize; 
            //取余保证，当quil=queuesize-1时，再转回0
            if (tail == q->head)                   //此时队列没有空间
            {
                printf("the queue has been filled full!");
            }
            else
            {
                q->q[q->tail] = key;
                q->tail = tail;
            }
    }

出队列

int DeQueue(Queue *q)
    {
            int tmp;
            if(q->tail == q->head)     //判断队列不为空
            {
                printf("the queue is NULL\n");
            }
            else
            {
                tmp = q->q[q->head];
                q->head = (q->head+1) % q->queuesize;
            }
            return tmp;
    }

判断队列是否为空

int IsQueueEmpty(Queue *q)
    {
            if(q->head == q->tail)
            {
                return 1;
            }
            else
            {
                return 0;
            }
    }

以上这些只是自己实现一下，标准库里面都有标准的库函数

头文件为<queue>

队列提供了下面的操作

q.empty()               //如果队列为空返回true，否则返回false

q.size()                 //返回队列中元素的个数

q.pop()                 //删除队列首元素但不返回其值

q.front()                // 返回队首元素的值，但不删除该元素

q.push()                // 在队尾压入新元素

q.back()                // 返回队列尾元素的值，但不删除该元素

# 优先队列 #

优先队列：顾名思义，首先它是一个队列，但是它强调了“优先”二字，所以，已经不能算是一般意义上的队列了，它的“优先”意指取队首元素时，有一定的选择性，即根据元素的属性选择某一项值最优的出队~

百度百科上这样描述的：优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。