implementing a push method of stack in C programming

Question

developers! I have a question of push() method of the stack in C!

I implemented my own push() method in C! but I can't understand the results!

My stack code below

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

#define MAX_SIZE 10

int top = -1;
int array[MAX_SIZE];

void init(){
    top = -1;
}

void push(int array[], int data){

    if(top > MAX_SIZE-1)
        fprintf(stderr, "invalid top %d\n", top+1);
    else{
        array[++top] = data; // top == 9, ++top == 10
        printf("top: %d data: %d\n", top+1, array[top]); // top == 11, top == 10
    }
}
void pop(int array[]){

}
void peek(int array[]){

}

int main() {
   int data = 1;

   for (int i=0; i<MAX_SIZE; i++)
        push(array, data++);
   push(array, 100);
   push(array, 200); // invalid top
   push(array, 300); // invalid top
   return 0;
}

and the result of this code is below

top: 1 data: 1
top: 2 data: 2
top: 3 data: 3
top: 4 data: 4
top: 5 data: 5
top: 6 data: 6
top: 7 data: 7
top: 8 data: 8
top: 9 data: 9
top: 10 data: 10
top: 11 data: 100
invalid top 11 
invalid top 11

The thing That I don't understand is .. in the results, when top: 11, actually, it's like top: top+1. If you look into the else statement in my push() method, you can notice it.

but, in else statement, when

printf("top: %d data: %d\n", 11, array[10]);
the result: top: 11 data: 100

, I think it should be an error. because I declared array size as 10 which is MAX_SIZE. so the index size will be 0 ~ 9. but how could array[10] works??

I really don't understand it.

C doesn't have any bound checking. It won't check if you've accessed an illegal memory location. `array[10]` is invalid. Using that invokes Undefined Behavior. Basically anything could happen like a crash, garbage value etc — Spikatrix, Jun 10 '18 at 08:21

score 5 · Accepted Answer · 2018-06-10T08:33:50.590

You can do it because C allows you to do so. But you shouldn't because it is dangerous to write in unallocated memory area. Your array has been assigned 10 integers of length. 10 integers of allocated memory. The 11th integer you try to access has no memory allocated for it.

As stated in the comment, the feature you'd want if you wanted your code to throw an error is bound checking. And it's exactly what your are doing in the first part of your push function.

Change your condition to top >= MAX_SIZE - 1 to fix the issue.

As for a better way to implement a stack, you could try to implement one on top of a linked list, which allows you to manage your stack in discontinuated memory areas.

You could also use unsigned int for array indexes because you don't need negative numbers there.

score 2 · Answer 2 · answered Jun 10 '18 at 08:25

You really need to learn basic debugging. For instance, the most basic thing is to find out the values at certain points in the code. This can be done via a debugger or a simple print statement.

I did this:

void push(int array[], int data){
    printf("%d\n", top);

    if(top > MAX_SIZE-1)
        fprintf(stderr, "invalid top %d\n", top+1);
    else{
        array[++top] = data; // top == 9, ++top == 10
        printf("top: %d data: %d\n", top+1, array[top]); // top == 11, top == 10
    }
}

And got this output:

...
top: 9 data: 9
8
top: 10 data: 10
9
top: 11 data: 100
10
invalid top 11
10
invalid top 11

Now it should be fairly obvious what the problem is.

I think it should be an error. because I declared array size as 10 which is MAX_SIZE. so the index size will be 0 ~ 9. but how could array[10] works??

It does not work. It does "work". Accessing out of bounds causes undefined behaviour. Read here for more info: https://stackoverflow.com/a/4105123/6699433

antara bhattacharya · Answer 3 · 2018-06-10T08:56:01.560

Actually ,in your code top is -1 while comparing with max_size-1 that means 9,the condition is true until the value of the top is 9.that means 10 times for top=-1,0,1,2,3,4,5,6,7,8.Therefore ,it is valid till array[10].

Try the below code.

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

#define MAX_SIZE 10

int top = -1;
int array[MAX_SIZE];

void init(){
    top = -1;
}

void push(int array[], int data){
++top;
    if(top > MAX_SIZE-1)
        fprintf(stderr, "invalid top %d\n", top+1);
    else{
        array[top] = data; // top == 9, ++top == 10
        printf("top: %d data: %d\n", top+1, array[top]); // top == 11, top == 10
    }
}
void pop(int array[]){

}
void peek(int array[]){

}

int main() {
   int data = 1;

   for (int i=0; i<MAX_SIZE; i++)
        push(array, data++);
   push(array, 100);
   push(array, 200); // invalid top
   push(array, 300); // invalid top
   return 0;
}

I think this what you desire.

top: 1 data: 1                                                                                                                                                                               
top: 2 data: 2                                                                                                                                                                               
top: 3 data: 3                                                                                                                                                                               
top: 4 data: 4                                                                                                                                                                               
top: 5 data: 5                                                                                                                                                                               
top: 6 data: 6                                                                                                                                                                               
top: 7 data: 7                                                                                                                                                                               
top: 8 data: 8                                                                                                                                                                               
top: 9 data: 9                                                                                                                                                                               
top: 10 data: 10         
invalid top 11                                                                                                                                                                              
invalid top 12                                                                                                                                                                              
invalid top 13

hey, I am confused by your comment. I used ++top. so the beginning of the array[++top] will be array[0]. So it will be array[0] ~ array[9] isn't it? — Noder, Jun 10 '18 at 08:46
If you do like this, you have to reset the value of `top` if the stack is full. — klutt, Jun 10 '18 at 09:03

yakobyd · Answer 4 · 2018-06-16T14:56:25.363

As an addition to the other answers, I would like to add a more convinient implementation to your stack using a struct. The behaviour of the program is changed a little bit, probably to the desired one.

#include <stdio.h>

#define MAX_SIZE 10

typedef struct Stack Stack;
void stackPush(Stack* s, int data);

struct Stack{
    unsigned int head;
    int arr[MAX_SIZE];

    void(*push)(Stack* s, int data);
};

void stackPush(Stack* s, int data) {
    if (s->head < MAX_SIZE) {
        s->arr[s->head] = data;  // push to stack
        printf("Head: %d. Data: %d.\n", s->head, s->arr[s->head]); 
        s->head++;  // move forward
    }

    else
        fprintf(stderr, "Stack is full! (head at: %d)\n", s->head);
}

int main() {
    // Initialize the stack
    Stack s;
    s.head = 0;
    s.push = stackPush;

    // Push the data
    int data = 1;

    int i;
    for (i = 0; i < MAX_SIZE; i++)
        s.push(&s, data++);

    s.push(&s, 100); // 
    s.push(&s, 200); // trying to push to a full stack
    s.push(&s, 300); // 

    return 0;
}

Which will output

Head: 0. Data: 1.
Head: 1. Data: 2.
Head: 2. Data: 3.
Head: 3. Data: 4.
Head: 4. Data: 5.
Head: 5. Data: 6.
Head: 6. Data: 7.
Head: 7. Data: 8.
Head: 8. Data: 9.
Head: 9. Data: 10.
Stack is full! (head at: 10)
Stack is full! (head at: 10)
Stack is full! (head at: 10)

I didn't know this way at all! very cool. really thanks. it helped me a lot. — Noder, Jun 16 '18 at 14:24

implementing a push method of stack in C programming

4 Answers4