Push and Pop function

Question

Im trying to replicate the push and pop functions using integers and an int array. However Im having trouble with finding the size of the array in the push function. How would I find the size or 'push' a new value into the array

typedef int data_t;
int
main(int argc, char **argv){
int *S, i;

    S = malloc(10*sizeof(int));
    S = NULL;
    push(1,S);
    push(3,S);

    for(i = 0; S[i]; i++){
        printf("%d\n",S[i]);
        }
    return 0;
}

void
push(data_t n,int *S ){
    int size = 0, i = 0;

    if (S == NULL){
        S[0] = n;
    }
    else{
        while(S[i] != NULL){
            size++;
            i++;
        }
        S[size] = n;
    }
}

`S = malloc(10*sizeof(int)); S = NULL;` I think you need to review the basics of C programming. You overwrite your variable right away so your `malloc`'d memory is lost. And with `if (S == NULL) S[0] = ...` you have yourself a nice boom — Eregrith, Jun 03 '15 at 08:38
Use a struct: `struct ArrayWithExtras { int *data; size_t total; size_t used; };` — pmg, Jun 03 '15 at 08:39
Sorry but this isn't about "push and pop function", or "finding the size of the array". This is "my code isn't working, why?", with so many problems tossed together that it becomes unsuited for a Q&A site. Voting to close. Sorry, really, but [you need a book](http://stackoverflow.com/questions/562303). — DevSolar, Jun 03 '15 at 08:58

score 3 · Answer 1 · answered Jun 03 '15 at 08:39

You first allocate an array of ten integers and assign the pointer to S. You then reassign S, making it point to NULL. That is not a valid pointer you can dereference. Dereferencing a null-pointer leads to undefined behavior.

You need to keep the size of the stack separately, and pass it along to the functions. Or use a structure containing both the pointer and the size.

Sir Jo Black · Answer 2 · 2015-06-03T15:20:31.033

I've written the below code on the fly! It seems to run good! It implements a stack management with stack overflow/underflow controls.

The main contains code to demonstrate the use of all the stack functions:

int initStack(StackType * stack, size_t numOfElement);
int freeStack(StackType * stack);
int push(StackType * stack, int value);
int mayPush(StackType *stack);
int pop(StackType * stack, int * value);
int pop2(StackType * stack);
int mayPop(StackType *stack);
StackError getError(StackType * stack);

The code uses the following basic stack operations:

stack init: sp="stack dimension".
push: stack[--sp]=value;
pop: stack[sp++]=value;
Stack overflow: (sp==0) [when we try to push a value]
Stack underflow: (sp=="stack dimension") [when we try to pop a value]

The code:

#include <stdio.h>
#include <malloc.h>

typedef enum {
    NO_ERROR,
    MEMORY_ERROR,
    STACK_OVERFLOW,
    STACK_UNDERFLOW
} StackError;

typedef struct {
    int * stack;
    size_t numOfElem;
    size_t sp;     //stack pointer
    StackError err;
} StackType;

int initStack(StackType * stack, size_t numOfElement);
int freeStack(StackType * stack);

int push(StackType * stack, int value);
int mayPush(StackType *stack);

int pop(StackType * stack, int * value);
int pop2(StackType * stack);
int mayPop(StackType *stack);

StackError getError(StackType * stack);

int initStack(StackType * stack, size_t numOfElement)
{
    if ( (stack->stack=malloc(sizeof(*stack->stack)*numOfElement))==NULL ) {
        stack->err=MEMORY_ERROR;
        return stack->err;
    }

    stack->err=NO_ERROR;

    stack->numOfElem=numOfElement;
    stack->sp=numOfElement;       //The stack is void!

    return stack->err;
}

int freeStack(StackType * stack)
{
    if (stack->stack==NULL){
        stack->err=MEMORY_ERROR;
        return stack->err;
    }

    stack->err=NO_ERROR;
    free(stack->stack);
    stack->stack=NULL;

    return stack->err;
}

int push(StackType * stack, int value)
{
    if (stack->stack==NULL) {
        stack->err=MEMORY_ERROR;
        return stack->err;
    }

    if (!stack->sp) {
        stack->err=STACK_OVERFLOW;
        return stack->err;
    }

    stack->err=NO_ERROR;
    stack->stack[--stack->sp]=value;

    return stack->err;
}

int pop(StackType * stack, int * value)
{
    if (stack->stack==NULL) {
        stack->err=MEMORY_ERROR;
        return stack->err;
    }

    if (stack->sp>=stack->numOfElem) {
        stack->err=STACK_UNDERFLOW;
        return stack->err;
    }

    stack->err=NO_ERROR;
    *value=stack->stack[stack->sp++];

    return stack->err;
}

int pop2(StackType * stack)
{
    int value;

    pop(stack,&value);

    return value;
}

int mayPush(StackType *stack)
{
    return (stack->stack!=NULL && stack->sp>0)?1:0;
}

int mayPop(StackType *stack)
{
    return (stack->stack!=NULL && stack->sp<stack->numOfElem)?1:0;
}

StackError getError(StackType * stack)
{
    return stack->err;
}

