Wrong output when popping from the stack

Question

I have made a program using stacks, but the output which i get is kind of wrong. The output i get, has the answer i need and also has 2 values which are not expected.

Here is what i have done:

#include <stdio.h>
#include<malloc.h>
#define MAX 180

struct cakes{
    int spongecake;
    int meringue;
    int chocalate;
    int red_velvet;
    struct cakes *next;
};

struct stack{
    int top;
    int cake[10];
};

int isFull(struct stack *);
int isEmpty(struct stack *);
void push(struct stack *,int);
int pop(struct stack *);

void order_out(struct cakes *);

main()
{
    struct cakes *head;

    head=(struct cakes *)malloc(sizeof(struct cakes));
    cake_order(head); //this is a seperate function, it works perfectly.
    head->next=(struct cakes *)malloc(sizeof(struct cakes));
    order_out(head->next);
}

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

void push(struct stack *sptr,int x)
{
    if(!isFull(sptr))
    {
        sptr->top++;
        sptr->cake[sptr->top]=x;
    }
}   

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

}

int pop(struct stack *sptr)
{
    int ret=NULL;
    if(!isEmpty(sptr))
    {
        ret=sptr->cake[sptr->top];
        sptr->top--;
        return ret;
    }
}

void order_out(struct cakes *theorder)
{
    struct stack s;
    s.top=-1;
    int k=0;
    int i=0;
    int p=0;
    int r=0;    
    int value1,value2;
    int items[10];    

    theorder->spongecake=1;
    theorder->meringue=2;
    theorder->chocalate=3;
    theorder->red_velvet=4;

    for(;i<10;i++)
    {
        push(&s,theorder->spongecake);

        push(&s,theorder->meringue);
        push(&s,theorder->chocalate);
        push(&s,theorder->red_velvet);
    }

    while(!isEmpty(&s))
    {
        printf("\n%d",pop(&s));
    }
}

The output which I get is as follows :

As you can see it prints 2 and 1 first. What seems to be the problem?

Answer 1

There is no problem with stack except the pop implementation where return value NULL is returned when stack is empty. Better return an invalid number as convention(like 0, -1, -999) left to your choice.

As you are restricting the stack size to 10, only 10 values are being inserted. So while inserting only following are inserted 1 2 3 4 1 2 3 4 1 2 and are popped inorder.

Answer 2

In my opinion your program is working as follows,

The following loop tries to insert 40 values,

for(;i<10;i++)
{
   push(&s,theorder->spongecake);
   push(&s,theorder->meringue);
   push(&s,theorder->chocalate);
   push(&s,theorder->red_velvet);
}

But only 10 values are inserted because of your statement if(q->top==10-1) in your isFull() function. i.e the counter counts 10 elements from 0 to 9. The order in which the elements are pushed is as follows 1, 2, 3, 4, 1, 2, 3, 4, 1, 2. These elements when popped gives you the sequence 2, 1, 4, 3, 2, 1, 4, 3, 2, 1. Thus the output you obtain is actually correct or at least not an aberration.

There are a few more issues I would like to point out,

The function pop() should be as follows,

 int pop(struct stack *sptr)
 {
    int ret=NULL;
    if(!isEmpty(sptr))
    {
        ret=sptr->cake[sptr->top];
        sptr->top--;
        return ret;
    }
    return 0;
 }

Otherwise the function returns random values when sptr is empty.

The statement if(q->top==10-1) should be if(q->top==9).