You are here:

# C++/Hi

Question
QUESTION: Can you explain me the concept of heap and stack and difference between them with proper example ?

ANSWER: In terms of data structures, heap and stack have a huge difference. See http://en.wikipedia.org/wiki/Heap_(data_structure) and http://en.wikipedia.org/wiki/Stack_(data_structure) Heap supports O(1) extract_min, O(log n) insert, O(log n) remove and O(log n) search where n is the number of elements in the heap. Therefore, heap is used where efficient extract_min is needed. Stack supports O(1) extract_recent, O(1) insert and O(n) search. Therefore stack is used where efficient extract_recent is needed.

In terms of memory allocation, C++ supports both stack and  heap allocation. Stack allocation is used when the size of memory allocation is known at compile time. For example,
The number of sides of a triangle will always be 3. So a program dealing with triangle will allocate memory as follows:

int main() {
double sides[3];
// ...
// get sides by user input or file input
cout >> "Enter the sides of triangle: ";
cin >> sides [0];
cin >> sides [1];
cin >> sides [2];

// ...
// do some computation and print the output
}

This is called stack allocation.

If instead of triangle it were a polygon, the program will be

int main() {
int nsides;
cout >> "Enter the number of sides of polygon: ";
cin >> nsides;

double sides[] = new double[nsides];
// ...
// get sides by user input or file input
cout >> "Enter the sides of polygon: ";
for(int i = 0; i < nsides; i++)
cin >> sides [i];
// ...
// do some computation and print the output
}
This is called heap allocation or dynamic allocation.

Also see http://www-ee.eng.hawaii.edu/~tep/EE150/book/chap14/subsection2.1.1.8.html

---------- FOLLOW-UP ----------

QUESTION: Hi, thanks for clearing me... I have one more doubt on stack and heap. When we allocate memory dynamically, we must have to free it(from heap), but when memory allocated on stack,why we don't care to free it? Is it getting free automatically? Please explain me memory structure for both stack and heap.What happen when a function called so many times in a program ? What happen in stack ?

I'm sorry I forgot to tell you about deallocation. Whenever memory is allocated using new, it must be deallocated using delete. Whenever there is a function call, the context of calling function is saved and stack grows to include the context of the callee function. The memory allocated on the stack may be a local variable in a function call. When this function returns the stack unwinds, deallocating stack memory. Please refer to a book on Computer Architecture for details.

C++

Volunteer

#### Amit Kumar

##### Expertise

I can answer Cplusplus language and library questions, including STL, ACE, Boost. I have a good background in Mathematics.

##### Experience

Programming in CPP for about 8 years. Industry experience of 4 years.

Education/Credentials
Bachelors and Masters in Computer Science from Indian Institute of Technology Delhi.