Data structures - Stack ADT: A stack is a linear data structure which follows LIFO (Last in first out) principle, in which both insertion and deletion occur at only one end of the list called the TOP.
OPERATIONS ON STACK :
The fundamental operations performed on stack are :
- Push (insertion)
- Pop (deletion)
The push operation is used to insert an element at the top of the stack. Pop is used to delete an element from the top of the stack.
Exceptional condition
- Overflow
- Underflow
Overflow: it is an attempt to insert an element when the stack is full .
Underflow: it is an attempt to delete an element when the stack is empty.
The general model is that there is some element that is at the top of the stack, and it is the only element that is visible.
IMPLEMENTATION OF STACK :
Since a stack is a list, any implementation will do. The two popular implementation performed are
- Linked list implementation of stacks.
- Array implementation of stacks.
Linked list implementation of stacks:
The first implementation of stack uses a singly linked list. Here PUSH and POP operations are performed at the TOP of the list.
Creating a stack :
Creating a stack is also simple. We merely create a header node, makeEmpty sets the next pointer to NULL.
Routine to check whether a stack is empty:
IsEmpty(stack R)
{
Return R->Next==NULL;
}
Routine to create an empty stack:
Stack
CreateStack (void)
{
Stack R;
R=malloc(sizeof(struct Node));
If(R==NULL)
FatalError("Out of total space><><");
makeEmpty(stack R)
{
If(R==NULL)
Error("It has to be CreateStack at first");
Else
While(!IsEmpty(R))
Pop(R);
}
- [SEE: C Program Tutorials] & [IT Companies Details]
PUSH OPERATION :
The process of inserting a new element to the top of the stack. For any PUSH operation the top is incremented by ‘1’. They are also called input operations.
Routine to push onto a stack :
Void
Push(ElementType K, Stack R)
{
ptrtoNode TMP;
TMP=malloc(sizeof(struct Node));
If(TMP=="")
FatalError("Out of the total storage");
Else
{
TMP->Element=K;
TMP->Next=R->Next;
R->Next =TMP;
}
}
TOP OPERATION:
A TOP operation examines the element at the front of the list , returning its value.
Routine to return top element in a stack:
ElementType
Top(stack R)
{
If(!IsEmpty(R))
Return R->Next->Element;
Error("This is an Empty stack");
Return 0;
}
POP OPERATION:
The process of deleting an element from the top of the stack is called POP operation. After every POP operation, the top pointer is decremented by ‘1’. They are also called output operations.,which delete the most recently inserted element.
Routine to pop from a stack:
Pop(stack R)
{
PNode FC;
If(IsEmpty(R))
Error("This is an Empty stack !!");
Else
{
FC=R->next;
R->next=R->next->next;
Free(FC);
}
}