【备战春招】第21天 嵌入式工程师学习笔记

课程信息

• 课程名称：物联网/嵌入式工程师
• 章节名称：第5周之第四讲 1-1 队列的基础概念
• 讲师姓名：大白老师

课程内容概述

1. 简介

本节介绍了C语言中的顺序栈的代码实现。

2. 图形操作

• 概述

队列是一种先进先出（First In Fisr Out）的线性表，简称FIFO，允许在一端进行插入操作的叫做队尾，允许删除的一端称为队头。

假如队列的元素为a1,a2,…an,那么如下图所示，a1就是队头元素，

an就是队尾元素。就像我们排队走地下通道，第一个进入的人肯定是第一个出来的人，这个就是我们所说的先进先出，如下图所示**。**

• 队列存储的问题

​ 按照我们之前的学习规律，我们应该会学习队列的顺序存储和队列的链式存储。下面我们先来看看队列的顺序存储。由于我们不知道究竟队列究竟存储多少个元素，因此我们一般定义一个比较大的数组来存储我们的数据。假如我们的一个队列有n个元素，一般下标为0的一般我们叫做队头，所谓的入队操作，就是在数组最后一个元素后，在追加一个新的元素。前面的元素不需要移动。如下图

**而根据我们队列的定义，我们队列的出队操作都是在队头，****也就是在下标为0的位置出队。**那也就是说，我们队列后面的元素相对来说都需要向前移动，以保持我们下标为0 位置不为空。如下图所示。

**这样对我们来说是不是效率太低呢？**若是我们把队头设置为可移动的，也就是说队头不需要一定在下标为0的位置，这样我们的效率不是大大的提高了吗？

**既然我们的数据是****尾入头出，**那么我们就来定义两个变量来表示头和尾，一个叫做front表示我们的队头元素的下标，一个叫做rear表示我们队尾元素的下一个元素下标。

**提问：**为什么要rear要指向我们的队尾元素的下一个元素的下标，而不是直接指向我们的队尾元素的下标呢？

答案：表示队尾元素的下一个元素下标方便我们队空的操作。

• 顺序存储的问题

  • 假设长度是我们有int a[5]的数组，刚开始里面没有存放任何的元 素,front和rear都指向下标为0的位置。
    

  • a1,a2,a3,a4开始入队,front依旧指向了0，rear则指向了4的位置。
    

  • **出队a1,a2,则front指向下标为2的位置，rear不变。如下左图所示，然后在入队a5,此时frone位置不变，raer的位置移动数组之外。**是不是越界了？我们数组中只有3个元素竟然越界了？？？

**这种现象叫做假溢出。

3. 代码常用操作

• head.h

#ifndef __LOOP_BALL_H__
#define __LOOP_BALL_H__

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

#define N 27

typedef int data_t;

// 链式节点类型
typedef struct node
{
    data_t data;
    struct node *next;
} linknode_t;

// 链式栈 栈头类型
typedef struct
{
    linknode_t *top;
    int n;
} linkstack_t;

// 链式队列 队头类型
typedef struct
{
    linknode_t *front;
    linknode_t *rear;
} linkqueue_t;

// 链式栈的相关操作
extern linkstack_t *create_empty_linkstack();
extern int is_empty_linkstack(linkstack_t *s);
extern int push_linkstack(linkstack_t *s, data_t data);
extern data_t pop_linkstack(linkstack_t *s);
extern data_t get_top_data(linkstack_t *s);

// 链式队列的相关操作
extern linkqueue_t *create_empty_linkqueue();
extern int is_empty_linkqueue(linkqueue_t *q);
extern int enter_linkqueue(linkqueue_t *q, data_t data);
extern data_t delete_linkqueue(linkqueue_t *q);

#endif

• linkqueue.c

#include "head.h"

linkqueue_t *create_empty_linkqueue()
{
    linkqueue_t *q = NULL;
    q = (linkqueue_t *)malloc(sizeof(linkqueue_t));
    if (NULL == q)
    {
        printf("malloc is fail!\n");
        return NULL;
    }

    linknode_t *node = NULL;
    node = (linknode_t *)malloc(sizeof(linknode_t));
    node->next = NULL;

    q->front = q->rear = node;
    return q;
}

int is_empty_linkqueue(linkqueue_t *q)
{
    return q->front == q->rear ? 1 : 0;
}

int enter_linkqueue(linkqueue_t *q, data_t data)
{
    linknode_t *temp = NULL;

    temp = (linknode_t *)malloc(sizeof(linknode_t));
    temp->data = data;

    temp->next = NULL;
    q->rear->next = temp;
    q->rear = temp;

    return 0;
}

// data_t delete_linkqueue(linkqueue_t *q)
// {
//   linknode_t *temp = NULL;

//   // q->front->next 可能 为 null
//   temp = q->front;

