Queue class

[MRKSalman0349]

I wanted to make a Queue class using linked list implementation and I tried . this is my code and its pop method has problem. plz help me.

  #include <iostream>
#include <cstdlib>

using namespace std;

template <class T>
class Node
{
public:
	Node(){
		next = NULL;
	}
	Node *next;
	T value;
};

template<class T>
class Queue{

public:
	Queue() : t(new Node<T>), size(0)
	{
		t = NULL;

		last = NULL;
		//value is undefined because there is nothing on the stack
	}

	void push(T val){
		Node<T> *newNode = new Node<T>();
		Node<T> *top = t;

		try{
			
			newNode->value = val;
			newNode->next = NULL;
			if (t == NULL)
			{
				last = newNode;
				t = newNode;
				
			}
			else
			{
				
				while (t != NULL){
					t = t->next;
				}
				t = newNode;
				delete newNode;
				t = top;
				
			}
		}
		catch (bad_alloc a){ a.what(); }
		
		cout << "Element added \n";
		size++;
	}

	T pop(){
		T val;
		if (size > 1){
			Node<T> *top = t;
			val = top->value;
			t = top->next;
			delete top;
			size--;
		}
		else{
			throw("Queue is Empty");
		}
		return val;
	}

	int length(){
		return size;
	}




private:
	Node<T> *t;
	Node<T> * last;
	int size;

};


int main(){
	Queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	cout << "size of the stack is " << q.length() << endl;

	cout << q.pop() << endl;
	cout << q.pop() << endl;
	cout << q.pop() << endl;
	system("pause");
}

[Gamer2015]

When deleting a Node you have to set the next of the previous node to null
Also you have to set the top to the new top node

Note: the pointer in Node needs to be declared Note<T>*

template <class T>
class Node
{
public:
	Node() : next(NULL) { }
	Node<T> *next;
	T value;
};

I think it would be a good idea to have a double linked list for that task because you need to modify the prev and the next node if you insert/delete something.
(just my opinion)

[fg109]

@Gamer2015

pop() only deletes the head of the list, so there is no previous node to worry about.

@salman 123

I don't see anything wrong with your function. Can you describe what the problem is?

It probably has to do with this:

				while (t != NULL){
					t = t->next;
				}
				t = newNode;
				delete newNode;
				t = top;

