Реализация стека в C ++ с использованием связанного списка

Question

Итак, я пытаюсь реализовать стек, используя связанный список и классы.Сейчас у меня есть 6 разных файлов: node.h, node.cpp, LL.h, LL.cpp, Stack.h и Stack.cpp.Я хочу заполнить файлы Stack.h и Stack.cpp, чтобы они работали как надо.Я уже реализовал функции связанного списка, и они работают как надо.Вот код:

node.h:

// node.h

class node { // node class used in the LL (linked list) class
    private:
        node * next; // Pointer to next node of an LL
        int data;    // integer data stored in this node

    public:
        node(int x, node * n);  // Constructor
        ~node();                // Destructor
        void set_data(int x);   // Change the data of this node
        void set_next(node * n);// Change the next pointer of this node
        int get_data();         // Access the data of this node
        node * get_next();      // Access the next pointer of this node
};  

LL.h:

// LL.h
#include "node.h"

// Linked list class, used in the Stack class
class LL {
    private:
        node * head; // pointer to first node
        node * tail; // pointer to last node

    public:
        LL(); // Constructor
        ~LL(); // Destructor
        void prepend(int value); // add a node to the beginning of the LL
        int removeHead();        // remove the first node of the LL
        void print();            // print the elements of the LL
    node * get_head();       // access the pointer to the first node of the LL
};

Stack.h:

// Stack.h
#include "LL.h"

class Stack {
private:
    LL_t intlist;

public:

    Stack();    // Constructor
    ~Stack();       // Destructor

    void push(int value);
    int pop();      
    int isEmpty();
    void print();
};

И, наконец, Stack.cpp:

// Stack.cpp
#include "Stack.h"
#include <stdio.h>

Stack::Stack() {
    head= NULL;
    tail= NULL;
}

Stack::~Stack() {
    delete intlist;
}

int Stack::isEmpty() {
    return (head==NULL);
}

void Stack::push(int value) {

    head= value;
}

int Stack::pop() {

    if ( !isEmpty() ) {
        int temp= tail->get_data();
        delete tail;
        return temp;    
    }
    return -1;
}

У меня проблемы с компиляцией.В нем говорится, что get_data () не определена, а "голова" и "хвост" не определены, хотя у меня есть "#include" LL.h "" в Stack.h и в LL.h, у меня есть "#include" node.h"", так что они все строят друг на друга, так что это должно работать правильно?Я хочу, чтобы он компилировался, чтобы я мог видеть, правильно ли я реализую Stack.h и Stack.cpp.Вы видите какие-либо проблемы с тем, как я их реализую?Если да, можете ли вы указать на них?Кроме того, есть идеи, почему я получаю эти проблемы компиляции?Любая помощь приветствуется!

Answer 1

Давайте посмотрим на ваши актуальные вопросы

Stack::Stack() {
    head= NULL;
    tail= NULL;
}

приводит к ошибке "head" and "tail" is undefined. Теперь посмотрите на файлы заголовков, где объявления head и tail? Ответ: в классе LL, а не в классе Stack. Класс LL несет ответственность за инициализацию head и tail, что он делает в конструкторе класса LL по умолчанию. Итак, ваш Stack конструктор должен выглядеть так

Stack::Stack() {
}

Всякий раз, когда у вас есть конструктор для класса, который содержит другой класс, будет вызываться конструктор для другого класса. В случае Stack конструктор по умолчанию для LL вызывается неявно, и это инициализирует head и tail для вас. Вам не нужно ничего делать.

Теперь давайте рассмотрим еще несколько ваших реализаций.

Stack::~Stack() {
    delete intlist;
}

intList не является указателем, поэтому его нельзя удалить. Понятно, что вы пытаетесь вызвать деструктор для вашего списка, но, как и конструктор, это происходит автоматически. Ваш деструктор должен выглядеть так

Stack::~Stack() {
}

Или вы можете (вероятно, должны) просто полностью удалить его.

Переезд

int Stack::isEmpty() {
    return (head==NULL);
}

Опять вы пытаетесь получить доступ к head там, где это недоступно. Ваш класс Stack имеет объект LL intlist, и это то, что он должен использовать, поэтому (например)

int Stack::isEmpty() {
    return intlist.get_head() == NULL;
}

Что-то здесь

void Stack::push(int value) {
    head= value;
}

должно быть

void Stack::push(int value) {
    intlist.prepend(value);
}

Используйте объект, который есть в стеке (intlist), а не внутренние объекты других объектов.

Я оставлю тебя, разберись с остальными. Но вы должны понимать разделение обязанностей, которые существуют в дизайне вашего класса. Класс Stack не должен (и не может) касаться внутренних элементов класса LL. Все, что нужно выполнить Stack, должно выполняться с открытым интерфейсом класса LL. Если нет, то класс LL необходимо изменить.

Также обратите внимание, что ваша реализация pop не просто неверна в исполнении, она неверна в концепции. Pop должен удалить голову списка, а не хвост. Стек - это список LIFO (последний пришел, первый вышел), поэтому pop удаляет последний добавленный элемент. Теперь, глядя на класс LL, есть метод removeHead (подсказка, подсказка).