言十年的博客

上善若水,水善利萬物而不爭

物盡其用!人盡其才!兩全其美!


队列【总结】

对链表进行了一些限制,把某些功能砍掉就变成了栈。先不讲链式实现的队列,讲数组实现的队列。

线性结构的两种常见应用之二 队列。

定义:

一种可以实现“先进先出”的存储结构。就像是火车站排队买票。

分类:

  • 链式队列(用链表来实现)

  • 静态队列(用数组实现)

    • 静态队列通常都必须是循环队列
    • 循环队列的讲解 * 1.静态队列为什么必须是循环队列 * 如果用普通的数组实现,删除元素之后,之前的空间就不能使用了。只能增不能减,空间就浪费了。还容易溢出 * 2.循环队列需要几个参数来确定 * front、rear * 3.循环队列各个参数的含义 * 2个参数来确定。2个参数不同场合有不同的含义。建议初学者先记住,然后慢慢体会。 * 1) 队列初始化 * front 和rear的值都是零 * 2) 队列非空 * front 代表的是队列的第一个元素 * rear 代表的是队列的最后一个有效的元素的下一个元素 * 3) 队列空 * font 和rear 的值相等,但不一定是零 * 4.循环队列入队伪算法讲解 * 两步完成; * 1.将值存入r所代表的位置。错误的写法 r = r + 1;正确的写法是:r = (r + 1)% 数组的长度 * 5.循环队列出队伪算法讲解 * f = (f + 1) % 数组的长度 * 6,如何判断循环队列是否为空 * 如果front 与 rear的值相等,则该队列一定为空 * 7.如何判断循环队列是否已满 * 预备知识: * front的值可能比rear大。也可能小,也可能相等。 * 两种方式 * 1. 多增加一个标识参数 * 2. 少用一个元素(通常使用这种方式)
如果r和f的值紧挨着,则队列已满
用c语言伪算法
if((r+1)%数组长度 == f)
	已满
else
	不满

将值存入r所代表的位置

错误的写法 r = r + 1

正确的写法

代码实现

#include <stdio.h>
#include <stdbool.h>
typedef struct Queue
{
    int * pBase;
    int front;
    int rear;
}QUEUE;
void init(QUEUE *);
bool en_queue(QUEUE *, int);
bool full_queue(QUEUE *);
void traverse_queue(QUEUE *);
bool empty_queue(QUEUE *);
bool out_queue(QUEUE *,int *);
int main(int argc, const char * argv[]) {
    QUEUE Q;
    int val;
    init(&Q);
    en_queue(&Q, 1);
    en_queue(&Q, 2);
    en_queue(&Q, 3);
    en_queue(&Q, 4);
    en_queue(&Q, 5);
    en_queue(&Q, 6);
    en_queue(&Q, 7);
    traverse_queue(&Q);
    if (out_queue(&Q, &val)) {
        printf("出队成功,队列出队的元素是:%d\n", val);
    } else {
        printf("出队失败!");
    }
    traverse_queue(&Q);
    return 0;
}
void init(QUEUE *pQ)
{
    pQ->pBase = (int *)malloc(sizeof(int) * 6);
    pQ->front = 0;
    pQ->rear = 0;
}
bool full_queue(QUEUE *pQ)
{
    if ((pQ->rear + 1) % 6 == pQ->front) {
        return true;
    } else {
        return false;
    }
}
bool en_queue(QUEUE* pQ, int val)
{
    if(full_queue(pQ))
    {
        return false;
    }
    else
    {
        pQ->pBase[pQ->rear] = val;
        pQ->rear = (pQ->rear + 1) % 6;
        return true;
    }
}
bool out_queue(QUEUE * pQ,int *pVal)
{
    if (empty_queue(pQ)) {
        return false;
    } else {
        *pVal = pQ->pBase[pQ->front];
        pQ->front = (pQ->front+1) % 6;
        return true;
    }
}
bool empty_queue(QUEUE *pQ)
{
    return (pQ->front == pQ->rear);
}
void traverse_queue(QUEUE *pQ)
{
    int i = pQ->front;
    
    while (i != pQ->rear) {
        printf("%d\n", pQ->pBase[i]);
        i = (i + 1) % 6;
    }
    return;
}

###应用

所有和时间操作都有队列的影子。比如操作系统执行任务,先进去的先执行。时间是个参数(还有其他参数,优先级等等)等待队列,阻塞队列。

分享到