Объясните пожалуйста смысл строк(указатели)?

Question

[sddvxd]

Здравствуйте! Делаю класс очереди по примеру

//head.h

//Any classes....
class Queue{
private:
  struct Node
  {
    String str; //Мой класс
    Node *next;
  };
  enum{
    Q_SIZE = 10
  };
  int items;
  const int qsize;
  Node *front,*rear;
public:
  Queue(int);
  bool isfull()const;
  bool isempty()const;
  bool enqueue(const String&);
};

Объект может добавлять в очередь, проверять на заполненность и пустоту

//func.cpp

//Any methods...
Queue::Queue(int qs = Q_SIZE):qsize(qs),front(nullptr),rear(nullptr),items(0){}
bool Queue::isfull()const{
  if(items==qsize)return true;
  else return false;
}
bool Queue::isempty()const{
  if(items==0)return true;
  else return false;
}
bool Queue::enqueue(const String &st){
  if(isfull())return false;
  Node *add = new Node;
  add->str = st;
  add->next = nullptr;
  items++;
  if(front==nullptr)front = add;
  else rear->next = add;
  rear = add;
  cout<<st<<" posted in "<<add<<" end has "<<items<<" position\n";
  return true;
}

Мне не совсем понятно, зачем сначала в поле структуры записывать адрес следующей структуры, а затем присваивать адрес новой структуры в конец очереди

if(front==nullptr)front = add;
  else rear->next = add;
  rear = add;

Таких "ужасных" отступов в книге нет. Я по своему писал

Answer 1

[JaxxDexx]

Очень просто! Когда вы добавляете новый элемент в свою очередь, rear указывает на ваш последний элемент в очереди. Его next установлен в nullptr, поэтому чтобы не потерять связь между последним элементом в очереди и тем, который вы добавляете, вы устанавливаете указатель rear->next на адрес нового элемента. А после этого всей своей очереди говорите, что теперь новый элемент имеет адрес add (rear = add).

Comments

[sddvxd]

А зачем устанавливать next если следующая строка все равно бесследно удалит его?

rear = add;

тут же мы присваиваем указатель структуры, а значит утрачиваем доступ к старому Node

[JaxxDexx]

sddvxd, представьте себе пустую комнату. В него заходит первый человек. Т.к. там никого не было, он знает что он первый (if(front==nullptr)front = add;). Далее заходит следующий ,спрашивает кто последний, и говорит ему свое Имя (rear->next = add;). И после этого становится последним (rear = add). И так далее, новый зашедший спрашивает кто последний, говорит ему свое имя и становится последним. Первый знает что он первый ,последний знает что он последний. А те кто посередине, знают только имя следующего за ними. Таким образом можно обойти всю очередь. Спросив, начиная с первого, как имя того кто за ним. И при этом не важно, будут ли они все стоять в ряд или хаотично в комнате.

[Therapyx]

sddvxd, в дополнение посоветую посмотреть структуру "List". На ютубе очень много визуальных и очень понятных видео про все такие связи в структурах данных. Например https://www.youtube.com/watch?v=o5wJkJJpKtM
Тоже самое можно найти и для Queue, хотя принцип очень схож. Хотя вот и на кью первая ссылка... https://www.youtube.com/watch?v=okr-XE8yTO8

[sddvxd]

JaxxDexx, , Спасибо за доступное объяснение концепции. Я правда был озадачен с технической точки зрения, комментарий оставил под ответом пользователя Mercury13

[JaxxDexx]

sddvxd, поймите, элемент который был последний, а потом им перестал быть, никуда не теряется, он все так же находится в памяти, а адрес его местонахождения знает предудущий элемент. А сам этот элемент знает адрес следующего. Поэтому мы зная адрес самого первого элемента, может пройтись по всем элементам, просто узнавая какой элемент следует за ними.

[sddvxd]

JaxxDexx, спасибо большое. Долго же до меня доходило

Answer 2

[Mercury13]

Перед нами структура данных под названием «односвязный список». У каждого элемента ссылка на следующий, у всей очереди ссылка на голову (front) и иногда на хвост (rear).

Для чего нужна проверка на заполненность — непонятно, ведь ёмкость списка не ограничена и единственный способ убедиться, что очередь полна — завести память под новый элемент. Выпадает авария std::bad_alloc — значит, памяти не хватило. Если только для каких-то прикладных нужд: так, в StarCraft очередь на строительство пять юнитов, и точка. (Есть другой тип очереди, т.н. циклическая очередь — вон там ограничено.)

Как работает enqueue: создаём новый элемент, следующий за ним — nullptr. Если очередь пуста, направляем на него front и rear. В противном случае пристраиваем его за тем, на который «смотрит» rear, и перенаправляем rear. Таким образом, «направляем rear» можно вынести за скобки, а остальные два исполнить в зависимости от пустоты очереди.

Comments

[sddvxd]

Большое спасибо за пояснение, неясным для меня остается одно:

else rear->next = add; //Тут мы присваиваем next адрес Node если элемент не первый
rear = add; //Тут мы просто меняем указатель на новую ноду

Получается мы просто "избавляемся" от предыдущего элемента если таковой есть, но при этом манипулируем одним из его полей next

Ведь теперь если я обращусь к rear->next то получу nullptr, ведь это последний элемент, куда же тогда теряется прошлая нода?
Или я все запутал и указатель на rear просто является частью прошлого элемента, а тут мы просто указываем новый конец

[Mercury13]

sddvxd,

else rear->next = add; // Пристраиваем за тем, на который «смотрит» rear
rear = add;   // Перенаправляем rear (нужно в обеих ветвях и вынесено за скобки)

Ведь теперь если я обращусь к rear->next то получу nullptr, ведь это последний элемент, куда же тогда теряется прошлая нода?

Обрати внимание на порядок, это важно. Сначала пристроить за тем элементом, куда смотрит rear, ПОТОМ переприсвоить rear.

[Mercury13]

sddvxd, и rear->next = чему-то там — это мы переприсваиваем указатель rear->next, и никто не думает его разыменовывать.