Posts
Introduction:
The stack is a linear data structure. A stack can be conceptualized by a stack of dishes, kept one upon another. As the dish which is at the top has to be removed at the first to get the depth of the stack, the stack is called a first in last out or last in first out structure. This is abbreviated as LIFO.
A stack, as it can be imagined as a one-side open tube, has one opening only and therefore it has to store this opening as a pointer when it is implemented. This pointer is named "top".
A stack has 5 normal functions to work with. It has a peek function which helps to look at the top of the stack and know the value. It has a push function to push a value from the top. And then there is a pop function which deletes the top value each time it is called. The other two functions are rather technical as such isempty() is a standard function to check whether the stack is empty or not and the isfull() is a similar one to check whether the stack is full or not.
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10 //observe how macro defination is used
int count=0; //global initialisation of count to count no of nodes
//define the type you want to use
typedef struct node{
int value;
struct stack *next;
struct stack *prev;
}stack;
//defining the global bottom and top. Because of the LIFO structure, top is the tail in linked list
stack *bottom=NULL;
stack *top=NULL;
//createnode function as always for creating each node
stack *createnode(int a)
{
stack *newstack;
newstack=(stack*)calloc(1,sizeof(stack));
newstack->value=a;
newstack->prev=NULL;
newstack->next=NULL;
return newstack;
}
//isempty function. checks if the stack is empty
int isempty()
{
if(count==0)
{return 1;}
else
{return 0;}
}
//isfull function. checks if the stack is full
int isfull()
{
if(count==SIZE)
{return 1;}
else
{return 0;}
}
//push, like the addnode function in list. pushes a value each time on top of the stack
void push(int a) //void as no need to return
{ if(isfull()==1) //first check if full
{
printf("overflow condition: stack full");
}
else // this is the portion which does the push
{count+=1; //count for how many nodes we are putting
stack *newstack = createnode(a);
if(bottom==NULL) //if bottom is null, then make it head and tail
{
bottom=newstack;
top=bottom;
}
else // if the linked list has some nodes already, then this will work
{
top->next=newstack;
newstack->prev=top;
top=newstack;
}
}
}
int peek() //peek to see the value on the top
{
printf("%d\n",top->value);
}
int pop() //pop function to delete the top node
{ if(isempty()==1) //check if there is at all any node, if not say it is underflow
{
printf("underflow condition:empty stack");
}
else //if there is only one node present, then this block to be used, because its {if(count==1) //not same as deleting 1 node with more than 2 noded linked list
{ int c;
c=top->value;
top=NULL;
printf("popped value is:%d\n",c);
count=count-1;
}
else //deleting node from a linked list with more than 2 nodes
{int c;
c=top->value;
top=top->prev;
top->next=NULL;
printf("popped value is:%d\n",c);
count=count-1;
}
}
}
// driver code , the main function
int main(void) {
stack ruby; int i; // initiating a stack, and the integer i for looping
for(i=0;i<12;i++)
{push(i);
printf("%d\n",count);
}
isfull();
pop();
pop();
pop();
pop();
pop();
pop();
pop();
pop();
pop();
pop();
pop();
int c=isempty();
printf("%d",c);
printf("%d",count);
return 0;
}
- Success #stdin #stdout 0s 9424KB
1 2 3 4 5 6 7 8 9 10 overflow condition: stack full10 overflow condition: stack full10 popped value is:9 popped value is:8 popped value is:7 popped value is:6 popped value is:5 popped value is:4 popped value is:3 popped value is:2 popped value is:1 popped value is:0 underflow condition:empty stack10
For deeper understanding of data structures and algorithm, I recommend reading this following book:
Comments
Post a Comment