一，前言

上一篇blogC工程自动注册子模块_框架重构--Apple的学习笔记更新了工程框架，更像是大型工程的感觉。而前面的例子中已经演示了小链表的的使用。等于这些数据结构是打包在大的对象结构中的，而只要操作这些局部的数据结构，大的对象也可以连接起来。当然在绑定关系中侧重应用于链表。而接下来我做的是栈和队列，由于感觉大型工程应用的不多，所以我就单独实现，不添加额外应用场景的功能。

二，队列

队列是先进先出的，它可以使用顺序存储结构和链式存储结构。顺序存储其实就是数组，但是数组有限制大小，当然链表也有限制大小，但是它的大小会比较大，取决于内存大小。有些可以顺序栈是循环顺序栈，就是围成一个圈，可以支持覆盖。队列的比较常见我就不贴代码了。链式的我贴下备忘下，这个代码也是参数网上的blog做了简单修改。
test3.c对于顺序队列的结构体设计如下

typedef struct node
{
    uint8 ucBuf[MAXLEN];
    uint8 count;
    uint8 front;
    uint8 rear;
} CQNode;

test4.c对于链式队列的完整代码如下，这个结构体设计为了一个独立的单链表，而top和rear变成了单独一个指向链表的point对象。原来不必都打包到一起的，其实链表的思路就是分散化，所以想起来qemu的双链表也是一单独的head链表可以指向另外一个链表的头和尾，然后单独一个节点链表包括前和后。qemu这样的结构体设计思路也是分散化的。

/*******************************************************************************
| Project                      : queue array
| Description                  : create;insert;remove;traversal functions
| CPU and Compiler             : win10 CodeBlocks MinGw32
|               R E V I S I O N   H I S T O R Y
|-------------------------------------------------------------------------------
| Date        Version   Author     Description
| ----------  --------  ------     ---------------------------------------------
| 2020-04-28  01.00.00  AppleCai   First version
*******************************************************************************/
/*********************
 *      INCLUDES
 *********************/
#include <stdio.h>
#include <stdlib.h>
#include "../../typedef.h"
#include "../../utility/module.h"
#include "../misc/log.h"

/**********************
 *      MACROS
 **********************/
#define MAXLEN   3u
#define FILLNUM  0xFFu
#define Empty    0
#define NoEmpty  1
/**********************
 *      TYPEDEFS
 **********************/
typedef struct QNode
{
    uint8 data;
    struct QNode *next;
}Node;
typedef struct QueuePoint
{
    Node *front;
    Node *rear;
    uint8 length;
}Queue;

/**********************
 *     GLOBAL VAR
 **********************/

/**********************
 *     CONST VAR
 **********************/

/**********************
 * Functions Implement
 **********************/
int IsemptyQueue(Queue p)
{
    if (p.front == p.rear)
    {
        return Empty;
    }
    else
    {
        return NoEmpty;
    }
}
Queue DeletNode (Queue p)
{
    Node *del;

    if (IsemptyQueue(p) == Empty)
    {
        printf("Nothing can be pop up\n");
        return p;
    }
    else
    {
        if (p.front->next == p.rear)
        {
            free(p.rear);
            p.rear = p.front;
            p.front->next = NULL;
            p.length--;
        }
        else
        {
            del = p.front->next;
            p.front->next = p.front->next->next;
            free(del);
            p.length--;
        }

        return p;
    }
}
/* init head */
static Queue initQ (Queue p)
{
    p.front = p.rear = (Node *)malloc(sizeof(Node));
    if (p.front == NULL && p.rear == NULL)
    {
        printf("initialization failed\n");
    }
    p.front->next = NULL;

    return p;
}
/**
 * add node
 * @param p: head of the single list
 * @param data: data to be add
 */
Queue AppendNode (Queue p,uint8 data)
{
    Node *q;

    q = (Node *)malloc(sizeof(Node));
    if (q == NULL)
    {
        printf("No enough memory to allocate");
        exit(0);
    }
    p.rear->next = q;    /* add q in last node */
    p.rear = q;          /* point to the last node */

    p.rear->data = data; /* add data to the new node */
    p.rear->next = NULL; /* the next of new node point to NULL */
    p.length++;
    return p;            /* return head */
}

