Вопрос о стеке связанного списка в отношении того, что стек пуст

Question

Я работаю над стеком связанных списков и кучей функций для него. В настоящее время я не понимаю, почему моя функция isEmpty работает неправильно. Я считаю, что то, как я это написал, имеет смысл. По своей природе, если Front равен Null, тогда список должен быть пустым, что означало бы, что «isEmpty» вернул бы false. Проблема, которую я имею, состоит в том, что моя программа говорит, что список всегда пуст, независимо от того, есть он на самом деле или нет. Я не уверен, в чем проблема. Любая помощь будет оценена.

struct node
{
    int data;
    node *next;
}*front = NULL, *rear = NULL, *p = NULL, *np = NULL;
void push(int x)
{
    np = new node;
    np->data = x;
    np->next = NULL;
    if(front == NULL)
    {
        front = rear = np;
        rear->next = NULL;
    }
    else
    {
        rear->next = np;
        rear = np;
        rear->next = NULL;
    }
}
int pop()
{
    int x;
    if (front == NULL)
    {
        cout<<"empty queue\n";
    }
    else
    {
        p = front;
        x = p->data;
        front = front->next;
        delete(p);
        return(x);
    }
}

int peek()
{
    int x;
    if (front == NULL)
    {
        cout<<"empty queue\n";
    }
    else
    {
        p = front;
        x = p->data;
        front = front->next;
        return(x);
    }
}

bool isEmpty()
{
    if (front == NULL)
    {
        return true;
    }
    else if (front != NULL)
    {
        return false;
    }
}

void Display()
{
cout << front;
}

int main()
{
    int n, c = 0, x;
    bool is_empty = isEmpty();
    cout<<"Enter the number of values to be pushed into queue\n";
    cin>>n;
    while (c < n)
    {
    cout<<"Enter the value to be entered into queue\n";
    cin>>x;
        push(x);
        c++;
    }
    cout<<endl<<"Pop value: ";

    if (front != NULL)
            cout<<pop()<<endl;

    cout<<endl<<"Peak value: ";

    if (front != NULL)
            cout<<peek()<<endl;

    if (is_empty == true)
    {
        cout<<endl<<"The list is empty";
    }
    else if (is_empty == false)
    {
        cout<<endl<<"The list is not empty";
    }


    cout << endl << "The current contents of the stack are: ";
while(front != NULL)
{
    Display();
    if(front == NULL)
        cout << "The stack is empty";
    break;
}
    getch();
}

Answer 1

Есть некоторые проблемы с вашим кодом.

Вы определили функцию isEmpty(), но на самом деле это не так.Вы объявили отдельную переменную is_empty, для которой вы устанавливаете возвращаемое значение isEmpty() один раз перед заполнением списка, и никогда не обновляете is_empty после внесения каких-либо изменений в список.Вот почему ваш код всегда сообщает, что список «пуст», даже если на самом деле это не так.Вам нужно избавиться от переменной is_empty и вызывать isEmpty() каждый раз, когда вам нужно проверить наличие пустых.

Кроме того, возвращаемые значения peek() и pop() являются неопределенными , если front НЕДЕЙСТВИТЕЛЕН.

И peek() извлекает узел front из списка.Только pop() должен делать это.

И pop() не проверяет, указывает ли rear на выталкиваемый узел.В этом случае вы не сбрасываете rear в NULL.

И вы не освобождаете узлы, оставшиеся в списке, перед выходом из программы.

Вместо этого попробуйте что-то подобное:

#include <iostream>
#include <limits>

struct node
{
    int data;
    node *next;

    node(int value): data(value), next(NULL) {}
};

node *front = NULL;
node *rear = NULL;

void push(int x)
{
    node **np = (rear) ? &(rear->next) : &front;
    *np = new node(x);
    rear = *np;
}

int peek()
{
    if (front)
        return front->data;
    return -1;
}

int pop()
{
    int x = peek();

    if (front)
    {
        node *p = front;
        front = front->next;
        if (p == rear) rear = NULL;
        delete p;
    }

    return x;
}

bool isEmpty()
{
    return !front;
}

void clear()
{
    while (front)
    {
        node *p = front;
        front = front->next;
        delete p;
    }
    rear = NULL;
}

void display()
{
    node *n = front;
    if (n)
    {
        cout << n->data;
        while (n = n->next)
            cout << ' ' << n->data;
    }
}

int askForNumber(const char *prompt)
{
    int n;
    cout << prompt << ": ";
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    return n;
}

int main()
{
    int n, x;

    n = askForNumber("Enter the number of values to be pushed into queue");

    for(int c = 0; c < n; ++c)
    {
        x = askForNumber("Enter the value to be entered into queue");
        push(x);
    }
    cout << endl;

    cout << "Pop value: ";
    if (!isEmpty())
        cout << pop();
    else
        cout << "empty queue";
    cout << endl;

    cout << "Peak value: ";
    if (!isEmpty())
        cout << peek();
    else
        cout << "empty queue";
    cout << endl;

    if (isEmpty())
        cout << "The list is empty";
    else
        cout << "The list is not empty";
    cout << endl;

    cout << "The current contents of the stack are:" << endl;
    display();
    cout << endl;

    clear();

    cin.get();
    return 0;
}