Stack is linear data structure based on “Last In First Out” (LIFO) principle. The elements that are inserted later will be deleted first and the elements added earlier will be deleted later. It is reversed time sequence of events. Application of stack is effective in problems where you have to maintain top-down sequence of events.
You can understand it to be a memory area that keeps on storing the elements at top. When you wish to remove an element, you can do so from the top position. If you have seen a stack of things like dishes, books, coins or cards, you will understand a stack easily. In all these physical application of stack you can add a new thing at the top and remove one from the top. In the case of stack of plates, first plate placed will be used up at the end. Plate placed at top will be taken first.
Memory Representation of Stacks
Stacks can be represented in memory in two ways.
Using the Contiguous Memory like an Array
In this representation the stack is implemented using the array. Variables used in this case are
- STACK- the name of the array storing stack elements
- TOP- storing the index where the last element is stored in array representing the stack
- MAX- defining that how many elements (maximum count) can be stored in the array representing the stack
Using the Non-Contiguous Memory like a Linked List
In this representation the stack is implemented using the dynamic data structure Linked List. Using linked list for Application of stack make a dynamic stack. You don’t have the need to define the maximum number of elements in the stack.
Pointers (links) to store addresses of nodes used are.
- TOP- storing the address of topmost element of the Linked list storing the stack
Application of Stack
Stacks are used in various applications-
- All postponed decisions in computer programs applications
- Maintaining function calls in recursive functions
- Heap memory
- Conversion of Infix arithmetic expressions into post fix expressions and their evaluation