Stack

Operation	Best Time Complexity	Average Time Complexity	Worst Time Complexity	Memory Complexity
`Search`	`O(1)`	`O(n)`	`O(n)`	`O(1)`
`Insertion`	`O(1)`	`O(1)`	`O(1)`	`O(1)`
`Deletion`	`O(1)`	`O(1)`	`O(1)`	`O(1)`

Have you ever played a pyramid game in your childhood?

I bet if you play this pyramid, you will first fill it with circle elements and then decompose.

And the element you put the last while composing the pyramid will be the first while decomposing it. It is called LIFO: last in, first out.

Super! Now you have learned what stack is!

So, let’s learn this thing deeply.

Why is stack needed at all?

When we write an algorithm, it is essential not only to write a super algorithm itself but also to figure out how to store data so that the algorithm has the most efficient access to them.

Stack is straightforward and fast. Let’s try to understand how the stack works with an example.

Let’s imagine that we have the f() function. It works, and at one moment, it needs to call the function g(). At this point, the function f() will pop onto the stack. If the function g() in turn calls the function p(), then the function g() is stored on the stack after the function f().

When the function p() finishes its work, we return to the stack and complete the function g(). And then, as the function g() finalizes, we get the last f() function from the stack.

When an element is put in the stack, the action is called pop, and when the element is put out of the stack, the action is called a push.

Advantages	Disadvantages
Stack helps in managing data that follows the LIFO technique;	Stack memory is of limited size;
Stacks are be used for systematic Memory Management;	The total of size of the stack must be defined before;
Stack cleans up the objects automatically;	If too many objects are created then it can lead to stack overflow;
Stack allows control over memory allocation and deallocation;	Random accessing is not possible in stack;
Stacks are more secure and reliable as they do not get corrupted easily.	If the stack falls outside the memory it can lead to abnormal termination.

Все було зрозуміло?

Секція 2. Розділ 1