Stacks
2.1 Introduction
What is an abstract data
type?
Abstract data type is a data type defined by the user.Typically
more complex than simple data types like int, float, etc.
Why abstract?
Because details of the implementation are hidden. When
you do some operation on the list, say insert an element, you just call a
function. Details of how the list is implemented or how the insert function is
written is no longer required.
Stack
- Stack is an ordered list in which,
insertion and deletion can be performed only at one end that is
called top.
- Stack is a recursive data structure
having pointer to its top element.
- Stacks are sometimes called as
Last-In-First-Out (LIFO) lists i.e. the element which is inserted first in
the stack, will be deleted last from the stack.
Example: Some of you may eat biscuits (or poppins). If you assume only one side of the cover is torn and biscuits are taken out one by one . This is called popping and similarly if you want to preserve some biscuits from some time later you put them back into pack through the same torn ending called pushing.
Stack Implementation
Stack can be implemented in two ways .
– Static implementation Using arrays
– Dynamic implementation Using linked list
Adding an element onto the stack (push operation)
Adding an element into the top of the stack is referred to as push
operation. Push operation involves following two steps.
- Increment the variable Top so that
it can now refere to the next memory location.
- Add element at the position of
incremented top. This is referred to as adding new element at the top of
the stack.
Stack is overflown when we try to insert an element into a
completely filled stack therefore, our main function must always avoid stack
overflow condition.
Algorithm:
begin
if top = n then stack full
top = top + 1
stack (top) : = item;
end
Implementation of push algorithm
in C language
void push (int val,int n) //n is size of the stack
{
if (top == n )
printf("\n Overflow");
else
{
top = top +1;
stack[top] = val;
}
}
Deletion of an element
from a stack (Pop operation)
Deletion of an element from
the top of the stack is called pop operation. The value of the variable top
will be incremented by 1 whenever an item is deleted from the stack. The top
most element of the stack is stored in an another variable and then the top is
decremented by 1. the operation returns the deleted value that was stored in
another variable as the result.
The underflow condition
occurs when we try to delete an element from an already empty stack.
Algorithm :
begin
if top = 0 then stack empty;
item := stack(top);
top = top - 1;
end;
Implementation of POP algorithm using C language
int pop ()
{
if(top == -1)
{
printf("Underflow");
return 0;
}
else
{
return stack[top - - ];
}
}
Program to implement stack
using Array
C program
#include <stdio.h>
int stack[100],i,j,choice=0,n,top=-1;
void push();
void pop();
void show();
void main ()
{
printf("Enter the number of elements in the stack ");
scanf("%d",&n);
printf("*********Stack operations using array*********");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("Chose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
show();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}
void push ()
{
int val;
if (top == n )
printf("\n Overflow");
else
{
printf("Enter the value?");
scanf("%d",&val);
top = top +1;
stack[top] = val;
}
}
void pop ()
{
if(top == -1)
printf("Underflow");
else
top = top -1;
}
void show()
{
for (i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
}
if(top == -1)
{
printf("Stack is empty");
}
}
No comments:
Post a Comment