Stack

A stack is a data structure in which insertion and deletion are allowed at only one end which is called the top of the stack so it follows last in, first order or LIFO.

let’s see in the picture

 

Insertion operation

Insertion in a stack is also known as a push operation. Always insert an element at the top of a stack, after inserting new element top pointer now points to a newly inserted element.

Overflow – If a stack is full, a new element can’t be inserted. This is known as stack overflow condition.

let’s see in the picture

Deletion operation

Deletion in a stack is known as pop operation. An element is always deleted from top of the stack. After deletion operation, a top pointer points to the previous element of deleted element.

Underflow – If a stack is empty delete operation can’t be performed. This is known as the underflow condition.

let’s see in the picture

After understanding the theory of stack let’s design algorithm for stack operations and we are going to perform following operation in a stack.

  1. A push operation to insert an element.
  2. A pop operation to delete an element.
  3. A Size operation to calculate the number of elements in a stack.
  4. A top element operation to get the top element of the stack.

Push operation

PUSH_STACK(STACK,TOP,SIZE,ELEMENT)
1. if  TOP == SIZE - 1
	 stack is full	
	 print overflow and return
2. Increment TOP
	TOP = TOP + 1
3. Insert new element at top
	STACK [ TOP ] = ELEMENT
4. Exit.

Pop operation

POP_STACK(STACK,TOP)
1. if  TOP == -1
	 stack is empty	
	 print underflow and return
2. Decrement TOP
	TOP = TOP - 1
3. Exit.

Size operation

SIZE_STACK(TOP)
1. Return TOP + 1
2. Exit.

Top element operation

TOP_ELEMENT_STACK(STACK,TOP)
1.Return STACK [ TOP ]
2. Exit.

Now we will see a C program of a stack.

In this code, I am using -999999 as an INVALID value, you can use whatever suits you better according to the problem statement.

 
//Insert
void push_stack(int stack[],int *top,int size,int element){
    if (*top == size - 1){
        printf("Overflow\n");
        return;
    }
    *top = *top + 1;
    stack[*top] = element;
}
//Delete
void pop_stack(int stack[],int *top){
    if (*top == -1){
        printf("Underflow\n");
        return;
    }
    *top = *top - 1;
}
//Size
int size_stack(int top){
    return top + 1;
}
//Top
int topElement(int stack[],int top){
    if (top == -1){
        printf("Stack is empty,underflow\n");
        return -999999;
    }
    return stack[top];
}
//Print
void printStack(int stack[],int size){
    for(int i=0;i<=size;i++){
    printf("%d ",stack[i]);
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    
    int top = -1;
    int size = 5;
    int stack[size];
    
    printf("Size of stack is %d\n",size_stack(top));
    
    int topValue = topElement(stack,top);
    if (topValue  != -999999){
        printf("Top element is %d\n",topValue);
    }
    
    push_stack(stack,&top,size,120);
    push_stack(stack,&top,size,21);
    push_stack(stack,&top,size,32);
    push_stack(stack,&top,size,352);
    push_stack(stack,&top,size,65);
    
    printf("After inserting 5 element stack is \n");
    
    printStack(stack,top);
    
    printf("Inserting 6th element \n");
    
    push_stack(stack,&top,size,645);
    
    printf("Size of stack is %d\n",size_stack(top));
    
    pop_stack(stack,&top);
    pop_stack(stack,&top);
    pop_stack(stack,&top);
    
    printf("After removing 3 element stack is \n");
   
    printStack(stack,top);
    
    printf("Top element is %d\n",topElement(stack,top));
    
    printf("After deleting 2 more element\n");
    
    pop_stack(stack,&top);
    pop_stack(stack,&top);
    
    topElement(stack,top);
    
    
    return 0;
}

Output

Size of stack is 0
Stack is empty,underflow
After inserting 5 element stack is 
120 21 32 352 65 
Inserting 6th element 
Overflow
Size of stack is 5
After removing 3 element stack is 
120 21 
Top element is 21
After deleting 2 more element
Stack is empty,underflow

 

Leave a Reply

Your email address will not be published. Required fields are marked *