Member Avatar for eager04

ok im trying to change this from link list to a queue.bt whenever i run it it sill shows from last to first which is the opposite from what i want.here it is, i hope somebody can try to see whats wrong with it.

#include<iostream.h>
#include<conio.h>
struct queue
{
int data;
queue* next;
};
class queueL
{
protected:
queue* last;
queue* first;
public:
queueL()
{last = NULL;}
void additem(int d);
void display();
};
void queueL::additem(int d)
{
queue* newqueue = new queue;
newqueue->data=d;
newqueue->next=last;
last = newqueue;
}
void queueL::display()
{
queue* current = last;
while(current!=NULL)
{
cout<<endl<<current->data;
current = current->next;
}
}
void main()
{
queueL ql;
clrscr();
ql.additem(25);
ql.additem(36);
ql.additem(49);
ql.additem(64);
ql.display();
}

  • 5 Contributors
  • 5 Replies
  • 171 Views
  • 1 Month Discussion Span
  • Latest Post Latest Post by gusano79
Member Avatar for kc0arf

Hi,

I am not a well - versed programmer, but yes, you do have a linked list going there in one direction. How about trying a dual linked list (a list that has pointers going in both directions so that if you had

A B C

and the "now" is on B, that you have the pointer information for both A and C, so that you can move forwards or backwards.

Then, for queue mode, go to the end of the list, and work it backwards using the reverse pointers.

Christian

Member Avatar for infamous

your add_item method should traverse to the END of the list, and add the element there. the remove_item method should remove the first element in the list.

Member Avatar for kc0arf

Hi,

I think infamous is right! Might have mis-read what you are trying to do.

I do know that in my programming days, I did make a lot of linked lists both ways, just for flexibility. I also kept another copy of the head pointer around in another variable in the event I "lost" it during coding.

Christian

Member Avatar for abu_sager

Hello
Why you are using a c-style struct why you are not using a c++ class
here you are a good example

#ifndef QUEUE_H
#define QUEUE_H
enum Error_code {success,overflow,underflow};
template <typename Queue_entry>
class Queue {
public:
	Queue();
	bool empty()const;
	Error_code append(const Queue_entry &);
	Error_code serve();
	Error_code retrieve(Queue_entry &)const;
	~Queue();
	Queue(const Queue &);
	Queue &operator=(const Queue &);
protected:
	struct Node { 
		Queue_entry data;
		Node *next; 
	};
	Node *front,*rear;
};
template<typename Queue_entry>
Queue<Queue_entry>::Queue() {
	rear = front = NULL;
}
template<typename Queue_entry>
Queue<Queue_entry>::Queue(const Queue &x) {
	rear = front = NULL;
	Node *orginalFront = x.front,*orignalRear = x.rear,*q,*p = NULL;
	if (orginalFront != NULL) {
	front = new Node;
	p = NULL;
	front->data = orginalFront->data;
	front->next = NULL;
	p = front;
	
	while (orginalFront != NULL) {
	
		q= new Node;
		q->data = orginalFront->data;
		q->next = NULL;
		p->next = q;
		
		
		orginalFront = orginalFront->next;
		
	}
	
	rear = q;
	}
}

template<typename Queue_entry>
Error_code Queue<Queue_entry>::append(const Queue_entry &x) {
	Node *p = new Node;
	p->data = x;
	p->next = NULL;
	if (rear != NULL ) rear->next = p;
	
	rear = p;
	if (front == NULL) front = rear;
	return success;
}
template<typename Queue_entry>
Error_code Queue<Queue_entry>::retrieve(Queue_entry &item) const{
	if (!empty() ) {
		item = front->data;
		return success;
	}
	return underflow;
}
template<typename Queue_entry>
Error_code Queue<Queue_entry>::serve() {
	if (!empty() ) {
		Node *q = front;
		front = front->next;
		if (front == NULL) rear = NULL;
		delete q;
		return success;
	}
	return underflow;
}
template<typename Queue_entry>
bool Queue<Queue_entry>::empty() const {
	if (front == NULL) return true;
	return false;
}
template<typename Queue_entry>
Queue<Queue_entry> &Queue<Queue_entry>::operator =(const Queue<Queue_entry> &x)
{
	if (this != &x) {
		Node *p = front;
		while (front != NULL) {
			p = front;
			front = front->next;
			delete p;
		}
	
		rear = front = NULL;
	Node *orginalFront = x.front,*orignalRear = x.rear,*q;
	
	if (orginalFront != NULL) {
	front = new Node;
	p = NULL;
	front->data = orginalFront->data;
	front->next = NULL;
	p = front;
	
	while (orginalFront != NULL) {
	
		q= new Node;
		q->data = orginalFront->data;
		q->next = NULL;
		p->next = q;
		
		
		orginalFront = orginalFront->next;
		
	}
	
	rear = q;
	}
	}

	return *this;
}
template<typename Queue_entry>
Queue<Queue_entry>::~Queue()
{
		Node *p = front;
		while (front != NULL) {
			p = front;
			front = front->next;
			delete p;
		}
}
#endif
Member Avatar for gusano79

Hello
Why you are using a c-style struct why you are not using a c++ class
here you are a good example

There is nothing wrong with using a struct for the queue nodes here. If all you're storing are a few pieces of information, there's no need for an overgrown class to handle the same data.

The queue template class posted, while it is an example (I'm assuming it works as advertised), I wouldn't call it a good example--it's a bloated gob of code handed down from on high. It looks like Abu here is more interested in saying "ooh, look at all the features i'm using! classes! enumerations! pointers! const methods! templates!" ...all of which are useful things, but not really necessary for the problem at hand.

If you haven't run across templates yet, have a look at http://babbage.cs.qc.edu/STL_Docs/templates.htm for a start.

Now, on to your question--the solution provided by 'infamous' will work, as will doubly-linking the list and running through the display backward. Another approach is to alter the display method:

void queueL::display()
{
    display_recursive(last);
}

void queueL::display_recursive(queue *n)
{
    if(n == NULL) return;
    display_recursive(n->next);
    cout << endl << n->data;
}

Recursion can be a handy tool when dealing with linked lists. If it's not clear, display_recursive will continue to call itself, passing each successive queue node until it hits the end of the list, i.e. it hits a null next pointer. Then it will display them in reverse order as each recursive call terminates.

This is a little more complicated than the other two solutions; I'm just offering it as an alternative. Now you have at least three ways to get your display method to show the nodes in the desired order.

--sg

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.