You are here:

Advertisement

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

If still in doubt, please reply to me.

---------- 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.

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

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.