C 程序中的堆栈。弹出操作不起作用

Question

伙计们，这个程序有什么问题。我在弹出操作时遇到问题，即使在堆栈为空后它也会显示一个额外的值。 ??

void initstack (struct stack * p, int maxSize) 

void push (struct stack * p, int item) 

int pop (struct stack * p) 

void display (struct stack p) 

 struct stack

{

   int * a;

   int top;

   int maxSize;

};

注意：必须使用d以上结构和函数..

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct stack {
    int * a;
    int top;
    int maxSize;
};
void initstack(struct stack * p, int maxSize);
void push(struct stack * p, int item);
int pop(struct stack * p);
void display(struct stack p);
int StackIsEmpty(struct stack * p);
int StackIsFull(struct stack * p);
void printMenu();

int main()  {
    struct stack p;
    int data,ch, data1, m;
    printf("Enter the maximum size of the stack\n");
    scanf("%d",&m);
    initstack(&p,m);
    do {
    printMenu();    
    printf("Enter your choice\n");
    scanf("%d",&ch);
    switch(ch) {
      case 1:
        printf("Enter the element to be pushed\n");
        scanf("%d",&data);
        push(&p, data);
        break;
      case 2:
        data1 = pop(&p);
        if(data1 != -1000)
        printf("The popped element is %d\n",data1);
        break;
      case 3:
        printf("The contents of the stack are");
        display(p);
        printf("\n");
        break;
      default:
        exit(0);
    }
    } while(1);
    return 0;
}

void printMenu()
{
    printf("Choice 1 : Push\n");
    printf("Choice 2 : Pop\n");
    printf("Choice 3 : Display\n");
    printf("Any other choice : Exit\n");
}

void initstack(struct stack * p, int maxSize) {
    int *newContents;
  newContents=(int *)malloc(sizeof(int)*maxSize);
  p->a=newContents;
  p->maxSize=maxSize;
  p->top=-1; 
}

void push(struct stack * p, int item) {
    if(StackIsFull(p))
    {
      printf("Stack is full\n");
    }
  p->a[++p->top]=item;
}

void display(struct stack p) {
  int i;
  struct stack *b=&p;
  if(StackIsEmpty(b))
    printf(" {}");
  for(i=0;i<b->top;i++)
  {
    printf(" %d",b->a[i]);
  }
}

int pop(struct stack * p) {
    if(StackIsEmpty(p))
    {
      printf("Stack is empty\n");
      return -1000;
    }
  else
    return p->a[--p->top];
}

int StackIsEmpty(struct stack *p)
{
  return p->top == -1;          //p->top==-1;
}

int StackIsFull(struct stack *p)
{
  return p->top >= p->maxSize-1;
}

Answer 1

你的显示逻辑有问题。它有一个差一错误并跳过最顶层的元素。

Answer 2

return p->a[--p->top];

在这部分我认为你应该先

int result =  p->a[p->top];

然后

p->top --;
return result;

我遇到了同样的问题，这对我有帮助。

Answer 3

推测问题与推送和弹出功能有关。两者都使用预增量，因此您推送的最后一项不是您弹出的第一项。

您的 push 执行：首先递增 top，然后将值存储在 a[top] 中。所以 top 指向新推送的元素。

您的 pop 执行：首先递减 top，然后检索 a[top] 处的值。检索到的值不是最后推送的值，而是倒数第二个。 top 一直指向这个相同的值。

我的建议：保持 push 不变，并将 pop 更改为：

int pop(struct stack * p) {
    if(StackIsEmpty(p))
    {
      printf("Stack is empty\n");
      return -1000;
    }
  else
    return p->a[p->top--]; /* post-increment!! */
}

因此，push 将使顶部指向最后推送的值。 pop 将检索此值，然后递减 top，使其指向下一个要检索的值。

Answer 4

让我们看看你的 push 和 pop 操作：

p->a[++p->top]=item; // push
p->a[--p->top];      // pop

让我们假设堆栈是空的并且top是-1。当你进行推送时，你将 top 递增到 0 并将你的元素写入 p->a[0]。弹出该元素时，首先将 top 递减回 -1，然后尝试访问元素 p->a[-1]。

这是个问题。您不仅会弹出错误的元素，还会访问数组范围之外的元素并调用未定义的行为。

您需要在访问您想要的元素后更改堆栈指针，如下所示：

