Introduction to Stacks
Explore the core concepts of stacks as a linear data structure operating in Last In First Out order. Understand push and pop operations, stack overflow and underflow conditions, and implementations using arrays and linked lists. Learn to recognize problems suited for stacks such as string reversal, expression evaluation, and nested structure handling. This lesson prepares you to apply stack concepts to coding interviews and real-world tasks like undo features and browser navigation.
We'll cover the following...
About the pattern
A stack is a linear data structure that organizes and manages data in a Last In, First Out (LIFO) manner. This means the last element added to the stack is the first to be removed. Think of it like a stack of plates where you can only add or remove plates from the top.
There are two fundamental operations, push and pop, to add and remove elements while maintaining the LIFO order. Let’s delve into each operation:
push: This operation involves placing an element at the top of the stack. Whenever we push a new element onto the stack it becomes the new top element and this is why the stack grows in an upward direction.
pop: This operation involves removing the top element from the stack. The removed element is usually returned by the pop operation so that we can use or process it. After a pop operation, the element just below the one removed becomes the new top element.
The slides below are the visual demonstration of the push and pop operations:
There is some capacity associated with every stack which is nothing but the size of the stack. It is important to keep an eye on the stack’s capacity while performing the push and pop operations otherwise it results in either stack overflow or underflow.
A stack overflow occurs when we try to push an element onto a full stack. Therefore, a push operation can’t be called on a full stack. For example, if the stack has a capacity of
...