Tuesday, September 23, 2014

Dynamic Stack using struct in C

Here's a simple implementation of dynamic stack in c.

/*
 * ----------------------------------------------------------------------------
 * "THE BURGER-WARE LICENSE" (Revision 42):
 *  wrote this file. As long as you retain this notice you
 * can do whatever you want with this stuff. If we meet some day, and you think
 * this stuff is worth it, you can buy me a burger in return. Abhishek Baddi
 * ----------------------------------------------------------------------------
 */

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

struct stack {
    int *data;                          //the data will be saved via this pointer
    int size;                           //this is the size of the stack
    int cursor;                         //the current position of cursor
};

void init(struct stack *x, int s) {               //initialize a stack "x" of size "s"
    x->data = (int *) malloc(s*sizeof(int)+1);    //allocate space for "s" integers on the stack
    x->size = s;                                  //remember the size
    x->cursor = 0;                                //initialize the cursor to 0
}


void push(struct stack *x, int item) {                       //push an "item" onto the stack
    if(x->cursor<x->size) {                                  //check if cursor hasn't reached the end
        x->data[x->cursor++] = item;                         //if so, copy "item" and then increment cursor
    }
    else {                                                   //cursor is at the end
        printf("[Error: %d] Stack is full.\n", x->cursor);   //print the error
    }
    //printf("cursor = %d.\n", x->cursor);
}

int pop(struct stack *x) {                           //pop an "item" from the stack
    if(x->cursor>0) {                                //if cursor is not at the base
        x->cursor--;                                 //decrement the cursor first
        //printf("cursor = %d.\n", x->cursor);
        return x->data[x->cursor];                   //then return the "item"
                                                     //we don't bother to clear the memory here.
    }
    else {
        printf("[Error: %d] Stack is empty.\n", x->cursor);        //same as before
        //printf("cursor = %d.\n", x->cursor);
        return 0;                                                  //print the error and return 0;
    }
}

int del(struct stack *x) {                      //"del" frees up the memory allocated by malloc()
    free(x->data);                              //free() requires the pointer to the allocated memory
    printf("--------------\nFreed\n--------------\n");
}

int main() {
    struct stack stk;
    int i, j;
    init(&stk, 5);                              //we initialize a stack of 5 elements

    for(i=0; i<10; ++i) {                       //we push more elements than the stack can handle
        push(&stk, i);
        printf("Pushing %d onto the stack.\n", i);
        /*
        for(j=0;j<5;++j) {
            printf("stk.data[%d]=%d\n",j,stk.data[j]);      //printing the contents of the stack after every push
        }
        */
    }
    printf("--------------\nPushing over.\n--------------\n");

    for(i=0; i<10; ++i) {
        printf("Pop %dth element: %d\n", i, pop(&stk));
    }
    del(&stk);
    return 0;
}

Every line of the code is commented. So, it'll be easier to understand.

No comments:

Post a Comment