c - 排队/出队奇怪？

Question

我一直在做一项作业，涉及实现包含空指针的队列，以便它们可以针对任何类型的数据进行泛化。我目前遇到一个奇怪的问题，虽然出队节点减少了列表的大小但没有返回我期望的节点。在出列操作中省略对 free() 的调用可以纠正这一点，但因为我想释放出列节点，所以这是不可取的。有什么建议吗？

测试运行:routine.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "queue.h"

int main() {
  queue test = make_queue();
  enqueue("One", test);
  enqueue("Two", test);
  printf("Item is %s!\n", (char *)dequeue(test));
  printf("Item is %s!\n", (char *)dequeue(test));
  return 0;
}

queue.h

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
/* A queue is implemented as a pointer to a structure not specified here. */

typedef struct queue_structure *queue;

struct node {
  struct node * next;
  void * data;
};

struct queue_structure {
  struct node * head;
  struct node * tail;
};

/* List of function protocols. */
bool is_empty_queue(queue q);

/* The make_queue function returns a newly created queue with no values
   stored in it.
*/

queue make_queue() {
  queue newQueue = malloc(sizeof(struct queue_structure));
  return newQueue;
}

/* The enqueue function adds a value to a queue.  Although this function
   does not change the pointer q, fields of the structure to which q
   points may be modified in the course of a call to this function.
*/

void enqueue(void *value, queue q) {
  struct node * newNode = (struct node *)malloc(sizeof(struct node));
  newNode->data = value;    
  if(is_empty_queue(q))
    q->tail = newNode;
  newNode->next = q->head;
  q->head = newNode;
}

/* The dequeue function removes a value from a queue and returns it.
   Although this function does not change the pointer q, fields of the
   structure to which q points may be modified in the course of a call to
   this function.

   It is a precondition of this function that at least one value is stored
   in the queue.
*/

void *dequeue(queue q) {
  if(!q->head->next) { // Only a single item in the queue.
    printf("Only one item in queue!\n");
    struct node * to_dequeue = q->tail;
    void * data = q->head->data;
    free(to_dequeue);
    q->head = NULL;
    q->tail = NULL;
    return data;
  }
  else { // Multiple items in the queue.
    printf("Several items in queue!\n");
    struct node * to_dequeue = q->tail;
    void * data = q->tail->data;
    struct node * trace = q->head;
    while(trace->next && trace->next != q->tail)
      trace = trace->next;
    free(to_dequeue);
    q->tail = trace;
    q->tail->next = NULL;
    return data;
  }
}

/* The front_of_queue function returns the value at the front of a queue
   (that is, the one least recently added to the queue) without removing
   that value from the queue.  It has no side effect.

   It is a precondition of this function that at least one value is stored
   in the queue.
*/

void *front_of_queue(queue q) {
  return q->head->data;
}

/* The is_empty_queue function determines whether a queue is empty,
   returning the true Boolean value if no values are stored in the queue
   and the false Boolean value if one or more values are stored in the
   queue.
*/

bool is_empty_queue(queue q) {
  if(q->head)
    return 1;
  return 0;
}

Answer 1

您没有在 make_queue 中将 head 和 tail 初始化为 NULL 并且您已经进行了空性测试错了，

bool is_empty_queue(queue q) {
  if(q->head)
    return 1;
  return 0;
}

这使得 enqueue 行为异常。

void enqueue(void *value, queue q) {
  struct node * newNode = (struct node *)malloc(sizeof(struct node));
  newNode->data = value;    
  if(is_empty_queue(q))
    q->tail = newNode;
  newNode->next = q->head;
  q->head = newNode;
}

情况 1，可能 head 和 tail 最初是 NULL

head -> 0; tail -> 0  // now enqueue 1
is_empty_queue(q) returns 0 since q->head == NULL, so q->tail still points to 0
n(1)->next = 0
head = n(1)

results in
head -> n(1) -> 0; tail -> 0  // next enqueue 2
is_empty_queue(q) returns 1 since q->head = n(1) != 0, so
q->tail = n(2)
n(2)->next = n(1)
q->head = n(2)

result:
head -> n(2) -> n(1) -> 0; tail -> n(2)

所有进一步的入队操作将离开head == tail。但是，如果您现在 dequeue:

struct node * to_dequeue = q->tail;   // n(2)
void * data = q->tail->data;
struct node * trace = q->head;        // n(2)
while(trace->next && trace->next != q->tail)  // n(2) -> n(1) -> 0
  trace = trace->next;                // trace = n(1)
free(to_dequeue);                     // free n(2)
q->tail = trace;                      // tail -> n(1)
q->tail->next = NULL;                 // already had that

head 是一个悬挂指针。

情况 2，可能 head 最初不是 NULL。

head -> x; tail -> y // enqueue 1
is_empty_queue(q) returns 1 because q->head == x != 0
q->tail = n(1)
n(1)->next = x
q->head = n(1)

head -> n(1) -> x; tail -> n(1) // now enqueue 2
is_empty_queue(q) returns 1 because q->head == n(1)
q->tail = n(2)
n(2)->next = n(1)
q->head = n(2)

head -> n(2) -> n(1) -> x; tail -> n(2)

唯一的区别是现在 n(1)->next != 0，然后如果你出队，trace 将被设置为野外“指针”x 然后检查 x->next，但由于 x 是不确定的位模式，这通常会导致段错误。

除非我忽略了一些东西，在构造时初始化 head 和 tail，修复 is_empty_queue 并检查 dequeue 是否为空> 会给你一个工作计划。

但是如果队列很长，出队操作会很慢，因为它必须遍历整个队列才能找到倒数第二个元素来更新tail。你可以同时拥有enqueue和dequeue，如果你在tail位置入队和dequeue，O(1)操作> 来自 head。