CODEWITHSUNDEEP
cstack
Gary Ridgway
Gary Ridgway

Reputation: 69

Same value popped regardless of pushed values in a stack

I am writing a simple stack program (the main function just determines what the user is asking you to do).

However, it has "a bug", where it just continues to "pop" the same value off (It's not actually popping anything off).

Am I using structures and pointers incorrectly? Or is it a not-so-obvious coding mistake?

#include <stdio.h>

struct node {
    int data;
    struct node *next;
    struct node *prev;
} first;

void push(int);
void pop();

int main(void)
{
    int command = 0;
    
    while (command != 3)
    {
        printf("Enter your choice:\n1) Push integer\n2) Pop Integer\n3) Quit.\n");
        scanf("%d",&command);
        if (command == 1)
        {
            // push
            int num;
            scanf("%d",&num);
            push(num);
        }
        else
        {
            if (command == 2)
            {
                pop();
            }
            else
            {
                if (command != 3)
                {
                    printf("Command not understood.\n");
                }
            }
        }
    }

    return 0;
}

void push (int x)
{
    struct node newNode;
    newNode.data = x;
    newNode.prev = NULL;
    newNode.next = &first;
    first = newNode;
    printf("%d was pushed onto the stack.\n", first.data);
}

void pop()
{
    if (first.data == '\0')
    {
        printf("Error: Stack Empty.\n");
        return; 
    }
    printf("%d was popped off the stack.\n", first.data);
    first = *(first.next);
    first.prev = NULL;
}

Upvotes: 3

Views: 16045

Answers (8)

ruakh
ruakh

Reputation: 183311

The problem is that first is a single global node, and it's the only node you ever have (aside from a temporary local node inside your call to push).

This line:

first = newNode;

just copies the contents of newNode over into first; and since newNode.next is pointing to first, this means that now first.next is pointing to first, so you have a single-element circular linked list.

Similarly, this line:

first = *(first.next);

just copies the contents of *(first.next) over into first; which is a no-op, since (due to the above), *(first.next) is first.

To solve this problem, you actually need to dynamically create nodes, using malloc (and free). And your global first variable should be a pointer — a node * — that always points to the top element of the stack. (Better yet, your push and pop functions should take first as an argument, rather than having this as a global variable. There's no need for these functions to only allow a single stack to exist.)

Upvotes: 5

benzado
benzado

Reputation: 84338

When you have to manage memory yourself, as C requires you to do, you need to know the difference between areas of memory known as the stack and the heap. (This "stack" is slightly different from the data structure you are creating in your program.)

Your push() function is creating a new node on the stack; when the function exits, the stack is popped and the memory occupied by your new node is up for grabs. The fact that you see values you entered is due to the fact that your program is very simple. If it was calling other functions that did other things they would almost certainly overwrite that part of the stack and when you called pop(), you would see garbage.

As others have indicated, you need to use the functions malloc() and free(), which give you memory from the heap instead of the stack.

Upvotes: 1

Kyokook Hwang
Kyokook Hwang

Reputation: 2762

If you want to make a stack with a linked list, make first variable as a pointer. Then, when you push a new node to the stack, make a new node by allocating on the heap memory using malloc(). That is if you intend to use it to point to the top of the stack.

In your code, first variable is overwritten by a new node since it is not a pointer variable, but a value variable. That results in the loss of the top node of the stack.

Upvotes: 1

surender8388
surender8388

Reputation: 474

  1. first should be a pointer. Change it to struct node *first;

  2. in main, initialize first = NULL;

  3. change your push/pop operations as below:

void push (int x)
{
    struct node *newNode;// It should be a pointer
    newNode = (struct node *)malloc(sizeof(struct node));
    newNode->data = x;
    //newNode.prev = NULL; // You don't need this
    newNode->next = first;
    first = newNode;
    printf("%d was pushed onto the stack.\n", first->data);
}

void pop()
{
    struct node *prevPtr;
    //if (first.data == '\0')
    if (first == NULL) // check if stack is empty
    {
        printf("Error: Stack Empty.\n");
        return; 
    }

    printf("%d was popped off the stack.\n", first->data);
    prevPtr = first;
    first = first->next;

    free(prevPtr);
}

Upvotes: 5

Staunton Allen
Staunton Allen

Reputation: 77

void pop()
{
    struct node *prevPtr;
    //if (first.data == '\0')
    if (first == NULL)
    {
        printf("Error: Stack Empty.\n");
        return; 
    }

    printf("%d was popped off the stack.\n", first->data);
    prevPtr = first;
    first = first->next;

    free(prevPtr);
}

Upvotes: 1

abhishek agrawal
abhishek agrawal

Reputation: 35

#include<stdio.h>

#define max 10

int stack[max],top=-1,size=0;

void push()
{
    if(top==(max-1))
    {
        printf("stack full\n");
    }
    else
    {
        top++;
        printf("enter the value which you want to insert\n");
        scanf("%d",&stack[top]);
    }
}

void pop()
{
    int str;

    if(top==-1)
    {
        printf("stack empty\n");
    }
    else
    {
        str=stack[top];
        top--;
        printf("the removed element is %d\n",str);
    }
}

void display()
{
    int i;

    for(i=0;i<top;i++)
    {
        printf("%d\n",stack[i]);
    }
}

void main()
{ 
    int enter,x;
    do
    {
        printf("enter 1 for push the element in the array\n");
        printf("enter 2 for pop the element in the array\n");
        printf("enter 3 for display the element in the array\n");
        scanf("%d",&enter);

        switch(enter)
        {
            case 1:push();
                break;
            case 2:pop();
                break;
            case 3:display();
                break;
            default:
                printf("invalid syntax");
        }
        printf("for continue press 0\n");
        scanf("%d",&x);
    }
    while(x==0);
}

Upvotes: -2

20-BCA-039 Rishabh Gupta
20-BCA-039 Rishabh Gupta

Reputation: 1

#include <stdio.h>
#include <stdlib.h>

struct stack {
  int size;
  int top;
  int *arr;
};

int isEmpty(struct stack* ptr){
    if(ptr->top == -1){
        return 1;
    }
    else{
         return 0;
    }
}

int isFull(struct stack* ptr){
    if(ptr->top == ptr->size-1){
        return 1;
    }
    else{
         return 0;
    }
}

int display(struct stack *s){
    for(int i = s->top; i >= 0; i--){
        printf("%d\n", s->arr[i]);
    }
}

int main(){
    struct stack *s = (struct stack*)malloc(sizeof(struct stack));
    s->size = 80;
    s->top = -1;
    s->arr = (int *)malloc(s->size * sizeof(int));
    
    s->top ++;
    s->arr[s->top] = 1;
    s->top ++;
    s->arr[s->top] = 2;
    s->top ++;
    s->arr[s->top] = 3;
    
    display(s);
    // if(isEmpty(s)){
    //     printf("Stack Empty!");
    // }
    // else{
    //     printf("Stack not empty!");
    // }
    
    
    
}

Upvotes: 0

Jessica
Jessica

Reputation: 6957

What's the value of &first? Hint, it's always the same since first is statically allocated. Even if you change the contents of the structure, the address won't change. This might tell you why there's a bug in push. You'll need to use malloc and free if you are going to have a structure of varying size.

Upvotes: 2

Related Questions