This probably doesn't have anything to do with your problem, but you should fix it.

	Queue() : t(new Node<T>), size(0)
	{
		t = NULL;

EDIT: looked again and found more errors.

[Gamer2015]

@Gamer2015

pop() only deletes the head of the list, so there is no previous node to worry about.

edit: nevermind, the node he needs for that seems to be next and he allready does that

[SECMoG1T]

I hope it would help too, if I give you this custom interface here ; though it might be lacking some stuff it's always a good thing to learn from other people xD.

template<typename T>
struct Node
{
    Node(const T& val,Node* nxtptr):value(val),next(nxtptr){}
    T value;
    Node* next;
};

template<typename T>
class Queue
{
  public:
      Queue():head(nullptr),last(nullptr),size(0){}
      void push(const T& val);
      void pop();
      T& front();
      bool empty() const;
  private:
    Node<T>* head;
    Node<T>* last;
    unsigned int size;
} ;

template<typename T>
bool Queue<T>::empty()
{
    return (!head&&!last&&size==0);
}

template<typename T>
void Queue<T>::push(const T& val)
{
  if(empty())
    {head=last=new Node<T>(val,nullptr); last=last->next;++size;}
  else
    {last=new Node<T>(val,nullptr); lats=last ->next; ++size;}
}

template<typename T>
void Queue<T>::pop()
{
   if(!empty())
   {
       Node<T>* discard=head;
       head=head->next; --size;
       delete discard;
   }
}

template<typename T>
T& Queue<T>::front()
{
  if(!empty())
    return head->value;
}

[MRKSalman0349]

Brother in my code when i run this code in Dev C++ it shows just the first element and then it says the program stopped working


and when i use the visual studio it it says the unable to read the memory and shows the first element only.

I think that in the pust function the next node is not properly set .... plzzz look at this and help me...... i had my most time today working on this code and still got nothing

And @andy1992 in your code this same error pops up. so plz help me

after poping the first element the head and the last pointers are always NULL ..... then it certainly have something to do with my push function

[fg109]

@salman 123

andy1992's code has the same problem as yours in the push function. Did you take a look at what I pointed out?

On line 46, you loop until t == NULL. Then on line 49, you set t = newNode; but how is the node that comes before t supposed to know that its next node is this newNode? It doesn't. (In andy1992's code, last == nullptr, always. Just like your code, the node that comes before last doesn't know that its next is the new node.)

Your loop condition should be while(t->next != NULL) and you should use t->next = newNode;

On line 50 you made a different mistake. You delete the node you just created. I don't know how that makes any sense to you...

On line 22, in your constructor, you assigned the address of a new node to t, but then you set t = NULL;. Why did you create a new node in the first place? This means you have allocated memory sitting somewhere that you cannot de-allocate.

[MRKSalman0349]

Thanks@fg109 ..... it worked but still there is one problem.....

it pops all the elements and when it pops the last element it just throws the exception .....

and can you plz tell me why it didnt work when i delete the newNode like

t->next = newNode;
delete newNode;

i am deleting the newNode coz it is not needed .... does not that cause memory leak.?
why should i not delete newNode while i have already given that address to t->next?

thanks for help///

[Gamer2015]

i am deleting the newNode coz it is not needed .... does not that cause memory leak.?
why should i not delete newNode while i have already given that address to t->next?

it's simple, you point to a memory location and then you free that memory.
So your t->next now points to not allocated memory which causes bad behaviour because you can't check if t->next points to 0 now

[fg109]

Oh, my mistake. You do have a mistake in your pop function. if (size > 1) should be if (size > 0).

i am deleting the newNode coz it is not needed .... does not that cause memory leak.?
why should i not delete newNode while i have already given that address to t->next?

OK, you know that t->next and newNode are both pointers, right? That means that they contain memory addresses to the place where the actual node you created is stored.

So when you set t->next = newNode;, you're telling t->next to copy the address stored in newNode. When you delete newNode;, you are de-allocating the memory that it was pointing to. But since t->next is pointing towards the same memory, well... do you see the problem now?

EDIT: Why do i post so slooooow?
EDIT2: Attempt at amusing anecdotal analogy

Supervillain "programmer": new, go find me somebody *new goes off to find someone*
Henchman "new": Boss, here's someone's address *hands over an envelope labeled newNode*
Supervillain "programmer": Thanks new *copies the address in newNode into another envelope labeled t*
Supervillain "programmer": delete, go kill the person at this address *hands over the envelope labeled newNode*
Henchman "delete": OK boss. *heads off to kill someone*
Supervillain "programmer": shakedown, go shake down the person at this address for all his cash *hands over the envelope labeled t*
Henchman "shakedown": OK boss. *heads off to shake someone down, but returns angrily*
Henchman "shakedown": Boss, I went where you said but that stupid delete already killed the guy! How am I supposed to shake down a dead person?

[MRKSalman0349]

Thanks @fg109 and @Gamer2015 and the other guys ... the solution helped me but i wanna understand one thing.....

suppose

int *p;
int *p1 = p;
delete p;

will this delete p1 too?and if yes why? *p1 is another pointer? plz explain

[fg109]

You can't delete p because it's not pointing at anything right now.

[MRKSalman0349]

S s = new S();//suppose its an object of some class S
int *p = &s;
int *p1 = p;
delete p;

will this delete p1 too?and if yes why? *p1 is another pointer?now explain me please if you dont mind?

[fg109]

That code is still wrong, because new S() returns the address of the new object of class S that you just created, which is of type S*, not type S.

Anyway, refer to the analogy I gave you a couple posts ago. In this case, instead of envelopes labeled newNode and t, they're envelopes labeled p and p1.