In the realm of computing, the concept of a stack is one that cannot be overlooked. However, many people—even those in computer science—do not realize that the term "stack" actually refers to two different data structures.
A stack is a data structure where data items are arranged sequentially and can only be inserted or removed from one end, known as the top.
Key points:
- Heap: Order is arbitrary.
- Stack: Follows Last-In/First-Out (LIFO).
The difference between heap and stack:
1. **Preliminary Knowledge - Memory Allocation in Programs**
A program compiled in C/C++ occupies several parts of memory:
1. **Stack Area (stack)** – Automatically allocated and released by the compiler, it stores parameter values and local variable values. Its operation resembles the stack data structure.
2. **Heap Area (heap)** – Typically allocated and released by the programmer. If the programmer does not release it, the OS may reclaim it when the program ends. Note that this is different from the heap in data structures; however, its allocation method is similar to a linked list.
3. **Global Area (Static Area)** – Global variables and static variables are stored together. Initialized global and static variables occupy one region, while uninitialized ones occupy an adjacent region. The system releases this area after the program ends.
4. **String Constants Area** – Constant strings are stored here. The system releases this area after the program ends.
5. **Code Area** – Stores the binary code of function bodies.
2. **Example Program**
This example was written by someone else and is very detailed:
```cpp
// main.cpp
int a = 0; // Global initialized area
char *p1; // Global uninitialized area
main()
{
int b; // Stack
char s[] = "abc"; // Stack
char *p2; // Stack
char *p3 = "123456"; // "123456\0" in constant area, p3 on stack
static int c = 0; // Global (static) initialized area
p1 = (char *)malloc(10);
p2 = (char *)malloc(20);
}
```
The 10 and 20-byte regions allocated by `malloc` reside in the heap area.
```cpp
strcpy(p1, "123456"); // "123456\0" in constant area; the compiler might optimize it to share the same location as what `p3` points to.
```
3. **Practical Knowledge About Heap and Stack**
**1. Allocation Method**
- **Stack**: Automatically allocated by the system. For example, declaring a local variable like `int b` causes the system to automatically allocate space for `b` on the stack.
- **Heap**: Must be explicitly allocated by the programmer with a specified size. In C, the `malloc` function is used, e.g., `p1 = (char *)malloc(10);`. In C++, the `new` operator is used, e.g., `p2 = new char[20];`. Note that `p1` and `p2` themselves are still located on the stack.
**2. System Response After Allocation**
- **Stack**: If the remaining stack space is greater than the requested space, the system provides memory for the program. Otherwise, an exception indicating a stack overflow is raised.
- **Heap**: The operating system maintains a linked list of free memory addresses. When the system receives a request, it traverses this list to find the first heap node larger than the requested space. It removes this node from the free list, allocates the space to the program, and records the allocation size at the start address. Excess space may be returned to the free list.
**3. Size Limitations**
- **Stack**: On Windows, the stack expands downward into lower memory addresses and is a contiguous block of memory. The stack's top address and maximum capacity are predefined by the system. On Windows, the stack size is typically 2MB (or sometimes 1MB). If the requested space exceeds the remaining stack space, an overflow error occurs. Therefore, the stack offers relatively limited space.
- **Heap**: The heap expands upward into higher memory addresses and consists of non-contiguous memory regions. Since the system uses a linked list to store free memory addresses, the heap is naturally non-contiguous. The heap's size is limited by the system's available virtual memory. Thus, the heap provides more flexible and larger memory allocations.
**4. Efficiency Comparison**
- **Stack**: Automatically managed by the system, it is faster but less controllable.
- **Heap**: Allocated using `new`, it is generally slower and prone to memory fragmentation but more convenient to use. Alternatively, in Windows, `VirtualAlloc` is the most efficient way to allocate memory directly within the process's address space, though it is less convenient.
**5. Storage Content**
- **Stack**: When a function is called, the first item pushed onto the stack is the address of the next instruction in the calling function (the instruction following the function call). Then the function's parameters are pushed onto the stack (in most C compilers, parameters are pushed right-to-left), followed by the function's local variables. Static variables are not pushed onto the stack.
After the function call ends, local variables are popped off the stack first, followed by the parameters, and finally, the stack pointer is reset to point to the original address, allowing the program to continue execution from there.
- **Heap**: Typically, the size of the heap is stored in the header byte. The specific content of the heap is determined by the programmer.
**6. Access Efficiency Comparison**
```cpp
char s1[] = "aaaaaaaaaaaaaaa";
char *s2 = "bbbbbbbbbbbbbbbbb";
```
The string `"aaaaaaaaaaaaaaa"` is assigned at runtime, whereas `"bbbbbbbbbbbbbbbbb"` is determined at compile time. However, accessing arrays on the stack is faster than accessing strings pointed to by pointers (e.g., on the heap).
Example:
```cpp
#include
void main()
{
char a = 1;
char c[] = "1234567890";
char *p = "1234567890";
a = c[1];
a = p[1];
return;
}
```
Corresponding assembly code:
```
10: a = c[1];
00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]
0040106A 88 4D FC mov byte ptr [ebp-4],cl
11: a = p[1];
0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]
00401070 8A 42 01 mov al,byte ptr [edx+1]
00401073 88 45 FC mov byte ptr [ebp-4],al
```
The first method directly reads the element into the register `cl`, while the second must first load the pointer value into `edx` before reading the character, making it slower.
**7. Summary**
The difference between heap and stack can be likened to:
- Using the stack is like dining at a restaurant where you simply order food, pay, and eat. Once full, you leave without worrying about preparation or cleanup. It’s fast but less flexible.
- Using the heap is like cooking your favorite dish yourself, which is more麻烦but allows for greater customization and flexibility.
While the terms "heap" and "stack" are often used together, they refer to distinct concepts. In operating systems, they describe different memory areas, while in data structures, "heap" refers to a priority queue satisfying heap properties, and "stack" refers to a LIFO structure.
**Supplement**
A stack is a type of storage component where data is read and written without providing an address. Instead, the order of writing determines the order of reading.