《数据结构》——队列相关知识点笔记

队列
定义：一种可以实现“先进先出”的存储结构
分类：
静态队列：用数组实现
链式队列：用链表实现
循环队列的讲解：

1. 静态队列为什么必须是循环队列
   传统方式实现不了
2. 循环队列需要几个参数来确定，及其含义
   需要两个参数来确定：front，rear
3. 循环队列各个参数的含义
   2个参数不同场合有不同的含义
   建议初学者先记住，然后慢慢体会

     1）.队列初始化
         front和rear的值都是零
     2）.队列非空
         front代表的是队列的第一个元素
         rear代表的是队列的最后一个有效元素的下一个元素
     3）.队列空
         front和rear的值相等    ，但不一定是零

4. 循环队列入队伪算法讲解（%是取余）
   两步完成：
   1.将值存入rear所代表的位置
   2.rear=（rear+1）%数组的长度
5. 循环队列出队伪算法讲解
   front=（front+1）%数组的长度
6. 如何判断循环队列是否为空
   如果front与rear的值相等，
   则该队列一定为空
7. 如何判断循环队列是否已满
   预备知识：

     front的值可能比rear大
     front的值也可能比rear小
     当然也可能两者相等

   两种方式

     1.多增加一个标识参数
     2.少用一个元素【通常用这种方式】
         如果rear和front挨着，则队列已满
         c语言伪算法表示就是：
             if（（rear+1）%数组长度==front）
                 已满
             else
                 不满    

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

#include <stdio.h>
#include <malloc.h>


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

void init(QUEUE *);
bool en_queue(QUEUE *,int val);
void traverse_queue(QUEUE *);
bool full_queue(QUEUE *);
bool out_queue(QUEUE *,int *);
bool empty_queue(QUEUE *);

int main(void)
{
    QUEUE Q;
    int val;

    init(&Q);
    en_queue(&Q,1);
    en_queue(&Q,2);
    en_queue(&Q,3);
    en_queue(&Q,5);
    en_queue(&Q,4);
    en_queue(&Q,5);
    en_queue(&Q,6);
    en_queue(&Q,7);
    en_queue(&Q,8);
    traverse_queue(&Q);

    if(out_queue(&Q,&val))
    {
        printf("出队成功，出队元素为：%d\n",val);
    }
    else
    {
        printf("出队失败！\n");
    }
    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;
    }

}

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

bool empty_queue(QUEUE *pQ)
{
    if(pQ->front==pQ->rear)
    {
        return true;
    }
    else
    {
        return false;
    }
}

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;
    }

}