# Stack When we start learning Data Structures and Algorithms, **Stack** is one of the first data structures we usually encounter. At first, Stack looks very simple. It basically follows one rule: > **Last In, First Out (LIFO)** But understanding why it works this way, how its operations work, and how to implement it efficiently is important because Stack appears everywhere in programming—from function calls and recursion to undo/redo operations, expression evaluation, and even browser history. In this article, we will understand Stack from the basics and implement it mainly using **Python**, with a look at how the same idea can be implemented in **C**. * * * ## What is a Stack? A **Stack** is a linear data structure in which elements are added and removed from the same end, called the **top**. It follows the **LIFO (Last In, First Out)** principle. Think about a stack of plates. If you place plates one on top of another: ```text ┌───────┐ │ Plate │ ← Top ├───────┤ │ Plate │ ├───────┤ │ Plate │ └───────┘ ``` The last plate you put on the stack is the first plate you can take out. The same thing happens in a Stack data structure. If we insert: ```text 10 → 20 → 30 ``` our Stack looks like: ![](https://cdn.hashnode.com/uploads/covers/6950e81e2f9daf13464777e3/44b707a4-962b-4573-b826-37d8e5695f56.png align="center") When we remove an element, `30` is removed first. This is why Stack is called **LIFO**. * * * # Basic Operations of a Stack A Stack mainly has three important operations: ### 1\. Push **Push** adds an element to the top of the Stack. ```text Push(10) 10 ``` Then: ```text Push(20) 20 ← Top 10 ``` Then: ```text Push(30) 30 ← Top 20 10 ``` * * * ### 2\. Pop **Pop** removes the element from the top of the Stack. If our Stack is: ```text 30 ← Top 20 10 ``` and we perform: ```text Pop() ``` `30` is removed: ```text 20 ← Top 10 ``` The important thing to remember is that **Pop usually returns the removed element as well**. * * * ### 3\. Peek **Peek** returns the element at the top without removing it. For example: ```text 30 ← Top 20 10 ``` Calling: ```text Peek() ``` returns: ```text 30 ``` but the Stack remains: ```text 30 ← Top 20 10 ``` * * * # Stack Overflow and Stack Underflow There are two common problems associated with Stack. ## Stack Overflow Stack Overflow happens when we try to insert an element into a Stack that has reached its maximum capacity. For example, suppose a Stack can store only 3 elements: ```text 30 20 10 ``` Trying to perform: ```text Push(40) ``` would cause **Stack Overflow** in a fixed-size implementation. In Python lists, this generally isn't something we need to manually handle because Python lists can dynamically grow. But i C, C++ languages the arrays need to be declared with a specific size * * * ## Stack Underflow Stack Underflow happens when we try to remove an element from an empty Stack. For example: ```text Stack = [] ``` Calling: ```text Pop() ``` would result in an underflow condition. This is why a good Stack implementation checks whether the Stack is empty before performing `Pop` or `Peek`. * * * # Implementing Stack in Python Python already provides a very convenient way to implement a Stack using a list. The **end of the list** can be treated as the top of our Stack. ```python class Stack: def __init__(self): self.s = [] def push(self, value): self.s.append(value) def peek(self): if len(self.s) == 0: print("The stack is empty") return return self.s[-1] def pop(self): if len(self.s) == 0: print("The stack is empty") return return self.s.pop() ``` Let's understand this step by step. * * * ## Creating the Stack ```python def __init__(self): self.s = [] ``` When we create a Stack object, an empty Python list is created. For example: ```python stack = Stack() ``` Initially: ```text s = [] ``` * * * ## Push Operation ```python def push(self, value): self.s.append(value) ``` We use `append()` to add the element to the end of the list. For example: ```python stack.push(10) stack.push(20) stack.push(30) ``` The internal list becomes: ```text [10, 20, 30] ``` We treat `30` as the top. ```text 30 ← Top 20 10 ``` * * * ## Peek Operation ```python return self.s[-1] ``` Python allows negative indexing. `-1` refers to the last element of a list. So: ```python self.s[-1] ``` returns the top element without removing it. because of: ```plaintext pyhton indexing looks like; positive index 0 1 2 3 4 5 10 20 30 40 50 60 negative index -6 -5 -4 -3 -2 -1 ^ | Top ``` * * * ## Pop Operation ```python return self.s.pop() ``` Python's `pop()` removes and returns the last element. For example: ```python stack = Stack() stack.push(10) stack.push(20) stack.push(30) print(stack.pop()) ``` Output: ```text 30 ``` The Stack now contains: ```text 20 ← Top 10 ``` > Note: (method) def pop( index: SupportsIndex = -1, / ) -> Any > > Remove and return item at index (default last). > > Raises IndexError if list is empty or index is out of range. > > > The default of pop() will always points at index = -1 * * * # Why Use the End of the List? You might wonder why we don't insert elements at index `0`. For example: ```python self.s.insert(0, value) ``` and remove them using: ```python self.s.pop(0) ``` This works logically, but it isn't efficient. When we insert or remove an element from the beginning of a Python list, the other elements may need to be shifted. Therefore, these operations take **O(n)** time. Instead, we use: ```python append() pop() ``` at the end of the list. These operations are **O(1) amortized**. So our Stack implementation becomes much more efficient. * * * # Time Complexity of Stack Operations in Python For the list-based implementation: | Operation | Time Complexity | | --- | --- | | Push | O(1) amortized | | Pop | O(1) | | Peek | O(1) | | Checking Empty | O(1) | | Space | O(n) | This is exactly what we generally want from a Stack. * * * # A Complete Example Here is a simple example using all three operations: ```python stack = Stack() stack.push(10) stack.push(20) stack.push(30) print("Top:", stack.peek()) print("Removed:", stack.pop()) print("Removed:", stack.pop()) print("Top:", stack.peek()) ``` Output: ```text Top: 30 Removed: 30 Removed: 20 Top: 10 ``` Notice how the elements come out in reverse order: ```text Input: 10 → 20 → 30 Output: 30 → 20 → 10 ``` That's LIFO in action. * * * # Implementing Stack in C Python makes Stack implementation very easy because its list can grow dynamically. In C, we usually implement a Stack using an **array** and keep track of the top using an integer variable. For example: ```c #include #define MAX 100 int stack[MAX]; int top = -1; void push(int value) { if (top == MAX - 1) { printf("Stack Overflow\n"); return; } top++; stack[top] = value; } int pop() { if (top == -1) { printf("Stack Underflow\n"); return -1; } return stack[top--]; } int peek() { if (top == -1) { printf("Stack is empty\n"); return -1; } return stack[top]; } ``` Here, `top = -1` means the Stack is initially empty. When we perform: ```c push(10); ``` `top` becomes `0`: ```text Index: 0 Value: 10 ``` After: ```c push(20); push(30); ``` we have: ```text Index: 0 1 2 Value: 10 20 30 ↑ top ``` When we call: ```c pop(); ``` the element at `top` is returned and `top` is decreased. This gives us the same LIFO behavior as our Python implementation. * * * # Stack Using Linked List A Stack can also be implemented using a **Linked List**. In that implementation, the head of the linked list is generally treated as the top of the Stack. For example: ```text Top ↓ 30 → 20 → 10 → NULL ``` A `push` operation adds a node at the beginning, while `pop` removes the first node. This is useful when we don't want a fixed maximum capacity like a traditional array-based Stack. The important point is that the underlying implementation can change, but the **Stack behavior remains the same**. * * * # Real-World Applications of Stack Stacks aren't just theoretical DSA concepts. They are used in many practical situations. ### 1\. Function Calls Programming languages use a **call stack** to keep track of function calls. For example: ```text main() ↓ functionA() ↓ functionB() ``` When `functionB()` finishes, it returns first because it was the most recently called function. * * * ### 2\. Undo/Redo Text editors can maintain previous actions using stacks. For example: ```text Type A Type B Type C ``` An Undo operation can remove `C` first. * * * ### 3\. Browser History Browser navigation can be modeled using Stack-like behavior. Going back generally means returning to the most recently visited page. * * * ### 4\. Recursion Recursion heavily relies on the call stack. For example: ```python def factorial(n): if n == 1: return 1 return n * factorial(n - 1) ``` Each recursive call is placed on the call stack until the base condition is reached. * * * ### 5\. Expression Evaluation Stacks are commonly used for: * Parentheses matching * Infix to postfix conversion * Postfix expression evaluation * Syntax parsing For example: ```text ( A + B ) ``` A Stack can help determine whether the parentheses are properly matched. * * * # Common Mistakes While Implementing Stack When implementing a Stack yourself, keep an eye on these mistakes: **1\. Removing from the wrong end** If you add elements at the end, remove them from the end as well. ```python append() pop() ``` should work together. **2\. Forgetting the empty condition** Always consider what happens when someone calls `pop()` on an empty Stack. **3\. Confusing Peek and Pop** `peek()` only looks at the top. `pop()` removes the top. **4\. Ignoring time complexity** Two implementations can behave the same way but have different performance. For example: ```python insert(0, value) pop(0) ``` works, but is less efficient than: ```python append(value) pop() ``` * * * # Final Thoughts Stack is one of the simplest data structures to understand, but it is also one of the most useful. The main idea is easy: > **The last element added is the first element removed.** Once you understand **Push, Pop, and Peek**, you have the foundation needed for many more advanced DSA problems. For Python, a list provides an efficient and simple way to implement a Stack: ```python stack.append(value) stack.pop() stack[-1] ``` But the real goal while learning DSA isn't just remembering these methods. It's understanding **why** they work, their time complexity, and how the same Stack can be implemented using arrays or linked lists in languages such as C. That understanding becomes much more valuable when we start solving actual Stack-based problems.