Saturday, February 6, 2016

Stack data structure implemented in C


Stack

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. Only two operations are allowed in a stack:

  • Push the item into the stack
  • Pop the item out of the stack
A stack is a limited access data structure - elements can be added and removed from the stack only at the top.


Following is an implementation of a stack in C

stack.h file contains all the implementations related to the stack. Please find a link on github.com for the same implementation below at the bottom.


[code]#include <stdlib.h>
#include <limits.h>

//functions and data structure are implemented in the header file

typedef struct node
{
    int pos;
    int data[SIZE];
   
}stack_node;

typedef stack_node* stack_ref;

//create a new stack
stack_ref stackCreate()
{
    stack_ref ref = malloc(sizeof(stack_node));
    (*ref).pos = 0;
    return ref;
}

//destroy an existing stack
int stackDestroy(stack_ref st)
{
    if(st != NULL)
    {
        free(st);
        return 1;
    }
    return 0;
}

//add a new element
int stackPush(stack_ref st,int el)
{
    if(!StackIsFull(st))
    {       
        (*st).data[(*st).pos] = el;
        (*st).pos++;
        return 1;
    }

    return 0;
}

//remove the last element
int stackPop(stack_ref st)
{
    if(StackIsEmpty(st))
    {
        return INT_MIN;
    }   
    (*st).pos--;
    return (*st).data[(*st).pos];
}

//peek at the top element
int stackPeak(stack_ref st)
{
    if(StackIsEmpty(st))
    {
        return INT_MIN;
    }   
    return (*st).data[(*st).pos-1];
}

//if stack is empty
int StackIsEmpty(stack_ref st)
{
    if((*st).pos == 0)
        return 1;
    return 0;
}

//if stack is full
int StackIsFull(stack_ref st)
{
    if((*st).pos == SIZE)
        return 1;
    return 0;
}
[/code]

reverse_string.c file is an example of how a stack can be used.



[code]

//define the stack size here
#define SIZE 50

#include <stdio.h>
#include "stack.h"
#include <string.h>


int main()
{
    char string[SIZE];
    char reverse[SIZE];
    int i,j;
   
    printf("Enter the string to reverse: \n");
    fgets(string, SIZE, stdin);
   
    //create stack for the string
    stack_ref st = stackCreate();
   
    for(i = 0; i<strlen(string); i++)
        stackPush(st, (int)string[i]); 
   
    for(i = 0; i<strlen(string); i++)
        reverse[i] = (char)stackPop(st);
   
    reverse[i] = 0;
   
    printf("Reversed string: %s\n",reverse);
    return 0;
}[/code]

Please visit here to view the code in github.com

No comments:

Post a Comment

Optimized quick sort

In the previous article  we discussed about quick sort algorithm. In this article we are going to discuss about further optimizing quick sor...