STACK

The linear data structures linked lists and arrays allow us to insert and delete elements at any place in the list, at the beginning, at the end, or in the middle. Sometimes we have situations, where insertion or deletion is required only at one end, either at the beginning or end of the list. One of the suitable data structures to fulfill such requirements is stacks.

A stack is a non-primitive linear data structure in which addition or deletion of elements takes place at the same end. This end is often called the top of stack. For e.g. a stack of plates, a stack of coins, etc. As the items in this type of data structure can be added or removed from the top, it means the last item to be added to the stack in the first item to be removed.

Therefore stacks are also called Last In First Out (LIFO) lists.

STACK AS AN ABSTRACT DATA TYPE

Stack can also be defined as Abstract Data Types (ADT). A stack of elements of any particular type is a finite sequence of elements of that type together with the following operations:

1. Initialize the stack to be empty.
2. Determine whether stack is empty or not.
3. Determine if stack is full or not.
4. If stack is not full, then add or insert a new node at one end of the stack called top. This operation is called push.
5. If the stack is not empty, then retrieve the node at its top.
6. If the stack is not empty, then delete the node at its top. This is called pop.

STACK TERMINOLOGY

1.Context: The environment in which a function executes : includes argument values, local variables and global variables. All the context except the global variables is stored in a stack frame. 

2. Stack frames: The data structure containing all the data (arguments, local variables, return address, etc.) needed each time a procedure or function is called.

3. MAXSIZE: This term is not a standard one, we use this term to refer the maximum size of stack.

4. TOP: This term refers to the top of stack (TOS). The stack top is used to check stack overflow or underflow conditions. Initially Top stores -1.This assumption is taken so that whenever an element is added to the stack the Top is first incremented and then the item is inserted into the location currently indicated by the top.

5. Stack: It is an array of size MAXSIZE.

6. Stack empty or underflow: This is the situation when the stack contains no element. At this point the top of stack is present at the bottom of the stack.

7. Stack overflow: This is the situation when the stack becomes full, and no more elements can be pushed onto the stack. At this point the stack top is present at the highest location of the stack.