int main(void)
{
    StackType stack;
    int res,i,j;
    size_t max=20;

    if ( (res=initStack(&stack, max))!=NO_ERROR ) {
        printf("Error: %d\n",res);
        return res;
    }

    //Fill the stack;
    printf("Pushing: ");
    i=0;
    while(mayPush(&stack)) {
        push(&stack,++i);
        printf("%d ",i);
    }
    puts("");

    //Try to push another element into the stack
    res=push(&stack,i);
    if (res!=NO_ERROR) {
        printf("Push error: %d\n",res);
    }

    //Read all the stack
    printf("Popping: ");
    while(mayPop(&stack)) {
        printf("%d ",pop2(&stack));
    }
    puts("");

    //Try to pop another element into the stack form 1
    res=pop(&stack,&i);
    if (res!=NO_ERROR) {
        printf("Pop error: %d\n",res);
    }

    //Try to pop another element into the stack form 2
    i=pop2(&stack);
    res=getError(&stack);
    if (res!=NO_ERROR) {
        printf("Pop error: %d\n",res);
    }

    //Fill an half of the stack
    printf("Pushing: ");
    for(i=1;i<=(int)max/2;i++) {
        push(&stack,i);
        printf("%d ",i);
    }
    puts("");

    //Get some value from the stack
    printf("Popping: ");
    for(i=1;i<=(int)max/4;i++) {
        printf("%d ",pop2(&stack));
    }
    puts("");

    //Put some value in the stack (also generates errors)
    for (j=0;j<3;j++) {
        printf("Pushing: ");
        for(i=1;i<=(int)max/3;i++) {
            printf("%d ",i*3+j);
            if ( (res=push(&stack,i*3+j))!=NO_ERROR ) {
                printf("Push error: %d\n",res);
            }
        }
        puts("");
    }

    //Get some value from the stack (also generates errors)
    printf("Popping: ");
    for(i=0;i<(int)max+2;i++) {
        if ( (res=pop(&stack,&j))!=NO_ERROR ) {
            printf("\nPop error: %d",res);
        } else {
            printf("%d ",j);
        }
    }
    puts("");

    puts("Deallocating the stack!");
    freeStack(&stack);
    printf("Pushing: ");
    if ( (res=push(&stack,415))!=NO_ERROR ) {
        printf("Push error: %d\n",res);
    }

    puts("Re-Deallocating the stack!");
    if ( (freeStack(&stack))!=NO_ERROR ) {
        printf("freeStack Error: %d\n",res);
    }

    return 0;
}

WedaPashi · Accepted Answer · 2015-06-03T10:52:56.833

Firstly, so glad to see that you didn't cast the result of malloc.

Your
```
int  
main(int argc, char **argv){
```
Be assured that it doesn't have any side effect on the code behaviour, but as I have seen most of the people doing it this way, improves readability. should be,
```
int main(int argc, char **argv){  
```

This

S = malloc(10*sizeof(int));
S = NULL;

should be

S = NULL;        
S = malloc(10*sizeof(int));

I don't comprehend what you are trying through this:

for(i = 0; S[i]; i++)

May be this should be something like,

for(i = 0; i < MAX_LENGTH; i++)  //MAX_LENGTH should be some integer #defined somewhere in the code

Apart from these obvious mistakes, you can actually think about adding a check to ensure that, in the while loop in the function push() you don't overrun the value of size than what s can accommodate.

Then, instead of doing

if (S == NULL){
    S[0] = n;
}

in push(), I would have preferred checking if the memory is allocated after malloc. So,

S = malloc(10*sizeof(int));
if (S == NULL)
{
    //Error handling supposed to be done if no memory is allocated
}

This should do what you are looking forward to:

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

typedef int data_t;

int top;    

void push(data_t,int*);
int  pop(int*);

int
main(int argc, char **argv)
{
    int *S = NULL, i;
    top = -1;

    S = malloc(10*sizeof(int));
    if(S == NULL)
    {
        printf("Memory Allocation failed");
        //other error handling implementation if any
    }
    push(1,S);
    push(2,S);
    push(3,S);

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

    printf("\n Popping:\n");
    pop(S);

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

    return 0;
}

void
push(data_t n,int *S )
{
    //Check if Stack is full
    if (top == 10)
    {
        printf("Stack Full");
        //other implementation
    }
    else
    {
       ++top;
       S[top] = n;
    }
}

int
pop(int *S)
{
    //Check if Stack is empty
    if (top == -1)
    {
        printf("Stack Empty");
        //other implementation
    }
    else
    {
       return S[top--];
    }
}

The code is untested as I am travelling.

Point 1 is irrelevant (many coding styles place return type above name), Point 2 is probably not what OP meant (guess he wanted to initialize the first element to `NULL`), point 3 is not entirely correct, since OP wants to check `S[i]` to find the first `NULL`, but then he also have to check for `i < MAX_LENGTH` as you suggest. — Stefano Sanfilippo, Jun 03 '15 at 09:35
@StefanoSanfilippo: While I agree with what you suggested through the comment above about points 1 and 3, but am taken aback by point 2. How would that be possible? after `s = NULL;` you loose the reference. Did you mean OP was trying somethink like `*s = NULL;`? even thats horrible! — WedaPashi, Jun 03 '15 at 09:42
I may repeat Stefano but... (1) Question was not about code style preference. (2) First suggested command is redundant and doesn't make sense. — Pavel Šimerda, Jun 03 '15 at 09:59
^^ it's totally pointless initializing a var if you are going to load it in the next line. — Martin James, Jun 03 '15 at 12:02

Push and Pop function

3 Answers3