INTRODUCTION TO STACK
Stack is one of the most commonly used linear data structure of variable size. In linear data structure discussed so far i.e array , insertion and deletion of an element can take place at any position of the array but in case of stack, the insertion and deletion of an element can occur at only one end, known as TOP.
In stack insertion operation is known as push and deletion operation is known as pop.
Stacks are also called Last in Last out (LIFO) list. It means that the last item to be added to the stack is the first item to be removed from the stack.
Operations on stack as follows:
There are two basic operations which are performed on the stack:
- Push
- POP
PUSH operation refers to the insertion of a new element into the stack. Its obviously, new element will be inserted on the top of the stack.We can perform the push operation only when the stack is not full i.e stack has sufficient space to accommodate the element. When stack is full and we are attempting to insert a new element into the stack then this conditions is known as stack overflow.
On the other hand, POP operations refers to the deletion of an element from the top of the stack. We can perform the pop operation only when the stack is not empty. Therefore, we must ensure that stack is not empty before applying the poo operation. when stack is empty and we are attempting to remove an element from the stack then this condition is known as stack underflow.
MEMORY REPRESENTATION OF STACKS
There are two common ways to implement a stack, it can be represented into memory by means of linear arrays or linked lists. Array representation of stack is accetable if an accurate estimate of the stack’s maximum size can be made before the program runs. The linked representation of stack is more suitable if an accurate estimate of the stack’s size can not be made in advance.
Array Representation of stacks
Representation of stacks using arrays is the simplest form of representation.But arrays put some restrictions while representing the stacks:
Stack must contain the homogeneous data elements.
One must specify the upper bound of the array i.e maximum size of the stack must be defined before implementing it. Generally, stack grows and shrinks over time but it is confined to the space allocated to the array implementating that stack.
While implementing a stack using array we need a pointer variable.
TOP which holds the index number of top element of the stack. Initially, the stack is empty, TOP has value equal to zero and when first element is inserted into the stack, the value of TOP is incremented by one and so on. Each time a new element is inserted into the stack, the value of the TOP will be incremented by one before placing the new element into the stack. On the other hand, each time a deletion is made , pointer variable TOP is decremented by one. One another variable Max is also used that represent the maximum number of elements that can be accommodated in the stack.
LINKED REPRESENTATION OF STACKS
Stacks can also be implemented using the linked list. By implementing the stacks using lined list, we can eliminate the drawbacks which arises while implementing the stacks using arrays. That is , while implementing the stacks using linked list , there is no need to know the maximum size of stack in advance. Linked representation of stacks allows the stacks to grow without any prior fixed limit.
The push and pop operation can be performed on the linked implementation of the stack by inserting and deleting an element at the beginning of the the linked list.
although stacks can be implemented using linked list by pushing or popping the element at the head of the linked list but the most common application for the stack has space restraint so that array implementation of the stack is natural and efficient one. In most of the operating systems allocation and de-allocation of memory is relatively expensive operation which a penalty for the flexibility of linked list implementation.