Stacks

Stack is a data structure that follows LIFO principle (Last in first out). Think of it like container in which you can put in items, and so the last item you put in, will the first one you will have to take out.

Imagine a stack of plates, the first plate you can take out, is the one at the top.

Stacks strictly follow this principle and hence the access is restricted to the top

Okay so stack is an abstract idea that can be implemented using other data structures primarily we use arrays or linked lists for it.

Top identifies the most recently pushed element

All insertions and deletion happen at the top

• push(item): Adds an item to the top.

• pop(): Removes the item from the top.

The Bottom is the oldest element still in the stack.

Lets talk about Stack Overflow, it was a place where people used to go and find fixes to their bugs before AI made us lazy. Now there traffic is so down they should call themselves Stack Underflow

Okay jokes apart , Stack overflow occurs when we try to push beyond a fixed-capacity stack’s limit. In JavaScript, the term commonly refers to excessive recursion creating more active function frames than the call stack can hold. and Stack Underflow is the error when we try to pop elements even after the stack is empty. JavaScript’s array pop() returns undefined rather than throwing an error

Core stack operations are :

push : adding element at the top

pop: Removing element from the top

isEmpty : returns a boolean where the stack is empty or not

peek: inspects the top element of the stack without removing it

size : returns the number of items in the stack

Time and Space Complexity

Implementing a Stack in JavaScript

Using an array

let stack = []

//push
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack) // [1, 2, 3]

//pop
stack.pop()
console.log(stack) // [1, 2]

//peek
console.log(stack[stack.length - 1]) // 2

Notice that we treat the end of the array as the top so that pushing and popping elements are time efficient. We can perform them

Technically we can use shift() and unshift() functions as well to add and remove elements considering we treat the start of the array as the top of the stack, but those functions require reindexing elements making them inefficient, so we avoid them

A real world application of stacks can be seen in, Function Calls and the Call Stack

When functions are called we use a call stacks to make use we handle the order in which each function has to be executed.

Consider we have nested functions that are to be executed,

A calls B
B calls C
Completion order: C → B → A

In this case our stack is [A, B, C] at the top we have C which will finish first, while B and A will be paused, waiting in the stack till C finishes. When it does we pop it out of the call stack.

One important thing to note here is that the call stack only contain active functions which have started and not finished yet.

If the functions are running sequentially and they are not overlapping each other, we don't have to pause one function and process another one. If you're running 1,000 functions sequentially, we can just put one function in, process it, pop it out, and then put another one in it. In a nested case we have to remember a function that is paused to resume it later from the stage it was paused at. Hence it has to be there in the stack.

How to identify stack problems

• Most recently added item processed first

• Nested structures

• Reversing an order

• Undoing previous actions

• Pausing one task and later resuming it

Type of questions you can find:

• Build an Array With Stack Operations

• Evaluate Reverse Polish Notation

• Exclusive Time of Functions