What Is Stack?
A stack is a data structure which is used to store data in a particular order. Two operations that can be performed on a stack include push operation which inserts an element into the stack and pop operation which removes the last element that was added into the stack. It follows Last In First Out (LIFO) order. Every time an element is added, it goes on top of the stack and the only element that can be removed is the element at the top of the stack, just like a pile of objects. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.
Stack can easily be implemented using an array or a Linked List. Arrays are quick but limited in size and linked list requires overhead to allocate, link, unlink and de-allocate, but is not limited in size.
Advantages Of Using Stack
- Stack automatically cleans up the object.
- It allows control on memory allocation and de-allocation.
- It is difficult to resize the variable.
- A stack is used when a variable is not used outside that function.
- Stack is not easily corrupted.
- With Stack, it is possible to manage the data in Last in First out (LIFO) method, something that is not possible with linked list and array.
Disadvantages of Stack
- Stack memory is very limited.
- There is usually the risk of stack overflow when creating too many objects on stack.
- Random access is usually not possible with stack.
- With stack cases of abnormal termination may occur, because stack usually falls outside of the memory area.
- Variable storage will be overwritten and this can result to undefined behavior of the program.
Application of stack
- Expression Conversion (Infix to Postfix, Postfix to Prefix etc).
What Is Heap?
Heap is a specialized case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. A heap respects the heap property namely: every node must be lower than each of its children or its lowest element at its root to be easily accessible.
To represent a binary tree such as a heap, one implementation is to make a dynamic allocation for each node, with 2 pointers pointing to its children. A heap can also be implemented by representing it in the form of an array, by doing a level order traversal of the heap whereby the array starts with the element at the root, then follows with the children of that root, then all the children of those children and then the great-grand-children and so on.
Advantages Of Using Heap
- Heap has unlimited memory size.
- It allows access of variables globally.
- Heap method also used in the propriety Queue.
- Heap helps to find the greatest and minimum number.
- To free the memory used by the object, garbage collection runs on the heap memory.
Disadvantages Of Using Heap
- It can provide the maximum memory an OS can provide.
- It takes a lot of time in execution when compared to stack.
- Memory management is a bit complex because it is used globally.
- Variables stored in stacks are only visible to the owner’s Thread whereas objects created in the heap are visible to all thread. In simple terms, stack memory is a kind of private memory of Java Threads while heap memory is shared among all threads.
- Heap is a hierarchical data structure whereas stack is a linear data structure.
- Heap can be implemented using array and trees whereas a stack can be implemented in three ways: Linked list based, dynamic memory or simple array based.
- A heap is flexible and the allotted memory can be altered. On the other hand, Stack is not flexible; the memory size allotted cannot be changed.
- Stack memory is used to store local variables and function call whereas heap memory is used to store objects in Java. Irrespective of where the object is created in code for example as a member variable, local variable or class variable, they are always created inside heap space in Java.
- Stack frame access is easier than the heap frame as the stack have small region of memory and is cache friendly, but in case of heap frames which are dispersed throughout the memory so it causes more cache misses.
- In a stack, the allocation and de-allocation is done by the CPU whereas, in heap, allocation and de-allocation needs to be done by the programmer manually.
- Almost all tree operations can be applied on heaps. Heapifying an element, find minimum and find maximum. On the other hand, Push, Pop and Top are the only operations on the stack.
- There is no case of overflow and underflow in heap whereas in stack, we can limit stack size, so that stack overflow and stack underflow conditions will occur. When we want to pop an element from the empty stack, that situation is referred to as stack underflow. On the other hand, when we want to push an element to a full stack (stack elements equal to stack size) the situation is referred to as stack overflow.
- Stack is thread specific whereas heap is application specific.
- Handling of heap frame is more costly than handling of stack frame.
Read Further: Procedural Vs. Object Oriented Programming
Stack Vs. Heap In Tabular Form
|BASIS OF COMPARISON||STACK||HEAP|
|Visibility of variables/objects||Variables stored in stacks are only visible to the owner’s Thread.||Objects created in the heap are visible to all thread.|
|Type of Structure||Stack is a linear data structure.||Heap is a hierarchical data structure.|
|Implementation||Stack can be implemented in three ways: Linked list based, dynamic memory or simple array based.||Heap can be implemented using array and trees.|
|Flexibility||Stack is not flexible; the memory size allotted cannot be changed.||A heap is flexible and the allotted memory can be altered.|
|Use||Heap memory is used to store objects in Java.||Stack memory is used to store local variables and function call.|
|Access||Stack frame access is easier than the heap frame as the stack have small region of memory and is cache friendly.||Heap frame access is a bit harder than the stack frame because heap frames are dispersed throughout the memory and therefore causes more cache misses.|
|Allocation And De-allocation||In a stack, the allocation and de-allocation is done by the CPU.||In heap, allocation and de-allocation needs to be done by the programmer manually.|
|Operations||Push, Pop and Top are the only operations on the stack.||Almost all tree operations can be applied on heaps. Heapifying an element, find minimum and find maximum.|
|Overflow and Underflow||In stack, we can limit stack size, so that stack overflow and stack underflow conditions will occur.||There is no case of overflow and underflow in heap.|
|Specificity||Heap is application specific.||Stack is thread specific.|
|Cost||Handling of stack frame is less costly than handling of heap frame.||Handling of heap frame is more costly than handling of stack frame.|