Stack
An Abstract Data Type consisting of a collection of items with operations:
- push: insert an item
- pop: removing the most recently inserted item (and typically returning)
Items removed in LIFO order Items enter the stack at the top and are removed from the top. So, top is always pointing to the top of the stack.
Extra operations:
- size
- isEmpty
- top
Realizations of Stack ADT
- using arrays (circular)
- a2q3 of CS247 - Software Engineering Principles: stack represented as an array to store the expressions
- using linked lists
How does Stack and Heap (Memory) work?
When a process starts, it gets stack allocated things.
Modern OS will keep track of when memory is requested by a process, so that when the process dies, it will clean up that memory.
Memory leak is different from automatic garbage collection:
- Because you can have a program that doesn’t crash and continuously have memory leak. It will keep on leaking and leaking, requesting more and more memory, until the program suffocates.
- So it’s important to still detect memory leaks, even though we have automatic garbage collection, because the program might not crash, and it will just continually leak memory.
- Side note on
valgrind: What valgrind does is that it creates a fake environment. Runs the program super slowly, and everything the program requests for memory, valgrind will remember it.