ETA: okay take two, I thought I had the problem fixed, turn out no. Okay so I'm a student on work term teaching myself C++ coming from a background in Java, having done that for the past two years in school. I'm having a tough time with some concepts and thought converting my java labs to C++ would help me understand. The lab is a priority queue, meant to take integers via an insert method and store them in ascending order. The remove method should remove the node at the head. My code compiles but breaks on runtime.

Here's the java code, the insert method is wrong actually and I've corrected it in the C+ version:

class QueueA2{
	private DNode head,tail;
	private int size;
	public QueueA2(){
		head = tail = null;
		size = 0;
	}
	public void insert(int x){
		DNode n = new DNode();
		n.setData(x);
		if(size == 0)
			head = n;
		else{
		DNode temp = head;
			while(temp != null){
				if(x > temp.getData()){
				tail.setNext(n);
				n.setPrev(tail);
				tail = n;
			}
				else {
				if(x < temp.getData()){
				temp.setPrev(n);
				n.setNext(temp);
				head = n;
				}
				/*else if(x > temp.getData() && x < tail.getData()){*/
				}
			}
		}
	size++;
	}	
	
	public void dequeue(){
		if(size == 0)
			System.out.println("Cannot Dequeue, queue is empty");
		else{
			if(size == 1){
				head = tail = null;
				size = 0;
			}
			else{
				head = head.getNext();
				size = 0;
			}
		}
	}
	public void print(){
		DNode temp = head;
		while(head != null){
			System.out.print(temp.getData()+ " ");
			temp = temp.getNext();
		}
		System.out.println();
	}
}

And this is the C++ code

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



Queue::Queue()
{
	head = tail = 0;
	size = 0;
}
void Queue::insert(int x)
{
	DNode *n = new DNode();
	n->setData(x);
	

	if(size == 0)
	{
		head = n;
	}

	else
	{
		
		if(x < head->getData())
		{
			head->setPrev(n);
			n->setNext(head);
			n = head;
		}
		else if(x > tail->getData())
		{
			tail->setNext(n);
			n->setPrev(tail);
			n = tail;
		}
		else if(x > temp->getData() && x < tail->getData())
		{
                        DNode *temp = new DNode();
                        temp = head;
			while(temp != 0)
			{
				if(x > temp->getData())
				{
					temp = temp->getNext();
				}
				else
				{
					DNode *prevTemp = temp->getPrev();
					n->setNext(temp);
					temp->setPrev(n);
					n->setPrev(prevTemp);
					prevTemp->setNext(n);
				}
			}
		}
	}
	size++;
}

void Queue::remove()
{
	if(size == 0)
	{
		cout << "Queue is empty \n";
	}
	else
	{
		if(size == 1)
		{
			head = tail = 0;
			size = 0;
		}
		else
		{
			head = head->getNext();
		}
	}
}


void Queue::print()
{
	DNode *temp = head;
	while(temp != 0)
	{
		cout << temp->getData();
		temp = temp->getNext();
	}
	cout << "\n";
}

Edited 5 Years Ago by dyingatmidnight: n/a

Line 33 looks problematic on the second insert. I see tail being assigned to 0 earlier, but I see nowhere where you assign tail to be anything other than 0, so on line 33 you would be dereferencing a null pointer. Can't do that. Seems to me that on your first insert, where you assign head the value of the new node on line 21, you should set tail equal to that too.

I believe you're right, I took the insert method from the C++ code and put it into the java code and it brought back a null pointer exception as well.

Given your spec (you only pop from the head and you insert in places other than the tail), I don't know that you even need a tail. The head should be able to handle everything. The only reason for a tail is so that, in a normal FIFO queue as opposed to your queue, you have a tail so you don't have to traverse the entire queue to insert since you're always inserting at the end. In your queue, since you keep it sorted, you have to traverse anyway, so the tail seems like unnecessary overhead. If you wanted to be able to remove the element at either end, it would be worth keeping the tail, but that doesn't seem to apply in your case.

all right, now my only problem is that the insert method is still wrong XD, but at least that's an error I should be able to figure out on my own, thanks for the help

ETA: The queue shouldn't always insert at the end - which is actually the trouble I'm having now.

for example, if I were to insert the values 1,5,2,4,3 it should store them with 1 at the head, followed by 2,3,4, and 5 at the tail however as it is right now I'm getting 1 followed by 3, its not inserting in the middle and considering that was the section I was unable to complete the first time around last year... I'll have to fiddle with things to get it right.

Edited 5 Years Ago by dyingatmidnight: n/a

By the way, you have a memory leak in this queue class. I understand the garbage collector takes that responsibility off your back when in Java, but in C++, you are responsible for cleaning up your own mess, like grown-ups do. So, in the remove function, you need to delete the old head pointer sometime before you return from the function. As so:

void Queue::remove()
{
  if(size == 0) {
    cout << "Queue is empty \n";
  } else {
    DNode* garbage = head; //store the old head pointer. 
    if(size == 1)
      head = tail = 0;
    else
      head = head->getNext();
    --size;
    delete garbage; //delete the old head pointer.
  }
}

Also, line 31 and 37 are inverted. What you want is to set tail to be a pointer to the new node "n" not the other way around. N.B.: Be sure you understand the difference between reference-semantics that Java uses and value-semantics that C++ uses. In Java, these lines might have the behaviour you expect, but not in C++, because of value-semantics.

At line 39, you should just have "else" not an else-if.

Line 41 should disappear.

After line 55, you should have break; statement to get out of the loop, otherwise the new node will get inserted ad infinitum and the loop will never end.

That's all I can see. If you really want to move to C++, learn to use STL containers and algorithms instead. A priority queue is available there, btw (and implemented as a heap, which is much better than a linked-list).

Edited 5 Years Ago by mike_2000_17: n/a

Thanks for the help, I suspect I had it wrong in java before anyway. Thank for the suggestions. I'm not really doing this so that I can use it for anything, merely for syntax comparison. I'm not really concerned with what's better application wise I'm merely trying to take code I understand (which at this point I'm questioning given I can't seem to get insert() to work in either java or C++ - just one of those days I guess) and compare and contrast the two.

Syntactically, they are very similar. But, I would say, the important differences are the things that are hidden in Java and for which you are responsible in C++. That includes:

- Cleaning up: C++ is not garbage collected. This means everything that you allocate with new has to eventually be deleted explicitly (with delete) when the memory is no longer needed (although experienced C++ programmers have much better tricks to manage memory which is typically far better than the vanilla solution of garbage collection in Java).

- Value-semantics: All variables, including objects, have value-semantics in C++. In Java, all objects just look like they are objects when really they are pointers to objects, but Java hides that fact from you (that is one of the things I hated the most when having to write Java code). In C++, if you want "reference-semantics", you have to do so explicitly in the code (by using references and pointers, and handling those correctly).

Then, of course, one of the major differences is the standard library. Be sure to explore this reference site to see the tools available in C++.

This article has been dead for over six months. Start a new discussion instead.