A Simple Stack in C Using an Array

A stack is like a stack of plates – the last plate put on the stack is the first one taken off. This behavior is known as LIFO – last in, first out. Computers in general are stack oriented machines.

The simplest implementation of a stack is as an array. Since the array’s name devolves to a pointer to the first element in the array, we always have a readily available base pointer. It is also possible to implement a stack using linked lists.

The stack can be managed with only two functions: the push() function to write data to the top of the stack, and the pop() function to read data from the top of the stack. As a side effect, the push() function increments the top pointer or array subscript. As a side effect, the pop() function in turn decrements the pointer or array subscript.

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


//add an int to the
//stack
int push(int *stack, int *top);
//return an int
int pop(int *stack, int *top);
//return an int value from stdin
int getInt();

const int stack_size = 10;

int main(void){


    char c, ch;
    int x;

    int stack[stack_size];

    int top = -1;

    while(1){
        printf("Enter command (R)ead, (W)rite, or (Q)uit: ");
        ch = getchar();
        //clear buffer
        while((c = getchar())!='\n');

        switch(ch){
            //assign old value to y
            //newly popped value to x
            case 'r':
            case 'R':
                x = pop(stack, &top);
                printf("Value popped of stack: %d\n", x);
                break;
            case 'w':
            case 'W':
                if((push(stack, &top))<0){
                    printf("Stack is full!\n");
                } else {
                    printf("Value added to stack: %d\n", stack[top]);
                }
                break;
            case 'q':
            case 'Q':
                printf("Exiting...");
                exit(EXIT_SUCCESS);
        }//end switch
            
    }//end while

    return 0;

}

int pop(int *stack, int *top){
    if(*top >= 0){
        int returnInt = *(stack + *top);
//decremement index value to
//top of the stack by one
        (*top)--;
        return returnInt;
    } else {
        return 0;
    }
} //end pop

//note that array name devolves
//to point to base address of the array
int push(int *stack, int *top){
//increment value pointed to by one
    (*top)++;    
//if we are still within the bounds
//of the array, add a value at the next index
    if(*top < stack_size){
        *(stack+(*top)) = getInt();
        return 0;
    } else {
        return -1;
    }
} // end push

int getInt(){
    printf("Please enter the int value: ");
    char input[12];
    fgets(input, sizeof(input), stdin);
    return atoi(input);    
}

The getInt() function reads up to 12 characters from stdin and places it in a buffer called input. The function then converts the char string contained in input to an integer using the atoi() function and returns it to the calling function.

The pop() function accepts two arguments, one being the base address of the int array, which stores the stack values, and the second being a pointer to the integer value that represents the offset needed to retrieve the value at the top of the stack. We pass the second argument as a pointer because we want to manipulate the integer value it points to directly within the function.

The push() function accepts two arguments, one being the base address of the int array, and the second being an integer value passed “by reference” as a pointer. If the value pointed to by the second parameter is less than the bounds of the int array, we can add a value to the top of the stack.  To access the value pointed to by the second parameter, we must use the dereference operator. It is important to remember to use the dereference operator when using the second parameter as an offset to the base address of the int array.

Note that the push() function returns negative one if there is no more room on the stack.

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s