void DisplyNode (Queue p)
{
    if (IsemptyQueue(p) == Empty)
    {
        printf("Empty now\n");
    }
    else
    {
        p.front = p.front->next;
        printf("Now has %d values,include:\n",p.length);
        while (p.front != NULL)
        {
            printf("%d ", p.front->data);
            p.front = p.front->next;
        }
        printf("\n");
    }
}

void queue2(void)
{
    printf("you select queue array test example 2!\n");
    /*********** Init *****************************/
    Queue q;

    q.front = q.rear = NULL;
    q.length = 0;
    q = initQ(q);
    printf("EnQueue value 0x1\n");
    q = AppendNode(q,1);
    printf("EnQueue value 0x2\n");
    q = AppendNode(q,2);
    DisplyNode(q);
    printf("DeQueue value is %d\n",q.front->next->data);
    q = DeletNode(q);
    DisplyNode(q);
    /*********** End ******************************/
}
/* Do initial call before main */
EXAMPLE_REGISTER(queue2,"queue2",4)

三，栈

栈是先进后出的，它可以使用顺序存储结构和链式存储结构，顺序存储感觉太简单了，所以就不实现了，而链式存储我一开始没想到用什么样的好方法去构造对象结构。网上搜索了下发现单链表的头插法非常合适。栈不就是头插吗？

/*******************************************************************************
| Project                      : stack array
| Description                  : create;insert;remove;traversal functions
| CPU and Compiler             : win10 CodeBlocks MinGw32
|               R E V I S I O N   H I S T O R Y
|-------------------------------------------------------------------------------
| Date        Version   Author     Description
| ----------  --------  ------     ---------------------------------------------
| 2020-04-28  01.00.00  AppleCai   First version
*******************************************************************************/
/*********************
 *      INCLUDES
 *********************/
#include <stdio.h>
#include <stdlib.h>
#include "../../typedef.h"
#include "../../utility/module.h"
#include "../misc/log.h"

/**********************
 *      MACROS
 **********************/
#define MAXLEN   3u
#define FILLNUM  0xFFu

/**********************
 *      TYPEDEFS
 **********************/
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;

/**********************
 *     GLOBAL VAR
 **********************/

/**********************
 *     CONST VAR
 **********************/

/**********************
 * Functions Implement
 **********************/
void push(lineStack * stack,uint8 a){
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    line->next=stack->next;
    stack->next = line;   /* head insert */
}
boolean pop(lineStack * stack,uint8 *value){
    boolean ret = 0;
    if (stack->next) {
        lineStack * p=stack->next;
        *value = p->data;
        stack->next=p->next;
        free(p);
    }else{
        printf("empty");
        return 1;
    }
    return ret;
}

void printstack(lineStack * stack)
{
    lineStack *p=stack->next;
    printf("Stack include:");
    while(p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");

}
void stack1(void)
{
    printf("you select stack array test example 2!\n");
    /*********** Init *****************************/
    lineStack * stack=(lineStack*)malloc(sizeof(lineStack));//NULL;
    stack->next = NULL;
    uint8 popval = 0;
    printf("push 1\n");
    push(stack, 1);
    printf("push 2\n");
    push(stack, 2);
    printf("push 3\n");
    push(stack, 3);
    pop(stack,&popval);
    printf("pop value is %d\n",popval);
    printstack(stack);
    printf("push 4\n");
    push(stack, 4);
    pop(stack,&popval);
    printf("pop value is %d\n",popval);
    printstack(stack);
    /*********** End ******************************/
}
/* Do initial call before main */
EXAMPLE_REGISTER(stack1,"stack1",5)

运行效果

image.png

四，总结

以前栈和队列其实我不怎么用链表方式去实现的。所以自己创造发明的时候就会卡住，不确定如何定义结构体实现起来才最容易。经过了栈和队列的链式方式实现，我感觉定义一个好的对象结构体还是很重要的，毕竟后面的代码实现都是围绕这个结构体进行的。包括之前多种双链表的设计，也是结构体不同导致实现方式不同，效率不同。