I have previously described about Stack Data Structure in Java. That was part of collection framework we need not to implement code for various operations of stack. I also strongly recommend you to go through previous articles about array. These articles are on java array. But you must aware of What is data structure? For that you must have a look at Insertion sorting of data in C.
Data Structure:
Data Structure is way of representing data in computer memory. It has very significant role in design and implementation of algorithm. So while developing any application program or system utility, selection of data structure is very important. So you have to aware of characteristics of various data structure.
Stack Data Structure:
Stack Data structure follows Last In First Out rule. It means we can delete the element which we have inserted last. You can think this like the stack of plates. We can put a new plate at the top of stack or we can remove a plate from top of stack. It is implemented in various application. In stack data structure the top is location of last element. And only element at top can be removed.
For example The postfix-prefix conversion which are important in parsing phase of compilation.For this conversion stack is main data structure.
Static Stack:
Stack having fixed amount of memory is static stack. Once static stack is defined we cannot alter the size of stack.The maximum number of elements that we can insert in the stack is called capacity of stack. We use array as underlying data structure while implementing static stack.
Dyanamic Stack:
The stack whose size can increases as requirement is known as dynamic stack.If we use dynamic allocation of memory then stacks become grow-able. We implement dynamic stack using various methods for dynamic memory allocation like malloc, calloc, realloc, etc..
I’ll provide the implementation for static stacks using array in this article. So now i’m going through steps.
Stack Step By Step
operations in stack are –
1. Creation of stack:
For creating static stack we must have to know the capacity of stack. Stack will be an array of size equal to capacity. And we have to set top equals to -1 at beginning. Because there is no any element in stack. Top equals -1 means stack is empty.
#define CAPACITY 5
int top=-1;
int stack[CAPACITY]
we can directly pas a constant integer in array to specify capacity of stack. But it is good practice using macro for this. But remember you cannot use variable as array size.
int size=5; int stack[size]; is not allowed.
2. push the elements(insertion)-
Push in stack means inserting the element on the stack. This function will take an argument which need to be inserted in stack. Before pushing element we have to check whether stack is full or not. If top is equal to CAPACITY-1 then stack is said to be full. In this case we return push fail message. Another thing is we have to increase the top, than only we can insert element.
push(int element){
if(top==CAPACITY-1){
printf("Stack overflow error");
}else{
top=top+1;
stack[top]=element;
}
}
Remember two important thin is push. First Check for overflow and second increase top before insertion.
3. pop (delete)-
Pop means deleting element from stack. The element that can be removed is the top elemnt. Here also take care of two things. First check if stack is empty or not. If stack is empty then it is stack Underflow error. Second thing you must decrease top as removal operation.
int pop(){
int item;
if(top==-1){
printf("Nothing in stack\n");
}else{
item=stack[top--];
return(item);
}
}
This function returns the poped element from stack.
4. traverse(displaying all element)
For traversing we have to go through all the elements from stack. Now have a look at code implementation for traverse.
void traverse(){
if(top==-1){
printf("Stack is empty\n");
}else{
for(int i=top;i>-1;i--){
printf("%d\n",stack[i]);
}
}
5. isEmpty()
This not an operation. It is kind of utility function to check whether given stack is empty or not.
int isEmpty(){
if(top==-1){
return 1;
}else{
return 0;
}
6. isFull()
This function checks whether the stack is full or not. If top is CAPACITY-1 then stack is full.
int isFull(){
if(top==CAPACITY-1){
return 1;
}else{
return 0
}
}
Keeping things together:
#include
#define MAX 5
void traverse();
int stack[MAX];
signed int top=-1;
void push(int);
int pop();
void main(){
char ch;
int item;
while(ch != 'x'){
printf("\n********************\n");
printf("\n'a' for push\n");
printf("'b' for pop\n");
printf("'c' for traverse\n");
printf("'x' for exit\n");
printf("********************\n");
printf("Enter your choice\n");
scanf(" %c",&ch);
switch(ch){
case 'a': {
printf("enter the value to be pushed\n");
scanf("%d",&item);
getchar();
push(item);
break;
}
case 'b':{
item=pop();
printf("\n %d is poped\n",item);
break;
}
case 'c':{
printf("\n traversing stack\n");
traverse();
break;
}
case 'x':{
printf("Have a nice learning\n");
break;
}
default:{
printf("Wrong input\n");
}
}
}
}
output
‘a’ for push
‘b’ for pop
‘c’ for traverse
‘x’ for exit
********************
Enter your choice
b
33 is poped
********************
‘a’ for push
‘b’ for pop
‘c’ for traverse
‘x’ for exit
********************
Enter your choice
c
traversing stack
32
2
********************
‘a’ for push
‘b’ for pop
‘c’ for traverse
‘x’ for exit
********************
Enter your choice
x
Have a nice learning
Ok in next article i will discuss about the dynamic stacks and see how we can change size of stack at runtime.
