当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 数据结构入门-队列

数据结构入门-队列

2019年12月16日  | 移动技术网IT编程  | 我要评论

海燕教案,箭在弦上29集,张晋买不起机票

一种可以实现"先进先出"的存储结构

分类：

  1. 链式队列：用链表实现
  2. 静态队列：用数组实现，静态队列通常都必须是循环队列

循环队列的讲解：

  1. 静态队列为什么是循环队列

    减少对内存的浪费

  2. 循环队列需要几个参数来确定

    两个参数，frant 、rear 但这2个参数不同场合有不同的含义，建议初学者先记住

  3. 循环队列各个参数的含义

    队列初始化：front和rear的值都是零

    队列非空：front代表队列的第一个元素，rear代表队列的最后一个有效元素的下一个元素

    队列空：front和rear的值相等，但不一定是零

  4. 循环队列入队伪算法

    将值存入rear所代表的位置

    错误的写法：r = r + 1

    正确的应该是r = (r+1)%数组长度

  5. 循环队列出队伪算法

    front = (front+1)%数组长度

  6. 如何判断循环队列是否为空

    如果front和rear的值相等，则队列为空

  7. 如何判断循环队列已满

    多增加一个表标识的参数

    少用一个元素，通常都是这样：(rear+1) % 数组长度 == front

具体的实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


typedef struct queue
{
    int * pbase;
    int front;
    int rear;
}queue;

void init(queue *);
bool full_queue(queue *);
bool empty(queue *);
bool en_queue(queue * , int val); // 入队
void traverse(queue *);
bool out(queue *, int * pval);


int main(void)
{
    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(&q);
    if (out(&q , &val))
    {
        printf("出队成功，出队的元素：%d\n", val);
        en_queue(&q , 9);
        traverse(&q);
    }
    else
    {
        printf("出队失败\n");
    }


    return 0;
}


void init(queue * pq)
{
    pq->pbase = (int *)malloc(sizeof(int) * 6); // 初始化默认是长度是6
    if (null == pq->pbase)
    {
        printf("初始化失败\n");
        exit(-1);
    }

    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 * pq)
{
    int i = pq->front;

    while(i != pq->rear)
    {
        printf("%d\n",pq->pbase[i] );
        i = (i+1) % 6;
    }

    return;
}


bool empty(queue * pq)
{
    if (pq->front == pq->rear)
    {
        return true;
    }
    else
    {
        return false;
    }
}


bool out(queue * pq, int * pval)
{

    if (empty(pq))
    {
        return false;
    }
    else
    {
        *pval = pq->pbase[pq->front];
        pq->front = (pq->front+1) % 6;
        return true;
    }

}

队列的应用

  • 所有和时间有关的操作都有队列的影子

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网