简介

在一生一芯项目中，我们在预学习C语言Q42中的主要任务为使用C语言实现栈和队列栈和队列，同时要求项目中不能创建stack.c和queue.c,只能使用stack.h和queue.h。

创建工程

可以使用Q33中创建的工程，我们直接将其拷贝到Q42目录下。根据Q42的要求新建两个test文件，和两个h文件，然后删除不需要的文件。
注意：这里还需要更改Makefile文件，原因是题目中不允许创建c文件，所以我们需要注释掉Makefile里面链接库的地方，这里我注释掉TARGET就可以了。

TEST_SRC=$(wildcard tests/*_tests.c)
TESTS=$(patsubst %.c,%,$(TEST_SRC))

# TARGET=build/lcthw.a
SO_TARGET=$(patsubst %.a,%.so,$(TARGET))

all: $(TARGET) $(SO_TARGET) tests

代码实现

先运行make命令编译测试queue_tests.c和stack_tests.c，这里会报很多没有实现的函数，我们根据报错逐一实现。最终代码如下。

stack.h

#ifndef lcthw_Stack_h
#define lcthw_Stack_h

#include <stdlib.h>

#define STACK_FOREACH(S, C)                                                                                            \
    Stack *C = NULL;                                                                                                   \
    for (C = S; C != NULL && C->value != NULL; C = C->next)

typedef struct Stack
{
    void *value;
    struct Stack *next;
} Stack;

Stack *Stack_create()
{
    return calloc(1, sizeof(Stack));
}

void Stack_destroy(Stack *s)
{
    STACK_FOREACH(s, cur)
    {
        free(s);
        s = cur;
    }
    free(s);
}

void Stack_push(Stack *s, void *value)
{
    if (s->value == NULL)
    {
        s->value = value;
        return;
    }
    Stack *temp = calloc(1, sizeof(Stack));
    temp->value = s->value;
    temp->next = s->next;
    s->value = value;
    s->next = temp;
}

int Stack_count(Stack *s)
{
    int count = 0;
    STACK_FOREACH(s, cur)
    {
        count++;
    }
    return count;
}

void *Stack_peek(Stack *s)
{
    if (s == NULL)
        return NULL;
    else
    {
        return s->value;
    }
}

void *Stack_pop(Stack *s)
{
    if (s == NULL || s->value == NULL)
        return NULL;
    Stack *temp = s->next;
    void *value = s->value;
    if (temp != NULL)
    {
        s->next = temp->next;
        s->value = temp->value;
    }
    else
    {
        s->value = NULL;
        s->next = NULL;
    }
    free(temp);
    return value;
}

#endif

queue.h

#ifndef lcthw_Queue_h
#define lcthw_Queue_h

#include <stdlib.h>

typedef struct QueueNode
{
    void *value;
    struct QueueNode *next;
    struct QueueNode *prev;
} QueueNode;

typedef struct Queue
{
    int count;
    QueueNode *first;
    QueueNode *last;
} Queue;

#define QUEUE_FOREACH(Q, C)                                                                                            \
    QueueNode *C = NULL;                                                                                               \
    for (C = Q->first; C != NULL; C = C->next)

Queue *Queue_create()
{
    return calloc(1, sizeof(Queue));
}
void Queue_destroy(Queue *q)
{
    for (int i = 0; i < q->count;i++){
        QueueNode *temp = q->first;
        q->first = temp->next;
        free(temp);
    }
    free(q);
}
void Queue_send(Queue *q, void *value)
{
    q->count++;
    QueueNode *temp = calloc(1, sizeof(QueueNode));
    temp->value = value;
    if (q->first == NULL)
    {
        temp->prev = NULL;
        temp->next = NULL;
        q->first = temp;
        q->last = temp;
        return;
    }
    temp->next = q->first;
    q->first->prev = temp;
    temp->prev = NULL;
    q->first = temp;
}
void *Queue_peek(Queue *q)
{
    return q->last->value;
}
int Queue_count(Queue *q)
{
    if (q == NULL)
        return 0;
    return q->count;
}

void *Queue_recv(Queue *q)
{
    void *result = NULL;
    if (q->count == 0)
        return NULL;
    q->count--;
    result = q->last->value;
    QueueNode *temp = q->last;
    if (q->count == 0)
    {
        free(temp);
        return result;
    }
    q->last = q->last->prev;
    q->last->next = NULL;
    free(temp);
    return result;
}

#endif