Is there a way to avoid isEmpty() function for a stack?

Question

The following program use an interger stack. Which value the function int pop() can return when the stack is empty, if I want to avoid using isEmpty() before calling the pop() ?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define STK_SIZE 100
#define INSTR_SIZE 5
int push(int * stack,int * stk_top,int operand);
int pop(int * stack,int * stk_top);

int main()
{
    
    int n_instr=0;
    int operand=0;
    int stack[STK_SIZE];
    int stk_top = -1;
    char line[INSTR_SIZE+5];

    FILE * fp = fopen("instructions.txt", "r");
            
    fgets(line, sizeof(line), stdin);
    n_instr = atoi(line);
        
    for(int i=0;i<n_instr;i++)
    {
     fgets(line, sizeof(line), stdin);
     char * opcode = strtok(line, " \n");
           
    if(!strcmp(opcode,"PUSH")){
        
        operand = atoi(strtok(NULL, " "));
        push(stack,&stk_top,operand);
                }
    else if(!strcmp(opcode,"POP")){
        
        printf("%d\n",pop(stack,&stk_top));
        
        }
    
    else if(!strcmp(opcode,"ADD")){
        
        int n1 = pop(stack,&stk_top);
        int n2 = pop(stack,&stk_top);
        push(stack,&stk_top,n1 + n2);
        
        }

    else if(!strcmp(opcode,"SUB")){
        
        int n1 = pop(stack,&stk_top);
        int n2 = pop(stack,&stk_top);
        push(stack,&stk_top,n2 - n1);
        
        }
    
    }
     fclose(fp);
     
    while(stk_top>=0)printf("%d\n",pop(stack,&stk_top));
   
    return 0;

}

int push(int * stack,int * stk_top,int operand){

if(*stk_top<STK_SIZE-1){
            (*stk_top)++;
            stack[*stk_top]=operand;
            return 0;
            }
return 1;

}

int pop(int * stack,int *stk_top){
if(*stk_top>-1){
            int n = stack[*stk_top];
            (*stk_top)--;
            return n;
            }
return 0;
}

I use the above code for simulating the machine language instructions PUSH and POP ,ADD and SUB.For each POP instruction, output the value that was popped from the stack. After processing all instructions, print the final content of the stack, from the top to the bottom, one value per line.

Tried returning Integer values but it confuses with stack content, is there any work around ?

Answer 1

You could change pop() to this:

bool pop(int *stack, int *stk_top, int *old_top)
{
    if (*stk_top > -1) {
        if (old_top)
            *old_top = stack[*stk_top];

        (*stk_top)--;
        return true; // operation succeeded
    }
    return false;    // operation failed
}

You can choose to make use of the old stack top value or to discard it by simply making old_top NULL:

// Print all stack elements (except the top one) while deleting them altogether.

// Discard the first element (i.e. the top)
pop(stack, &stk_top, NULL);

int old_top = 0;
while (pop(stack, &stk_top, &old_top))
    printf("%d ", old_top);

Answer 2

You can for example change the function definition the following way:

int pop( int * stack, int *stk_top, int *value )
{
    int success = *stk_top != -1;

    if( success )
    {
        *value = stack[*stk_top];
        --*stk_top;
    }

    return success;
}

and call it like:

int n1
pop( stack, &stk_top, &n1 );

or like:

int n1
if ( pop( stack, &stk_top, &n1 ) )
{
    // do somethimg with n1
}

Your code would be clearer if you were to combine the array stack and the variable stk_top. For example:

struct Stack
{
    int a[STK_SIZE];
    int stk_top;
};

In main you could define an object of the structure type:

struct Stack stack = { .stk_top = -1 };

In this case the function will have less parameters and will be more clear as for example:

int pop( struct Stack *stack, int *value )
{
    int success = stack->stk_top != -1;

    if( success )
    {
        *value = stack->a[stack->stk_top];
        --stack->stk_top;
    }

    return success;
}

Answer 3

"I want to avoid using isEmpty() before calling the pop()"

Using isEmpty() to avoid calling pop() on an empty stack handles the "pre-" case. You can avoid this (if pop() handles underflow gently), but the code then has to check the operation's success testing a return code (the "post-" case). (Your "test" code expects push() to always succeed. Not wise.)

Below is an implementation that uses fewer parameters (only two in each case) and shows how both functions are called with their return values evaluated:

#include <stdio.h>

#define STACK_SIZE 5

int pop( int **stk, int *val ) { // NB: Address of popped value
    int *pTop = *stk;

    if( *pTop == 0 ) return 0; // failed

    *val = pTop[-1]; // fetch value
    pTop[-1] = pTop[0] - 1; // decrement count and store "below"
    *stk = pTop - 1;
    return 1; // success
}

int push( int **stk, int val ) {
    int *pTop = *stk;

    if( *pTop >= STACK_SIZE ) return 0; // failed

    pTop[1] = pTop[0] + 1; // incr count and store "above"
    pTop[0] = val;
    *stk = pTop + 1;
    return 1; // success
}

int main( void ) {
    int stk[ STACK_SIZE + 1 ] = { 0 };
    int *pStk = stk;
    int i, x;

    for( i = 0; i < STACK_SIZE + 2; i++ )
        printf( push( &pStk, 1<<i ) ? "pushed %d\n" : "Can't\n", 1<<i );

    for( i = 0; i < STACK_SIZE; i++ )
        printf( "stk[%d] = %d\n", i, stk[i] );

    for( i = 0; i < STACK_SIZE + 2; i++ )
        printf( pop( &pStk, &x ) ? "popped %d\n" : "Exhausted\n", x );

    return 0;
}

This works with a stack of int's. It uses the cell that is one above the top of the current stack to store the number of used cells below it. This value can be tested, to prevent both overflow and underflow.

Below is the same thing shortened by using double pointers. (this makes the code more challenging.)

int push( int **stk, int val ) {
    if( **stk >= STACK_SIZE ) return 0;

    *(*stk + 1) = **stk + 1; // record increase of current ceiling
    *(*stk)++ = val; // store value, then increment to new ceiling
    return 1;
}

int pop( int **stk, int *val ) {
    if( **stk == 0 ) return 0;

    *val = *(--*stk); // decrement and retrieve value
    **stk = *(*stk + 1) - 1; // replace (lower) top of stack with new count
    return 1;
}