Вопрос реализации связанных списков

Question

Я пытаюсь создать стек, используя базовую структуру связанного списка.

Возможно, я ошибаюсь, но у меня проблемы с функцией remove ().

int Stack::remove(){  
  node* victim = new node;  
  int popped;  
  popped = top->element;  
  victim = top;
  top = victim->next;  
  delete victim;  
  return popped;  
}

Я получаю glibc dectecting

двойное освобождение или коррупция (нет);

Поскольку я выделяю новую память жертве, мне не нужно удалять жертву или мне не о чем беспокоиться?

Answer 1

Стек очень похож на набор посуды, которую моют и ставят друг на друга. Это первый вход, последний выход (тип данных FILO). То есть, если ваш стек читается в 2, 7, 8, он будет выглядеть так:

8

7

2

То есть сначала 2 помещается в стек, затем 7, а затем 8. Если вы хотите удалить или вытолкнуть стек, вам нужно переместить головку указателя. Ваш код выглядит немного странно для меня ...

int Stack::remove()
 {
  int datum;      //to store the popped value
  node* temp=head;  //assign pointer to head of list
  datum = temp->data; //grab the data value stored at the head (or temp since they carry same reference)
  head = temp->next; //move the head pointer (in our example now it points to 7)
  delete temp;
  return datum;
 }

Answer 2

Вам не нужно выделять узел для victim. Просто присвойте ему верх стека и, если это не null, установите top на его указатель next, получите значение из victim, а затем освободите victim.

На самом деле это не повреждение, а утечка памяти - вы выделяете узел, а затем переопределяете этот указатель на victim = top;, теряя, таким образом, только что выделенную память.

Answer 3

Нет смысла выделять кучу памяти в методе remove(), как вы делаете с victim. То, что вы хотите:

int Stack::remove(){  
  node* new_top = top->next;
  int popped = top->element;

  delete top;  
  top = new_top;

  return popped;  
}