使用deque函数时出现SegFault错误

Question

基本上，我正在使用链表实现队列，以尝试模拟人们在商店排队等候整天，并等待前面的人完成他们的业务。前几个人通过得很好，但当我到第二次调用dequeue时，它会发生段错误。gdb调试器说错误来自这一行head = current->next;（其中current = head）。

这是我的dequeue函数：

    void BankQueue::dequeue()
   {
      Node* current=head;
      head=current->next;
      if(head!=NULL)
      {
            head->prev=NULL;
      }
      delete current;
   }

这是enqueue函数（如果我在enqueue时导致内存泄漏）：

    void BankQueue::enqueue(Customer s)
    {
         Node* node= new node;
         node->data=s;
         node->next=NULL;
         if(tail==NULL)
         {
              head=node;
              tail=node;
              node->prev=NULL;
         }
         else
         {
              node->prev=tail;
              tail->next=node;;
              tail=node;
         }

任何能够提供的有关段错误可能发生在哪里的帮助都将非常棒，谢谢。顺便说一下，如果需要，我可以提供更多信息。

- Thomas

---

你在销毁 Node 时做了什么有趣的事情吗？我只看到您在 dequeue 函数中使用 head=current->next; 前没有检查 head (current) 是否为 NULL（此处：）。如果在空队列上进行出队操作，这将导致 segfault。编辑：啊，我认为这就是问题所在，因为 dequeue 不会重置 enqueue 使用的 tail 指针。 - paddy

Answer 1

你的dequeue函数存在缺陷。看看如果head为NULL会发生什么：

void BankQueue::dequeue()
{
    // current == NULL
    Node* current = head;
    // Setting head to NULL->next
    // This will reference memory location 0x00000000 + (some offset)
    head=current->next;
    // This is undefined, but it most likely will return true
    if(head!=NULL)
    {
        // undefined
        head->prev=NULL;
    }
    // Delete NULL
    delete current;
}

同时，是的，在那里需要更新tail。

// After you've made sure that head is valid
if (head == tail) {
    // there is only node, so we just clear tail
    tail = NULL;
}
// Then you proceed with removal

---

Thomas，回复你的评论：

void BankQueue::dequeue()
{
    // If the queue has instances
    if (head)
    {
        // If there is only one instance
        if (head == tail)
        {
            tail = NULL;
        }

        // set the new head
        head = head->next;
        // delete the old head if it exists
        if (head->prev)
        {
            delete head->prev;
        }
        // null data
        head->prev = NULL;
    }
}

- user123

---

那么我应该把 if(head==tail) 放在哪里呢？另外，我需要把 head=current->next 放在 if(head!=NULL) 里面吗？ - Thomas

Answer 2

我之前提出了一个评论，但我想详细说明一下，因为我认为这很可能是问题所在。

你的dequeue函数没有重置tail指针。由于enqueue函数使用此指针来确定队列是否为空，如果您清空队列然后再次放入项目，将会出现问题（因为head将为NULL）。

- paddy

---

是的，当你出队并发现新的“head”是“NULL”时，你还必须将“tail”设置为“NULL”。这对你来说应该很有意义，因为如果没有头，也就没有尾了。 - paddy

Answer 3

在dequeue中加入一个条件if(!head) return;作为第一行。按照建议，你将在此之后被设置。

- Vishal Kumar