关于堆栈为空的链表堆栈问题

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 queuen";
}
else
{
p = front;
x = p->data;
front = front->next;
delete(p);
return(x);
}
}
int peek()
{
int x;
if (front == NULL)
{
cout<<"empty queuen";
}
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 queuen";
cin>>n;
while (c < n)
{
cout<<"Enter the value to be entered into queuen";
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()。

此外，如果front为NULL，则peek()和pop()的返回值不确定。

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;
}