//   q->front = temp->next;

//   free(temp);
//   temp = NULL;

//   return q->front->data;
// }

data_t delete_linkqueue(linkqueue_t *q)
{
    linknode_t *temp = NULL;
    data_t data;

    // 1.保存原头结点首地址,取出数据
    temp = q->front->next;
    data = temp->data;

    // 2.释放节点
    q->front->next = temp->next;
    free(temp);
    temp = NULL;

    // 3.若是为空,q->front->next == NULL,表示数据都出完了.
    if (q->front->next == NULL)
    {
        q->rear = q->front;
    }

    // 4.返回结点中数据
    return data;
}

• linkstack.c

#include "head.h"

linkstack_t *create_empty_linkstack()
{
    linkstack_t *s = NULL;
    s = (linkstack_t *)malloc(sizeof(linkstack_t));
    if (NULL == s)
    {
        printf("malloc is fail !\n");
        return NULL;
    }
    s->top = NULL;
    s->n = 0;

    return s;
}

int is_empty_linkstack(linkstack_t *s)
{
    return s->n == 0 ? 1 : 0;
}

// 插入操作和删除操作均在链表头部进行，链表尾部就是栈底，栈顶指针就是头指针
int push_linkstack(linkstack_t *s, data_t data)
{
    linknode_t *temp = NULL;

    temp = (linknode_t *)malloc(sizeof(linknode_t));
    if (NULL == temp)
    {
        printf("malloc is fail!\n");
        return -1;
    }
    temp->data = data;
    temp->next = s->top;
    s->top = temp;
    s->n++;
    return 0;
}

data_t pop_linkstack(linkstack_t *s)
{
    data_t data;

    linknode_t *temp = NULL;
    temp = s->top;
    data = temp->data;

    s->top = temp->next;
    s->n--;

    free(temp);
    temp = NULL;
    return data;
}

data_t get_top_data(linkstack_t *s)
{
    return s->top->data;
}

• ballclock.c

#include "head.h"

int print_linklist(linknode_t *head)
{
    linknode_t *p = head->next;
    while (p)
    {
        printf("%-3d\t", p->data);
        p = p->next;
    }
    putchar('\n');
    return 0;
}

int is_original_queue(linkqueue_t *q)
{
    int i = 1;
    linknode_t *p = q->front->next;
    for (i = 1; i <= N; i++)
    {
        if (i != p->data)
        {
            return 0;
        }

        p = p->next;
    }
    return 1;
}

int ball_clock()
{
    linkstack_t *min_stack = NULL,
            *min5_stack = NULL,
            *hour_stack = NULL;
    linkqueue_t *ball_queue = NULL;
    int half_day = 0;
    int ball = 0;

    min_stack = create_empty_linkstack();
    min5_stack = create_empty_linkstack();
    hour_stack = create_empty_linkstack();

    ball_queue = create_empty_linkqueue();

    for (ball = 1; ball <= N; ball++)
    {
        enter_linkqueue(ball_queue, ball);
    }

    print_linklist(ball_queue->front);

    while (1)
    {
        // 从时钟球队列 中 取出小球
        ball = delete_linkqueue(ball_queue);

        // 放入 分钟栈 中，达到4个时停止放入
        if (min_stack->n < 4)
        {
            push_linkstack(min_stack, ball);
            continue;
        }
        // 达到 4 个时，开始从分钟栈 中取出小球，放入 时钟球队列中
        while (!is_empty_linkstack(min_stack))
        {
            enter_linkqueue(ball_queue, pop_linkstack(min_stack));
        }

        if (min5_stack->n < 11)
        {
            push_linkstack(min5_stack, ball);
            continue;
        }
        while (!is_empty_linkstack(min5_stack))
        {
            enter_linkqueue(ball_queue, pop_linkstack(min5_stack));
        }

        if (hour_stack->n < 11)
        {
            push_linkstack(hour_stack, ball);
            continue;
        }
        while (!is_empty_linkstack(hour_stack))
        {
            enter_linkqueue(ball_queue, pop_linkstack(hour_stack));
        }

        enter_linkqueue(ball_queue, ball);

        half_day++;

        // 校验 时钟球队列中的数据 和初始值是否一致，若一致表示一个周期走完
        if (is_original_queue(ball_queue))
        {
            break;
        }
    }

    return half_day / 2;
}

int main()
{
    int day_count = 0;

    day_count = ball_clock();

    printf("reboot time clock boll queue needs %d days\n", day_count);

    return 0;
}

运行结果

1       2       3       4       5       6       7       8       9       10      11      12      13      14      15      16      17      18      19      20      21      22      23
24      25      26      27
reboot time clock boll queue needs 23 days

学习心得

C语言中的数据结构，实践练习了队列的基础概念，感觉很有收获。

课程截图

1. 示例