用 C 语言实现 FIFO 队列

Question

对于嵌入式应用程序，我尝试使用 ANSI C 实现先进先出 (FIFO) 结构队列。最直接的方法似乎是通过实现链表，以便每个结构包含指向队列中下一个的指针。因此，我将结构本身定义为：

typedef enum { LED_on, LED_off, etc } Action;
typedef struct Queued_Action QueuedAction;

struct Queued_Action
{
    Action       action;
    int          value;
    QueuedAction *nextAction;
};

到目前为止一切顺利。如果我将指向队列中第一个和最后一个项目的指针定义为：

QueuedAction *firstAction;
QueuedAction *lastAction;

...那么我希望能够通过声明（例如）向队列添加新操作：

if (!add_action_to_queue(LED_on, 100, &lastAction))
     printf("Error!\n);

...所以在返回时，lastAction 将是指向队列中新创建的最后一个操作的指针。因此，将操作添加到队列的例程将如下所示：

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    *lastAction -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    *lastAction = newQueuedAction;
    return 1;
}

一切都会很好，但此代码无法编译。错误出现在

*lastAction -> nextAction = newQueuedAction;

...编译器声明“->”左侧的项目的行不是有效的结构。然而，确实必须如此。如果事实上我做了应该是完全冗余的转换：

fakeAction = (QueuedAction *)(*lastAction);
fakeAction -> nextAction = newQueuedAction;

...那么编译器会很高兴。但是，我担心错误消息暗示着我可能在这里做错了一些微妙的事情。所以（言归正传），谁能告诉我为什么编译器不高兴，以及是否有更好的方法来完成我在这里尝试做的事情。

Answer 1

你有没有尝试过：

(*lastAction) -> nextAction = newQueuedAction;

Answer 2

你也可以这样做：

(*lastAction)->nextAction

我认为这是一个操作者优先的问题。

Answer 3

我制作了一个可以处理队列的小型库。 "UltraQueue"

它是用 C++ 编写的，但与 ANSI C 完全兼容。
如果您确实愿意，可以轻松地将其转换为 ANSI C。

源代码可通过 GIT 获取。

格茨

Answer 4

我希望这能提前帮助您。
首先，对不起我的英语。它可能有一些语法或拼写错误。

我在您的代码中看到的问题主要是您混合了指针的定义和同一指针的实现。

从 ANSI C 到 C99，甚至在 C++ 中（未在 C# 中测试），使用指针的一个大技巧可能会有所帮助：认为指针是向量的第一个元素，[0] 一个。

解释这个概念的一个很棒的网站是：http://boredzo.org/pointers/

翻译，以及一个很好的黑客工具，可以更好地理解指针。

行动起来吧，孩子们。

用于将元素添加到列表中的函数

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    *lastAction -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    *lastAction = newQueuedAction;
    return 1;
}

包含一些错误。首先，考虑使用

*lastAction -> ...;

as

lastAction[0] -> ...;

正如您所看到的，您不能使用 -> 运算符来访问内部元素。

这里也发生同样的情况：

lastAction[0] = newQueuedAction;

您无法在结构内部复制指针。 lastAction，使用这个 hack 来更好地理解，它不再是一个指针 - 事实上，它是编译器分配到那里的结构中第一个元素的内容 - 所以你需要更改这一行，也可以更改指针值：

lastAction = newQueuedAction;

使用此翻译和注释，您的代码现在将是：

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    lastAction[0] -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    lastAction[0] = newQueuedAction;
    return 1;
}

现在，错误是可见的：您尝试错误地使用 -> 运算符。这意味着您的代码将以两种方式进行更改：

• 使用 -> 运算符

它看起来像这样：

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    lastAction -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    lastAction = newQueuedAction;
    return 1;
}

• 将 . 运算符与 [0]

看起来像这样：

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    lastAction[0].nextAction = newQueuedAction;
    newQueuedAction[0].nextAction = NULL;
    newQueuedAction[0].action = newAction;
    newQueuedAction[0].value = newValue;

    // Designate the new Action as the new lastAction:
    lastAction = newQueuedAction;
    return 1;
}

不要忘记删除 == NULL 代码，你会遇到一个消极攻击性的程序员，他将 NULL 定义为其他东西 始终使用大括号来确保可扩展性。这行只是代码风格的推荐。

希望有帮助，