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
Following is an implementation of a stack in C
[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