C++ delete error

Question

I'm new to C++ and I'm trying to code a linked-list based queue. My test program worked fine until I added delete to the dequeue function. Then I get the error: malloc: *** error for object 0x7f8a61403a00: pointer being freed was not allocated

Any help would be appreciated.

#include <string>
#include "queue.h"
#include <iostream>
using namespace std;


Queue::Queue() { // Constructs a new empty queue.
    current_size = 0;   // number of elements in queue
    front_p = NULL; // first element in queue
    back_p = NULL;  // last element in queue
}

Queue::Queue( const Queue& q ) {// Copy constructor.
    // nothing to copy if queue empty
    if (q.current_size == 0) {
        return;
    }
    // queue not empty
    else {
        node * p = q.front_p;
        node * n;
        // assign front pointer
        n = new node(p -> data, NULL);
        front_p = n;
        p = p -> next;
        // middle elements
        while (p -> next != NULL) {
            n -> next = p;
            n = new node(p -> data, NULL);
            p = p -> next;
        }
        // assign back pointer
        n = new node(p -> data, NULL);
        back_p = n;
        current_size = q.current_size;
    }
}

void Queue::enqueue( int item ) { // Enqueues <item> to back
    node * n = new node(item, NULL);

    // first item in queue, front & back ptrs point to same element
    if (back_p == NULL) {
        front_p = n;
        back_p = n;
    }
    else {
        back_p -> next = n;
        back_p = n;
    }
    current_size++;
}

int Queue::dequeue() { // removes and returns the front item.
    // empty queue
    if (current_size == 0) {
        return -1;
    }

    int item = front();
    node * p = front_p;
    if (current_size == 1) {
        front_p = NULL;
        back_p = NULL;
        delete p;
        current_size--;
        return item;
    }
    else {
        front_p = front_p -> next;
        delete p;
        current_size--;
        return item;
    }
}

test file

//test  file
#include <iostream> 
#include "queue.h"
using namespace std;

int main(void) {
    Queue q1;
    cout << "Create a new queue q1" << endl;
    cout << "Size of q1 \t" << q1.size() << endl;
    cout << "Is q1 empty? \t" << q1.empty() << endl;
    cout << endl << endl;
    cout << "enqueue \t1,2,3,4,5" << endl;
    q1.enqueue(1);
    q1.enqueue(2);
    q1.enqueue(3);
    q1.enqueue(4);
    q1.enqueue(5);
    cout << "front of q1 \t" << q1.front() << endl;
    cout << "size of q1 \t" << q1.size() << endl << endl;

    cout << "q2 is a deep copy of q1" << endl;
    Queue q2(q1);
    cout << "front of q2 \t" << q2.front() << endl;
    cout << "size of q2 \t" << q2.size() << endl << endl;

    cout << "removed 4 from q1" << endl;
    q1.remove(4);
    cout << "removed 2 from q2" << endl;
    q2.remove(2);
    cout << endl;

    cout << "print out remaining elements of q1" << endl;
    int N = q1.size();
    for(int i=0; i < N; i++) {
        cout << q1.dequeue() << " ";    
    }
    cout << endl << endl;
    cout << "print out remaining elements of q2" << endl;
    N = q2.size();
    for(int i=0; i < N; i++) {
        cout << q2.dequeue() << " ";
    }
    cout << endl;
}

header file

    class Queue
    {
    public:

        Queue(); // Constructs a new empty queue.
        Queue( const Queue& q );// Copy constructor.
        ~Queue();// Destructor.

        void enqueue( int item ); // Enqueues <item>.
        int dequeue();  // Dequeues the front item.
        int front();  // Returns the front item without dequeuing it.
        bool empty();  // Returns true iff the queue contains no items.
        int size();  // Returns the current number of items in the queue.
        bool remove(int item); // If <item> occurs in the queue, removes the 
      // first occurrence of <item> and returns true; otherwise returns false.

    private:
        class node  // node type for the linked list 
        {
       public:
           node(int new_data, node * next_node){
              data = new_data ;
              next = next_node ;
           }
           int data ;
           node * next ;
    };

    node * front_p ; // pointer to the (node containing the) next item 
              //  which to be dequeud, or NULL if the queue is empty.

    node * back_p ; // pointer to the (node containing the) last item 
              // which was enqueued, or NULL if the queue is empty.

    int current_size ; // current number of elements in the queue.
};

Answer 1

There are other issues with the code, but the most immediate one is that your copy-constructor is broken.

In this cycle

    while (p -> next != NULL) {
        n -> next = p;
        n = new node(p -> data, NULL);
        p = p -> next;
    }

p is a pointer to an element of a source queue q. Meanwhile, n is an element of the new queue. By doing n -> next = p; you are making the new queue nodes to link into the source queue node chain. This creates a completely nonsensical node linkage structure, which falls apart later.