Функция удаления и добавления элементов в середину. Класс очередь (Си).

[Nekit9401]

Здравствуйте, у меня имеется класс очередь. Подскажите пожалуйста, как реализовать для этого класса функцию добавления элемента в середину и функцию удаления элемента из середины?

 #include <stdio.h>

struct Node
{
	int data;
	Node* next;
};
	
class Queue
{
	public:
		Queue();
		Queue(int);
		~Queue();
		void AddToBack(int);     //Добавить элемент в конец очереди
		void DeleteFirstNode();      //Удалить первый элемент из очереди
		void Print() const;
		void PrintFirstNode() const;     //Читаем первый элемент очереди
	private:
		Node* first;
		Queue(const Queue& l);     //Прототип конструктора копирования
		const Queue& operator=(const Queue& l);     //Прототип оператора присваивания
};

Queue::Queue()
{
	first=NULL;
}

Queue::Queue(int x)
{
	first=new Node;
	first->data=x;
	first->next=NULL;
}

Queue::~Queue()
{
	while (first!=NULL) 
	{
		Node* next=first->next;
		delete first;
		first=next;
	}
}

void Queue::AddToBack(int x)
{
	if(first==NULL)
	{
		first=new Node;
		first->data=x;
		first->next=NULL;
	}
	else 
	{
		Node* z=first;
		for(;z->next!=NULL;z=z->next)
		{}
		z->next=new Node;
		z->next->data=x;
		z->next->next=NULL;
	}
}

void Queue::DeleteFirstNode() 
{
	if(first==NULL)
		return;
	Node* f=first->next;
	delete first;
	first=f;
}

void Queue::Print() const
{
	for(Node* z=first;z!=NULL;z=z->next)
		printf("%d",z->data);
		printf("\n");
}

void Queue::PrintFirstNode() const
{
	if(first==NULL)
		printf("The first element is not");
	else printf("The first element=%d\n",first->data);
}

[ViktorR]

Меня мучают сомнения и вот решил встрять.
1. Есть некоторое количество понятий для описания динамических структур:
- стек;
- очередь, дек;
- список;
- дерево.
Для каждого такого понятия есть перечень операций.
Стек - можно положить в стек и извлечь из стека.
Очередь - можно добавить элемент в хвост, удалить элемент с головы.
Дек - очередь у которой хвост и голова имеют одинаковый набор операций: добавить или удалить. Операции добавление/удаление элемента в середине не предусмотрены.
Список - добавление элемента в любое место или удаление из любого места. Элементы списка обладают таким понятием, как ключ.
Например, можно удалить элемен, ключь которого равен заданному или вставить элемент до/после элемента с заданным ключем.
И т.д.
Т.о. Ваша просьба не может быть просто так выполнена.
Сначала надо определить, с какой структурой работаете и, в Вашем случае, что такое середина очереди.


Как-то так ...

[Nekit9401]

Тогда извиняюсь, перепутал классы) Мне нужно вот это

Сообщение от ViktorR

Список - добавление элемента в любое место или удаление из любого места. Элементы списка обладают таким понятием, как ключ.
Например, можно удалить элемен, ключь которого равен заданному или вставить элемент до/после элемента с заданным ключем.

Ну в принципе, так как здесь класс "Очередь" построен на основе списка, то можно и для этого класса создать эти функции?)

[Nekit9401]

Сможет кто нибудь помочь?

[Abstraction]

Первое: невелика премудрость удалить элемент, на который мы указываем (что, собственно, с успехом продемонстрировано в DeleteFirstNode). Единственное - при удалении элемента из середины нужно "связать" предыдущий со следующим. "Наивное" решение: посчитать элементы в очереди

int count = 0;
for(Node* cur = first; cur != NULL; cur = cur->next) ++count;

...затем найти половину от этого количества...

if(count == 0) return; //Удалять нечего
int target = count/2;

...затем "дойти" до нужного элемента...

if(target == 0) DeleteFirstNode(); //Отдельный случай!
Node* previous; //Указатель на узел ПЕРЕД удаляемым
for(previous= first; target>1; --target, previous=previous->next) ; //Пустое тело цикла

...и, наконец, удалить тот элемент, который идёт следом за prevoius, аккуратно "связав" previous со следующим (это я предоставлю Вам сделать самостоятельно).
Вставка - аналогична, только после previous нужно вставить новый элемент.
Обратите внимание, что в последнем цикле нет проверок на previous==NULL: то, что мы не дойдём до конца списка, гарантируется условием на target.

В чём проблема с таким подходом? Ну, в том, что приходится проходить по списку дважды. Если список будет длинным, мероприятие может малость затянуться, а это нехорошо. Что можно сделать? Добавить инвариант класса: некоторое утверждение, которое верно для любого объекта класса, каким бы конструктором он ни был создан и какие бы методы для него ни вызывались. В настоящий момент у нас есть один инвариант класса: последовательность выражений first, first->next, first->next->next, ... представляет из себя последовательность корректных адресов структур Node, завершаемую NULL.
Чуть присмотримся к этому утверждению: оно верно после создания класса всеми нашими конструкторами и, если оно было верно для объекта перед вызовом любого из наших методов, то (к чему мы приложили усилия) оно верно и тогда, когда мы этот метод покидаем. Обратите внимание: в середине Queue::DeleteFirstNode() это утверждение нарушается (first указывает на удалённую область памяти), но, пока мы не решаем проблем с многопоточностью, это не страшно - "снаружи" наш инвариант сохраняется всегда.

Так вот, добавим-ка мы в класс ещё один инвариант: "член класса count содержит значение, равное количеству ненулевых адресов в последовательности first first->next, ...". Действие первое: добавляем член класса.

class Queue{
//...
private:
  size_t count; //size_t - стандартный тип для всякого рода "размеров". Можете использовать int, если так Вам проще
};

Действие второе: добавляем его инициализацию в конструкторы.

Queue::Queue()
{
	first=NULL;
        count = 0;
}

Queue::Queue(int x)
{
	first=new Node;
	first->data=x;
	first->next=NULL;

        count = 1;
}

Действие третье: добавляем его изменение в методы. Обратите внимание, что в DeleteFirstNode count не должна измениться, если очередь уже пуста.
Всё, теперь из нашего удаления среднего элемента подсчёт длины очереди можно выкинуть: мы её уже знаем.

[Nekit9401]

Спасибо, очень полезно, но я изначально не правильно сформулировал название темы, т.е. мне нужны функции удаляющие и добавляющие элемента в любое место списка, не обязательно в середину, например указать индекс элемента и функция его удаляет, тоже самое с добавлением, указать индекс элемента и перед / за ним вставить элемент. Только не могу понять как можно это реализовать, ведь тут нет индексов элементов как в массиве?