Реверсирование стека реализовано с помощью связанного списка

Question

Это очень простая программа, которая реализует стек, используя связанный список. Просьба помочь мне разобраться в логической ошибке, которая заставляет программу сбой работать.

class LLStack { 
    public: 
     struct Node { 
      int data; 
      Node* next; 
      Node(int n) { 
       data = n; 
       next = 0; 
      } 
      Node(int n, Node* node) { 
       data = n; 
       next = node; 
      } 
     }; 
     LLStack(); 
     LLStack(const LLStack&); 
     LLStack& operator = (const LLStack&); 
     ~LLStack(); 
     void push(int); 
     int pop(); 
     int top(); 
     bool isEmpty(); 
     void flush(); 

    private: 
     Node* head; 

}; 

LLStack::LLStack() { 
    head = 0; 
} 

LLStack::LLStack(const LLStack& s) { 
    head = new Node(NULL); 
    head->data = s.head->data; 
    head->next = new Node(*(s.head->next)); 
} 

LLStack::~LLStack() { 
    this->flush(); 
} 

LLStack& LLStack::operator = (const LLStack& s) { 
    this->head = new Node(NULL); 
    this->head->data = s.head->data; 
    this->head->next = new Node(*(s.head->next)); 
    return *this; 
} 

void LLStack::push(int x) { 
    if (head == 0) head = new Node(x); 
    else { 
     Node* temp = new Node(x, head); 
     head = temp; 
    } 
} 

int LLStack::pop() { 
    if (head == 0) { 
     cout << "\n\nNo elements to pop\n\n"; 
     return -1; 
    } 
    else { 
     Node* temp = head; 
     int n = temp->data; 
     head = temp->next; 
     delete temp; 
     return n; 
    } 
} 

int LLStack::top() { 
    if (head == 0) { 
     cout << "\n\nNo elements in the stack\n\n"; 
     return -1; 
    } 
    else { 
     return head->data; 
    } 
} 

bool LLStack::isEmpty() { 
    return (head == 0); 
} 

void LLStack::flush() { 

    if (head == 0) { 
     cout << "\n\nNo elements in the Stack to flush\n\n"; 
     return; 
    } 
    cout << "\n\nFlushing the Stack: "; 
    Node* temp = 0; 
    while (head != 0) { 
     temp = head; 
     cout << temp->data << " "; 
     head = head->next; 
     delete temp; 
    } 
    cout << endl << endl; 
} 

Это смутьян фикция:

void reverseStack(LLStack& s1) { 
    LLStack s2; 
    while (!s1.isEmpty()) { 
     s2.push(s1.pop()); 
    } 
    s1 = s2; 
} 

int main() { 

    LLStack s; 
    s.push(1); 
    s.push(2); 
    s.push(3); 
    s.push(4); 
    s.push(5); 
    reverseStack(s); 
    cout << "\n\nFlushing s:\n"; 
    s.flush(); 
    system("pause"); 
    return 0; 
} 

Я выполнил мой собственный конструктор копирования и оператор копирующего присваивания. Я не понимаю, почему он сработает при запуске. При промывке отображает значения мусора перед сбоем.

Answer 1

Проблема заключается в вашем операторе присваивания копии. Рассмотрим:

void reverseStack(LLStack& s1) { 
    LLStack s2; 
    while (!s1.isEmpty()) { 
     s2.push(s1.pop()); 
    } 
    s1 = s2; 
} 

Все работает прекрасно, пока вы не вернетесь из функции, в которой точка деструктор s2 называется. Деструктор вызывает flush(), который удаляет все элементы стека s2. В вашем операторе присваивания копии (и при создании этого экземпляра) вы создаете два узла: head и head->next; остальные узлы разделяются между двумя стеками, поэтому после удаления s2s1.head->next->next указывает на удаленный узел, но вы по-прежнему пытаетесь получить к нему доступ.

Раствор должен иметь оператор присваивания копии (и конструктор копирования) создать надлежащую глубокую копию стека, а не только первые два элемента, как это (также заботится о себе присваивание):

LLStack& LLStack::operator=(const LLStack& s) { 
    if (this==&s) return *this; // self assignment 
    flush(); // avoid memory leak 
    head = new Node(*s.head); 
    Node* s_ptr = s.head; 
    Node* t_ptr = head; 
    while (s_ptr->next) { 
     t_ptr->next = new Node(*s_ptr->next); 
     s_ptr = s_ptr->next; 
     t_ptr = t_ptr->next; 
    } 
    return *this; 
} 

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