出列循环链表中的最终节点

Question

当我在 C++ 中尝试去 queue 基于 queue 的循环链表中的最后一个节点时，我遇到了分段错误。最后一个元素之前的其余元素已成功删除，它只是最后一个元素，它似乎是解除分配的问题但是来自终端的唯一日志是分段错误：11。有人可以帮助我理解为什么我会出现这种行为.我在下面粘贴了完整的实现文件，以防 Enqueue 函数或构造函数出现问题。

#include "BQUEUE.h"
#include <iostream>

using namespace std;

BQUEUE::BQUEUE(): front(nullptr) {}

BQUEUE::BQUEUE(const BQUEUE & queue){
  bqnode *temp = queue.front;
  while (temp->next != queue.front){
    Enqueue(temp->time);
    temp = temp->next;
  }
  Enqueue(temp->time);
}

BQUEUE::~BQUEUE(){
  bqnode *current = front;
  while (current->next != front)
    Dequeue();
}

void BQUEUE::Dequeue(){
  // Empty queue
  if (front == nullptr){
    return;
  } else if (front->next == front){
    front->next = nullptr;
    delete front;
    front = nullptr;
  } else {
    bqnode *temp = front, *current = front;
    while (current->next != front)
      current = current->next;
    front = front->next;
    current->next = front;
    delete temp;
  }
}

void BQUEUE::Print(){
  bqnode *temp = front;
  while (temp->next != front){
    cout << temp->time << endl;
    temp = temp->next;
  }
  cout << temp->time << endl;
}

void BQUEUE::Enqueue(int i){
  bqnode *newNode = new bqnode;
  newNode->time = i;
  if (front == nullptr){
    front = newNode;
    front->next = front;
  } else {
    newNode->next = front;
    bqnode *previous = front;
    if (previous->next == front){
      front->next = newNode;
      return;
    }
    while (previous->next != front)
      previous = previous->next;
    previous->next = newNode;
  }
}

DRIVER:

#include <iostream>
#include "BQUEUE.h"

using namespace std;

int main(){
  BQUEUE k;
  k.Enqueue(60);
  k.Dequeue(); // Segmentation fault occurs here
}

HEADER:

#ifndef BQUEUE_H
#define BQUEUE_H

class bqnode {
public:
  int time;
  bqnode *prev, *next;
};

class BQUEUE {
  public:
    BQUEUE();
    ~BQUEUE();
    BQUEUE(const BQUEUE &);
    void Enqueue(int);
    void Dequeue( );
    void Print( );
  private:
    bqnode *front;
  };

#endif

Answer 1

一期是这样的：

void BQUEUE::Dequeue() {
    // Empty queue
    if (front == nullptr) {
        return;
    }
    else if (front->next == front) {  // <-- This is invoked when there is only one node remaining
        front->next = nullptr;
        delete front;
        front = nullptr;  // <--- This is now nullptr
    }
...

然后在析构函数中，你没有检查 front 是否是 nullptr:

BQUEUE::~BQUEUE() {
    bqnode *current = front;  // <-- No check to see if front is nullptr
    while (current->next != front)
        Dequeue();
}

然后您访问 current->next，这是无效的，因为 current 是 nullptr。修复方法是简单地检查 front 是否为 nullptr，如果是，则无需执行任何操作。

BQUEUE::~BQUEUE() {
    if ( front )
    {
        bqnode *current = front;  
        while (current->next != front)
            Dequeue();
    }
}

出列循环链表中的最终节点

Dequeue final node in circular linked list

c++

queue

data-structures

circular-queue