Memory allocation is the process of allocating a section of the memory or the entire memory for running certain programs. By this process, programs and processes are assigned a space in the physical or virtual memory. Software applications and the system’s hardware are used for the process of allocation.
Based on their requirements, programs are assigned a memory space. When a program completes execution, the memory space is released. This section is then assigned to another process or program. There are two main types of memory allocation – dynamic and static. In dynamic memory allocation, the programs are assigned a memory space during run time. But, in static memory, the memory space is allocated to the programs during compile time.
In this article, we will focus on two popular data structures used for memory allocation – stack and heap.
What is a Stack?
A stack is an abstract data structure that is used for memory allocation. It is a special portion of the memory that is used for storing temporary variables. These variables may have been created using a function. Using the stack data structure, these variables and values are stored, declared and initialised during runtime. Local variables, reference variables and methods are stored in a stack. A stack has elements of a similar data type.
Being a form of temporary storage, when an operation associated with the memory is over, space will be erased.
In a stack, the capacity is pre-defined. The data structure allows inserting and deleting elements in a specific order. If an element is added to the stack, it is stored at the top of the stack. If you have to delete an element, the element at the top has to be removed first. It is a form of linear data structure and follows the order LIFO (Last In First Out).
For example, a stack resembles a pile of books or cards. If you want to remove the middle book, you first need to remove the top book and then the one below it. You need to continue these steps until you get to the middle book.
These basic functions are used on the stack for performing data operations:
- Push – This function is used for adding or pushing items to a stack. If a stack is filled with elements and there is no space left, the condition is called an overflow.
- Pop – This function is used for deleting a stack element. All items are removed based on the LIFO rule. For an empty stack with no elements to remove, it is called an Underflow condition.
- isEmpty – This function is used for checking whether a stack is empty or not.
- isFull- This function is used for checking whether a stack is full or not.
- Peek or Top – This function returns the top element of the stack.
Time complexity
Let us look at the time complexities of the functions used for stacks:
- Push () – O (1)
- Pop () – O (1)
- isEmpty () – O (1)
- Top () – O (1)
Both Push () and Pop () have time complexities of O (1). This is because while inserting or deleting an element from the stack, we have to access the top element. This is a single-step process, so the time complexity is O (1).
Pros and Cons of Stack
The advantages of using the stack data structure are as follows:
- If you call a stack function, the local variables get stored in the stack. When the function is returned, these variables are destroyed automatically. So the memory is used efficiently.
- As stack automatically cleans up the memory space, the CPU organises the stack memory well, allowing faster reads and writes to the stack variables.
- It helps you organise data simply by using the LIFO order. This further helps in the computation of complex arithmetic operations.
- The elements can be accessed very fast.
- Stack variables cannot be resized.
- Objects are cleaned up automatically.
- Elements cannot be inserted easily in the middle, reducing the chances of data corruption.
The disadvantages of using the stack data structure are as follows:
- The elements cannot be accessed randomly.
- If too many elements are stored in the stack, it may cause a stack overflow, which might create allocation problems.
- If the variable storage is overwritten, it can lead to abnormal behaviour of the programs or the functions.
- The stack memory is limited.
Example of Stack using Java programming language
//Java program to illustrate the working of stack using Java
//Importing Scanner Class of Util Package
import java.util.Scanner;
//Public Class of the program
public class Main
{
//Creating the object for Scanner Class
static Scanner input = new Scanner(System.in);
static int stack[], top = -1, size;
//Block code to execute a function before main method
static{
create();
}
//Main method of the program
public static void main(String[] args)
{
int choice,item;
//While loop with always true condition (or Infinite loop)
while(true){
//Stack operation
System.out.println("1. Push Operation");
System.out.println("2. Pop Operation");
System.out.println("3. PeekAt Operation");
System.out.println("4. Traverse Operation");
System.out.println("5. Quit");
System.out.print("Please Enter your choice : ");
//Taking input which operation user want to perform
choice = input.nextInt();
//Switch case to do operation according to user choice
switch(choice){
case 1:
System.out.println("Enter the Element : ");
item = input.nextInt();
push(item);
break;
case 2:
item = pop();
if(item == 0){
System.out.println("Stack is Underflown");
}else{
System.out.println("Popped item is : "+item);
}
break;
case 3:
item = peekAt();
if(item == 0){
System.out.println("Stack is Underflown");
}else{
System.out.println("Element at the top is : "+item);
}
break;
case 4:
traverse();
break;
case 5:
System.exit(1);
break;
default:
System.out.println("Please choose a valid operation");
}
}
}
//Function to create the stack with the user select value
static void create()
{
System.out.print("Enter the size of stack : ");
size = input.nextInt();
stack = new int[size];
System.out.println("Stack has been created with size of :"+size);
}
//Function to check, Is Stack is full
static boolean isFull(){
if(top == size-1){
return true;
}else{
return false;
}
}
//Function to check, Is Stack is empty
static boolean isEmpty(){
if(top == -1){
return true;
}else{
return false;
}
}
//Function to add elements into the stack
static void push(int ele)
{
if(isFull()){
System.out.println("Stack is full and overflowing");
}else{
stack[++top] = ele;
}
}
//Function to show and remove the top most value from the stack
static int pop(){
if(isEmpty()){
return 0;
}else{
return stack[top--];
}
}
//Function to show (without removing) the top most value from the stack
static int peekAt(){
if(isEmpty()){
return 0;
}else{
return stack[top];
}
}
//Function to print all available elements in the stack
static void traverse(){
if(isEmpty()){
System.out.println("Stack is empty");
}else{
System.out.println("Elements of stack are : ");
for(int i = top; i >= 0; i--){
System.out.println(stack[i]);
}
}
}
}
What is Heap?
A heap is a data structure that is based on a Tree, where all the nodes of the Tree are arranged in a specific order. The Tree here is a complete binary tree. Here the root node of the tree is compared to the children and placed accordingly. In any heap, the maximum number of children depends upon the type of heap it is.
The two most common types of heaps are as follows:
Max Heap
In this heap, the value of the root node will be larger than or equal to the values of the children nodes. This root node value is greater than all of the other nodes in the heap.
Let us look at the algorithm for constructing a Max heap data structure. In this algorithm, one element will be inserted at a time. At all times, the heap must maintain its property – parent node is greater than or equal to children nodes.
The steps are as follows:
Step 1: At the end of the heap, create a node
Step 2: Give this node a value
Step 3: Compare the value of the parent node and this newly created child node
Step 4: If the value of the new node is greater than the parent, then interchange the values
Step 5: Continue repeating the steps 3 and 4 when inserting elements while the heap property is maintained
A max heap is a type of data structure that is a complete binary tree. Usually, an array is used for representing a Max heap. So for a max heap, the root node will be at the array position Arr [0]. For the node at the ith position,
- Arr [(i-1)/2], will return the index of the parent node
- Arr[(2*i)+1], will return the index of the left child node
- Arr[(2*i)+2], will return the index of the right child node
Example of Max Heap using Java programming language
//Java program to illustrate Heap Algorithm using Java
//Max Heap
//Main Class of the program
public class Main{
static int[] theHeap;
static int capacity;
static int pos;
//Function to create the array
static void MaxHeap(){
pos = 1;
capacity = 10;
theHeap = new int[capacity];
}
//Function to insert the elements into the array according to the position
static void insert(int value){
if(pos == capacity){
System.out.println("Tree is overflow");
}else{
theHeap[pos++] = value;
int child = pos - 1;
int parent = child / 2;
//Here we are doing the swapping according to the node values
while(theHeap[parent] < theHeap[child] && parent > 0){
int temp = theHeap[parent];
theHeap[parent] = theHeap[child];
theHeap[child] = temp;
child = parent;
parent = child / 2 ;
}
}
}
//Function to print the values
static void print(){
for(int i = 1; i < pos; i++){
System.out.print(theHeap[i] + " ");
}
}
//Main method of the program
public static void main(String[] args){
MaxHeap();
insert(12);
insert(7);
insert(6);
insert(10);
insert(8);
insert(20);
print();
}
}
Output:
20 10 12 7 8 6
Min Heap
In this heap, the root node value is the minimum value among the other node values of the tree. This value is lesser than or equal to either of the child nodes. This is also a complete binary tree.
A min heap is also represented using an array. The root node of the tree will be at the position Arr [0]. For the node at the ith position,
- Arr[(i -1) / 2] is used to return the index of the parent node.
- Arr[(2 * i) + 2] is used to return the index of the right child node.
- Arr[(2 * i) + 1] is used to return the index of the left child node.
Example of Min Heap using Java programming language
//Java program to illustrate Heap Algorithm using Java
//Min Heap
//Main Class of the program
public class Main{
static int[] theHeap;
static int capacity;
static int pos;
//Function to create the array
static void MinHeap(){
pos = 1;
capacity = 10;
theHeap = new int[capacity];
}
//Function to insert the elements into the array according to the position
static void insert(int value){
if(pos == capacity){
System.out.println("Tree is overflow");
}else{
theHeap[pos++] = value;
int child = pos - 1;
int parent = child / 2;
//Here we are doing the swapping according to the node values
while(theHeap[parent] > theHeap[child] && parent > 0){
int temp = theHeap[parent];
theHeap[parent] = theHeap[child];
theHeap[child] = temp;
child = parent;
parent = child / 2 ;
}
}
}
//Function to print the values
static void print(){
for(int i = 1; i < pos; i++){
System.out.print(theHeap[i] + " ");
}
}
//Main method of the program
public static void main(String[] args){
MinHeap();
insert(12);
insert(7);
insert(6);
insert(10);
insert(8);
insert(20);
print();
}
}
Output:
6 8 7 12 10 20
Pros and Cons of Heap
The advantages of using a Heap are as follows:
- In the case of the heap, there is no limit on the memory size.
- Objects or variables created within the heap space can be accessed globally from anywhere within the application or a program.
- The memory is used efficiently while operating within a heap. This is because garbage collection is performed in the heap memory that frees up the memory occupied by an object.
- The largest and the smallest node value can be found easily using heap.
The disadvantages of using a Heap are as follows:
- As the values stored in a heap can be used globally, memory management becomes a bit difficult.
- Computations and executions take more time.
Heap vs Stack
|
Basis of comparison |
Stack |
Heap |
|
Data structure type |
This is a type of linear data structure. |
This is a type of hierarchical data structure. |
|
Implementation |
A stack is implemented in two ways – arrays and linked lists. |
Heap is implemented using trees and arrays. |
|
Memory allocation |
The memory is automatically allocated and de-allocated based on the instructions of the compiler. |
The memory is allocated and de-allocated by the programmer himself. |
|
Memory size |
The memory size cannot be changed. |
The memory size can be altered. |
|
Variable access |
Variables are accessed locally. |
Variables can be accessed globally. |
|
Management of memory |
The OS manages the memory efficiently and there is no chance of fragmentation. |
Memory is not efficiently managed and can be fragmented as the memory is allocated first and then freed. |
|
Variable size |
No resizing of variables are allowed. |
Variable resizing is allowed. |
|
Access time |
Accessing a stack frame is faster as the stack is cache-friendly and holds a small section of the memory. |
Heap frames are distributed throughout the memory so it takes time. |
Conclusion
A stack is very efficient when you are working with variables having small values. These can be local variables of a function. In this case, stack will be better than heap, and it will be faster. Moreover, the elements can be accessed faster and you do not have to worry about memory cleanup.
But, if you are working with a big array with many elements and need to allocate a larger block of memory, a heap is the best choice. This is because there is no limit on the memory size and it can be altered. The choice of the data structure depends upon your requirement.