p->a[++p->top] = item; // push
item = p->a[p->top--]; // pop

对于基于数组的堆栈，堆栈增长实际上更自然一点 "downwards"，如下所示：

p->top = p->maxSize = maxSize; // init

if ( p->top )            // p->top != 0 means room left on the stack
  p->a[--p->top] = item; // push

if ( p->top < p->maxSize ) // p->top < p->maxSize means elements left on stack 
  return p->a[p->top++];   // pop

这样，您就不会运行访问数组范围之外的元素的风险。 p->top 将始终介于 0 和 maxSize - 1 之间。

最后，风格说明：

您不需要转换 malloc 的结果；它只会增加视觉混乱，并且在某些情况下会抑制有用的诊断。您可以通过简单地编写来清理它：

 /**
  * Whitespace is your friend.  Use it.
  */
 newContents = malloc( sizeof *newContents * maxSize );

sizeof *newContents等同于sizeof (int)；这样，如果您决定更改堆栈数组的类型，则不必担心更改 malloc 调用本身。省去一些维护麻烦，阅读起来更容易一些。

编辑

以下是导致您头痛的部分原因：

void push(struct stack * p, int item) {
    if(StackIsFull(p))
    {
      printf("Stack is full\n");
    }
    p->a[++p->top]=item; // DANGER WILL ROBINSON!
}

如果堆栈已满，您会打印一条警告，然后您无论如何都会压入该元素。

你需要一个 else 分支

void push(struct stack * p, int item) 
{
  if(StackIsFull(p))
  {
    printf("Stack is full\n");
  }
  <em><strong>else
  {
    </strong></em>p->a[++p->top]=item;<em><strong>
  }</strong></em>
}

Answer 5

谢谢大家，我修好了..工作正常。感谢您的所有建议。

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct stack {
    int * a;
    int top;
    int maxSize;
};
void initstack(struct stack * p, int maxSize);
void push(struct stack * p, int item);
int pop(struct stack * p);
void display(struct stack p);
int StackIsEmpty(struct stack * p);
int StackIsFull(struct stack * p);
void printMenu();

int main()  {
    struct stack p;
    int data,ch, data1, m;
    printf("Enter the maximum size of the stack\n");
    scanf("%d",&m);
    initstack(&p,m);
    do {
    printMenu();    
    printf("Enter your choice\n");
    scanf("%d",&ch);
    switch(ch) {
      case 1:
        printf("Enter the element to be pushed\n");
        scanf("%d",&data);
        push(&p, data);
        break;
      case 2:
        data1 = pop(&p);
        if(data1 != -1000)
        printf("The popped element is %d\n",data1);
        break;
      case 3:
        printf("The contents of the stack are");
        display(p);
        printf("\n");
        break;
      default:
        exit(0);
    }
    } while(1);
    return 0;
}

void printMenu()
{
    printf("Choice 1 : Push\n");
    printf("Choice 2 : Pop\n");
    printf("Choice 3 : Display\n");
    printf("Any other choice : Exit\n");
}

void initstack(struct stack * p, int maxSize) {
    int *newContents;
  newContents=malloc(sizeof(int)*maxSize);
  p->a=newContents;
  p->maxSize=maxSize;
  p->top=-1; 
}

void push(struct stack * p, int item) {
    if(StackIsFull(p))
    {
      printf("Stack is full\n");
    }
    else
    {
    p->a[++p->top]=item;  //FIXED LINE, ELSE BLOCK ADDED
    }
}

void display(struct stack p) {
  int i;
  struct stack *b=&p;
  if(StackIsEmpty(b))
    printf(" {}");
  for(i=0;i<=b->top;i++)   //FIXED PREVIOUSLY for(i=0;i<b->top;i++)
  {
    printf(" %d",b->a[i]);
  }
}

int pop(struct stack * p) {
    if(StackIsEmpty(p))
    {
      printf("Stack is empty\n");
      return -1000;
    }
  else
    return p->a[p->top--];     //FIXED PREVIOUSLY p->a[--p->top];
}

int StackIsEmpty(struct stack *p)
{
  return p->top < 0;          //FIXED PREVIOUSLY p->top==-1;
}

int StackIsFull(struct stack *p)
{
  return p->top >= p->maxSize-1;
}

C 程序中的堆栈。弹出操作不起作用

STACK in c program. pop operation not working

c

stack