队列知识总结

Julia999

队列
定义：
      一种可以实现‘先进先出’的存储结构（只允许在一端进行插入操作，在另一端进行删除操作的线性表）
分类：
       链式队列---用链表实现
       静态队列---用数组实现
             静态队列通常必须是循环队列
             循环队列：
             1.静态队列为什么一定是循环队列
             2.循环队列需要几个参数来确定及其含义
                     2个参数   front 和rear
             3.循环队列各个参数的含义
             2个参数在不同场合有不同的定义
                         1）队列初始化：front和rear的值都是0
                         2）队列非空：
                                  front代表的是队列的第一个元素
                                  rear代表的是队列的最后一个有效元素的下一个元素
                         3）队列空
                                   front和rear的值相等，但不一定都是0

             4.循环队列的入队伪算法                    （如果刚开始的时候front和rear在相同的位置，那么说明这是一个空队列，那么如果需要将元素入队，那么就将元素放在front所在的位置，然后rear向后移动一个元素位置）
                    1.将值存入r所代表的位置
                    2.r=r+1;  //这样写肯定是错误的
                       正确的写法是:r=(r+1)%数组的长度
             5.循环队列的出队伪算法
                    f=(f+1)%数组的长度


             6.如何判断循环队列是否为空
                    如果front和rear的值相等，该队列一定为空


             7.如何判断循环队列是否已满
             预备知识：
             front和rear的值之间没有什么规定的谁比谁大的关系
             两种方式：【通常用第二种方式】
                   1.多增加一个标识参数
                   2.少用一个元素（如果r和f紧挨着，那么队列已满）
                   if((r+1)%数组的长度==f)
                          已满
                   else
                          不满

           队列算法
                 入队
                 出队
           队列的具体应用：
                 所有和时间有关的操作都与队列都有队列的影子

#include<stdio.h>
#include<mallloc.h>

typedef struct Queue
{
        int *pBase;
        int front;
        int rear;

}QUEUE;

void init(QUEUE *pQ)
{
        *pQ->pBase(int *)malloc(sizeof(int)*6); //指向了一个24字节的数组
        pQ->front=0;
        pQ->rear=0;
}

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 full_queue(QUEUE *pQ)
{
        if((pQ->rear+1)%6==pQ->front)
                return true;
        else
                return false;
}

void traverse_queue(QUEUE *pQ)
{
        int i=pQ->front;
        while(i!=pQ->rear)
        {
                printf("%d ",pQ->pBase[i]);
                i=(i+1)%6;  //i不断往后移
        }
        printf("\n");
}

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)
{
        if(pQ->front==pQ->rear)
                return true;
        else
                return false;
}
int main()
{
        Queue Q;
        inti(&Q);
        int val;
        en_queue(&Q,1);
        en_queue(&Q,2);
        en_queue(&Q,3);
        en_queue(&Q,4);
        en_queue(&Q,5);
        en_queue(&Q,6);

        traverse_queue(&Q);
        if(out_queue(&Q,&val))
                printf("出队成功，队列出队的元素是：%d\n",val);
        else
                printf("出队失败！");

        return 0;
}

                        
链队列
我们将队头指针指向链队列的头结点，而队尾指针指向终端结点（头结点不是必要的，但是为了方便操作，我们加上了）
空对列的时候，front和rear都指向头结点

创建一个队列需要完成两个任务：
1.在内存中创建一个头结点
2.将队列的头指针和尾指针都指向这个生成的头结点，因为此时是空队列