c - 如何从我的自定义队列中取出元素

Question

作为练习，我正在尝试创建一个基本队列。我的 deQueue 方法有问题。

#include<stdio.h>

typedef int Task;
typedef struct QueueNode_ QueueNode;
typedef struct TQueue_ TQueue;

struct QueueNode_ {
    QueueNode* next;
    Task task;
};

struct TQueue_ {
    QueueNode* first;
    QueueNode* last;
};

TQueue* initializeQueue(){
    TQueue* queue = NULL;
    queue = malloc(sizeof(TQueue));
    queue->first = NULL;
    queue->last = NULL;
    return queue;
}

void enQueue(TQueue* q, Task t){
    if(q->first == NULL){
       q->first = malloc(sizeof(QueueNode));
       q->first->task = t;
       q->first->next = NULL;
       q->last = q->first;
    } else {
        QueueNode* node = malloc(sizeof(QueueNode));
        node->next = q->last;
        node->task = t;
        q->last = node;
    }
}

void printQueue(TQueue* q){
    QueueNode* node = q->last;
    printf("LAST->");
    while(node != NULL){
        printf("%d->", node->task);
        node = node->next;
    }
    printf("FIRST\n");
}

QueueNode* deQueue(TQueue* q){
    QueueNode* temp = q->first;
    QueueNode* newFirst = q->last;
    q->first = NULL;
    while(newFirst != NULL){
        newFirst = newFirst->next;
    }
    q->first = newFirst;
    return temp;
}

int main(){
    TQueue* queue = initializeQueue();
    enQueue(queue, 1);
    enQueue(queue, 2);
    printQueue(queue);
    QueueNode* node = deQueue(queue);
    printf("%d\n", node->task);
    printQueue(queue);
    return 0;
}

我希望我的 deQueue 方法能够移除队列的头部。但显然并非如此。

这是输出:

LAST->2->1->FIRST
1
LAST->2->1->FIRST

我怀疑我的 deQueue 方法没有用第二个元素替换队列的头部，但我虽然是用 q->first = newFirst; 来做的，所以我有点卡住了。

只是如果不清楚我希望它打印:

LAST->2->1->FIRST
1
LAST->2->FIRST

Answer 1

你可以这样做:

QueueNode* deQueue(TQueue* q){
    QueueNode *tmp = q->last;

    while(tmp->next != q->first) {
        tmp = tmp->next;
    }
    // new first is now the old second element
    q->first = tmp;

    // new firsts' next still points at 
    // old first so we free that memory here
    free(q->first->next);
    q->first->next = NULL;

    return tmp;
}

不要忘记释放内存。

您可以在这里进行测试:http://www.compileonline.com/compile_c_online.php