What is a stack?

Key takeaways:
The Last-In-First-Out (LIFO) attribute is present in the stack, a linear data structure.
The last added element becomes the “top” of the stack.
Only one end of a stack can have elements added or removed.
An element is inserted to the top of the stack via a push operation.
The top element of the stack is removed and returned by the pop operation.
The top element is retrieved via a peek operation without being removed.
To see if the stack is empty, use the is_empty function.
The number of elements in the stack is returned by the size procedure.
The display action tells if the stack is empty or displays every element in it.
Applications include Depth First Search (DFS), recursion, infix-to-postfix conversion, postfix evaluation, and balanced parenthesis testing.

In a stack, the last added element is removed first, following the LIFO principle. Stack exhibits the Last-In-First-Out (LIFO) property. This means that the last element inserted in a stack, is the first one that can be extracted from it. The “top” of a stack is the last element that was inserted in it.

Stacks and queues are both linear data structures, but they differ in how elements are inserted and removed. The stack has only one end from which elements can be inserted and removed, whereas the queue has two.

How does it work?

Let’s illustrate the working of a stack.

`push()` operation

The illustration below demonstrates how elements can be inserted in a stack:

The pop() operation "pops out" the element at the top of the stack. However, an edge case that needs to be handled here is to return None when the stack is empty. That is what the is_empty() function checks. If the length of self.items is 0, it returns true - indicating that the stack is empty.

`peek()` operation

Another operation very commonly used with the stack is the peek() operation. Which simply tells us what element is sitting on top of the stack without popping it from the array. Here’s what the code looks like:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop() if not self.is_empty() else None

    def peek(self):
        return self.items[-1] if not self.is_empty() else None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

    def display(self):
        if self.is_empty():
            print("Stack is empty!")
        else:
            print("Stack elements:", self.items)



# Example usage:
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
stack.display()  # Output: Stack elements: [10, 20, 30]
print(stack.pop())  # Output: 30
stack.display()  # Output: Stack elements: [10, 20]
print(stack.peek())  # Output: 20
print("Total items:", stack.size())  # Output: Total items: 2

The code above includes the following additional operations:

Lines 17–18: The size() method returns the length of the stack.
Lines 20–24: The display() method simply prints the stack if there are elements in it. Otherwise, it prints the message "Stack is empty!".

Furthermore, toward the end of the file, there is code to test out the operations defined in the class. Make sure to change the values to see for yourself how the stack works!

Applications of the stack

Here are some very common applications where the stack data structure is utilized.

Balanced parenthesis: Used in compilers, interpreters, and expression evaluation to ensure the correct opening and closing of brackets in code or mathematical expressions.
Infix to Postfix conversion: Simplifies expression evaluation by removing the need for operator precedence and associativity rules, often used in calculators and compilers.
Postfix evaluation: Efficiently evaluates expressions in postfix (Reverse Polish Notation), ideal for stack-based calculations in compilers and interpreters.
Recursion: Solves problems by breaking them into smaller subproblems, commonly used in algorithms like factorial computation, tree traversal, and divide-and-conquer techniques.
Depth First Search (DFS): Explores graph or tree structures by visiting nodes deeply before backtracking, widely used in pathfinding, maze-solving, and network analysis.

Master the art of coding with “Data Structures and Algorithms in Python.” Gain practical experience and insights to solve real-world problems and excel in interviews with structured lessons and exercises.

Conclusion

A stack is a fundamental data structure that follows the Last-In-First-Out (LIFO) principle, where elements are added and removed from the top. Key operations include push, pop, peek, and size. Stacks are used in various applications, such as balanced parenthesis checking, expression evaluation, recursion, and Depth First Search (DFS). Understanding stacks is essential for solving many computational problems efficiently.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What is in a stack?

A stack contains a collection of elements arranged in a Last-In-First-Out (LIFO) order. The elements can be of any type, but they all have to be of the same type.

What is the difference between a stack and a linked list?

A stack follows the LIFO principle for element access, while a linked list allows sequential access with flexible insertion and deletion at any point.