stacks

Pop operation in Stack

http://install4install.com

POP Operation

In this  operation topmost element is deleted from the stack.Before deleting check if TOP = NULL.If yes,it means that stack is empty and no deletion can be done.If an attempt to delete element is made in this case the UNDERFLOW message will be printed on screen.If no,then element is deleted then value of TOP is decremented by 1.

For example

  • We want to delete/pop 100 from this stack(Fig 9).
  • TOP = 4
  • TOP is not equal to null.
  • 100 is popped out/deleted.
  • TOP variable gets decremented to 3.

 

Screen Shot 2014-04-08 at 5.17.45 PM

Fig 9 : Pop Operation in Stack

Program 2

#include<stdio.h>

int main()
{
	int max;
	int stack[10];
	int num,val,i,temp;
	int top = -1;
	//printf("Enter the maximum size of stack");
	scanf("%d",&max);
	//printf("Enter the no of elements in stack");
	scanf("%d",&num);
	//printf("Enter the elements of stack");
	for(i=0;i<num;i++)
	{
		scanf("%d\n",&stack[i]);
		top++;
	}
	temp =top;
	if(top == -1)
	{
		printf("Underflow");
	}
	else
	{
		top =top -1;
		printf("The stack after pop operation is \n");
		for(i=0;i<temp;i++)
		{
		 printf("%d\n",stack[i]);
		top++;
	}
	}
	return 0;
}

Run
 Illustration of Program 2

  • Refer Program 1 for working of for loop and consider the same values.
  • top = 4
  • temp = top i.e temp = 4
  • if( top ==-1) i.e if no element is present in the stack then Underflow message will be printed on screen as no element is present to pop out.
  • top = top -1 =4-1=3.
  • for(i=0;i<temp;i++) - i would iterate till it is less than temp(4).
  • Elements of stack after pop operation is printed.

Short URL: http://tinyit.cc/dd0e98

Push operation in Stack

Push Operation

In this operation,the element is inserted at the top of stack(Fig 4).In order to insert element we need to check whether TOP = MAX-1.If  yes,then insertion  is not possible.If  element is still  tried for insertion , OVERFLOW message will be printed on screen as the stack do not have extra space to handle new element.If space is present and element is inserted,then the value of top will be incremented by 1 .

For example

  • Say we want to insert/push 800 in the following stack(Fig 4).
  • TOP = 4(index starts from 0)
  • MAX= 13
  • The value of TOP is 4 and MAX-1 is 13-1=12.TOP and MAX are not equal,thus element 800 can be pushed into the stack.
  • After insertion value of TOP gets incremented t0 5.
Screen Shot 2014-04-08 at 5.01.32 PM

Fig 5 : Push Operation in stack

Program 1

#include<stdio.h>
int main()
{
	int stack[10];
	int max;
	int num;
	int top = -1;
	int i;
	int item;
	//printf("Enter the maximum size of stack");
	scanf("%d",&max);
	//printf("Enter the no of elements in stack");
	scanf("%d",&num);
        //printf("Enter the elements of stack");
	for(i=0;i<num;i++)//Fig 7
	{
		scanf("%d\n",&stack[i]);
		top++;
	}

	if(top == max -1)//Fig 8
	{
		printf("Overflow");
	}
	else
	{
		//printf("Enter the item you want to insert\n");
		scanf("%d",&item);
		top = top + 1;//Fig 6
		stack[top] = item;
		printf("The stack after push operation is \n");
		for(i=0;i<=num;i++)
	{
	 printf("%d\n",stack[i]);
		top++;
	}
	}

	return 0;
}

Run

 Illustration of Program 1

  • Integer array of stack with size 10 is defined.
  • max is the maximum capacity of stack(Say 10).
  • num is the actual number of elements in stack(Say 5).
  • Variable top is initialized to -1.
  • i is used in for loop and item is the element we want to push in stack.
  • for loop(Fig 7) and scanf are used to read the values of stack.
Screen Shot 2014-04-09 at 1.11.26 PM

Fig 6 : Push Operation

 

Screen Shot 2014-04-09 at 1.03.37 PM

Fig 7 : Working of for loop

Screen Shot 2014-04-09 at 1.03.57 PM

Fig 8 : Working of if statement

 

 


Short URL: http://tinyit.cc/8c08e2

Stacks

Stacks are the linear data structure which stores data in an ordered way.The first element inserted is at the bottom and last element is at the top.It can be implemented using an array or a linked list.It is a LIFO(Last In First Out) data structure.This means that last element inserted will be first element to be removed incase of deletion operation(Fig 1,2).

Examples of Stack

  • Stack of plates.The last plate added is the first one to be removed.
  • A stack of files(Fig 1) .
  • A girl wearing bangles.The last bangle on the arm is the first one to be removed.
  • Luggage placed in truck.
Fig 1 : A Stack of Files

Fig 1 : A Stack of Files

Fig 2  : A Stack

Fig 2 : A Stack

Array Representation of Stack

In stack,the first element is at bottom(0 position) and last element at TOP position.The topmost element of stack is represented by TOP variable.MAX variable is used to store the maximum no of elements that the stack can hold(Fig 3).

  • if TOP =MAX-1,then stack is full.
  • if TOP = NULL,then stack is empty.
Fig 3 : A Stack

Fig 3 : A Stack

 

 

 

Operations on Stack

Each function in a stack runs in O(1) time.

Fig 3 : Push & Pop Operation

Fig 4 : Push & Pop Operation in Stack

 

PEEP Operation

This operation  first checks whether the stack is empty or has some elements(if TOP == NULL) and returns the value of topmost element without deleting it from the stack.In Fig 10, PEEP operation will return 100 to user.

Screen Shot 2014-04-08 at 5.29.36 PM

Fig 10 : A Stack

Applications of Stack

  • Converting a decimal number into binary.
  • Towers of Hanoi
  • Evaluation  of expression and syntax parsing.

 


Short URL: http://tinyit.cc/2c8820
By Cusp2207 on April 10, 2014 | Computer Science, Data Structures | A comment?
Tags: