[RESOLVED] Remove an element from a queue

[tishobg]

Hello. I need help with this one. The task is as follows: Create a program which creates a queue(FIFO, first in first out) and removes the last element from it. This is my code for the first part aka creating the queue, but I have no clue how to remove the last element.

#include <iostream>
using namespace std;
struct elem
{
	int key;
	elem *next;
}
*first = NULL, *last = NULL;

void push(int n)
{
	elem *p = last;
	last = new elem;
	last->key = n;
	last->next = NULL;
	if (p)
		p->next= last;
	else
		first = last;
}

int pop(int &n)
{
	if (first)
	{
		elem *p = first;
		n = p->key;
		first = p->next;
		delete p;
		if (first == NULL)
			last = first;
		return 1;
	}
	else return 0;
}

void main()
{
	int d;
	do
	{
		cout << "\n Digit:";
		cin >> d;
		if (d)
			push(d);
	} while (d != 0);
	cout << "\n Opashka:"<<endl;
	while (pop(d))
		cout << d << "\t"<<endl;
		system("pause");
}

[2kaud]

You're pushing at last, and poping from first. To remove the last pushed element you need to remove the element at last which means adjusting the pointer at the last but one element to be NULL and then delete the element and adjust last variable. As this is a single linked list, the issue you really have is to obtain a pointer to the last but one element. There are a couple of ways of doing this, which as this seems to be a homework exercise, for the moment I'll leave to you to explore.

Note that in c++ it is good practice to use nullptr rather than NULL.

Also note that being able to delete from both ends of a queue isn't really a feature of a FIFO container!

[tishobg]

After consulting with the guide book, I found something like these as a solution to my problem:

int del_elem(int &n, elem* &start)
{
	elem *p = start, *q;
	if (start)
	{
		if (p->next)
		{
			while (p->next)
			{
				q = p;
				p = p->next;
			}
			q->next = NULL;
		}
		else
			start = NULL;

		n = p->key;
		delete p;
		return 1;

	}
	else
		return 0;

}

It doesn't work though, so some help with the code will be very much appreciated.

[2kaud]

When posting code, please use code tags rather than quote so that the code is readable. Go Advanced, select the formatted code and click '#'.

It doesn't work though

It's often not a good idea to 'take code' and use it without understanding what it is trying to do. In what way? What is the code doing? Now is the time to get to grips with the debugger and learn how to use it. Use the debugger to step through the code tracing its execution and see what is happening. You should then be able to determine the issue. Being able to use the debugger is an important skill that every programmer needs to acquire.

NB. For every last deletion, this method traverses the linked list to find the last but one element. This is time consuming if there are a large number of elements. A more efficient way is to use a doubly linked list. The last element can then be removed without having to first traverse the list.

[tishobg]

I've had some success . This is the current state of my code :

#include <iostream>
using namespace std;
struct elem
{
	int key;
	elem *next;
}
*first = nullptr, *last = nullptr;

void push(int n)
{
	elem *p = last;
	last = new elem;
	last->key = n;
	last->next = nullptr;
	if (p)
		p->next= last;
	else
		first = last;
}

int pop(int &n)
{
	if (first)
	{
		elem *p = first;
		n = p->key;
		first = p->next;
		delete p;
		if (first == nullptr)
			last = nullptr;
		return 1;
	}
	else return 0;
}

int del_elem(int &n)
{
	elem *p = first, *q = nullptr;
	if (first)
	{
		if (p->next)
		{
			while (p->next)
			{
				q = p;
				p = p->next;
			}
			q->next = nullptr;
		}
		else
			first = nullptr;
		n = p->key;
		delete p;
		return 1;

	}
	else
		return 0;

}

void main()
{
	int d;
	do
	{
		cout << "\n Digit:";
		cin >> d;
			if (d)
			push(d);
	} while (d != 0);
	cout << "\n Opashka:"<<endl;
	while (pop(d))
		del_elem(d);
		cout << d << "\t";
		system("pause");
}

I've gotten quite desperate by now ,so if you could help me slightly ,that'd be great. I know i need to learn it myself properly, but I just need those points tomorrow and it's getting awfully late now.

[2kaud]

	while (pop(d))
		del_elem(d);

What are trying to achieve here? You are looping - poping off the elements at one end and also deleting them at the other until the queue is empty??

[tishobg]

I'm not sure where I need to insert the function in order for it to work and delete the last element before printing. I'm really behind on this subject , which explains why I don't do that great. I'm a graphic designer, this is just a side subject I thought I'd give a shot.
Oh wow, dude, thank u so much. I actually just figured what u meant and exchanged these two lines and boom, now it works. Thanks so much for not directly giving me the code, this exercise really frustrated me, but **** it sure feels good to finally get it.

[2kaud]

	//while (del_elem(d))
	//while (pop(d))
		cout << d << "\t";

Depending upon which while is uncommented, this will either remove elements from first or last. If the input is 1 2 3 4 5 6 7 8 9 0 then

while (del_elem(d))

displays

9   8   7   6   5   4   3   2  1

whilst

while (pop(d))

displays

1   2   3   4   5   6   7   8   9

as expected.

pop() gives a FIFO, whilst del_elem() gives a FILO.

[tishobg]

Thanks again, I managed to do it. The last element gets removed now. And i actually understood it.

[tishobg]

Great to know. I've been wondering, what if ,let's say, my task is to delete the 5th or 6th element, just an N-element from it, using my code ,what would need to be added to make it work?

[2kaud]

my task is to delete the 5th or 6th element, just an N-element from it

Then you need to change the while loop in del_elem() to also count the elements traversed and terminate when either p_next is not a pointer or the count is satisfied. But rather than setting q_next to nullptr, you set it to p->next. This is standard element deletion in the middle of a list. You also need to check for edge conditions - deleting the first & last elements. However, in this case it would be more usual to implement the list as doubly linked so the list can be traversed forward and backwards. It makes the code for insertion and deletion slightly more complicated but has performance benefits. If you also keep a count of the number of elements in the list, then to delete element N you start traversing the list from the nearest end.