Introduction to Stack data structure

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. A stack can be considered a list of elements where only the top element can be accessed and removed.

A stack has two main operations:

1. Push: This operation adds an element to the top of the stack.
2. Pop: This operation removes the top element from the stack.

In addition to these two basic operations, there are a few other commonly used operations:

1. IsEmpty: This operation checks whether the stack is empty.
2. Size: This operation returns the number of elements in the stack.

Stacks are often implemented using arrays or linked lists. The choice of implementation depends on the specific requirements of the application.

Stacks are used in various algorithms such as depth-first search, and parsing expressions, also it can be used in solving problems like balanced parentheses, conversion of infix to postfix and prefix expressions, and many more.

Implement Stack in Python using List

We will be implementing the following function in the stack class

Stack:
    def __init__(self):
        self.items = []
   
    def push(self, item):
        self.items.append(item)
   
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
   
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
   
    def is_empty(self):
        return len(self.items) == 0

Here’s how you would use the stack:

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek()) 
print(stack.pop())  
print(stack.pop())  
print(stack.is_empty()) 

The following will be the output

3
3
2
False

Notice the use of append and pop methods from python lists which are used to insert and remove elements from the list respectively.

Keep in mind that this is a basic implementation, and Python’s built-in list is not the most efficient data structure for implementing a stack. For more complex use cases, consider using collections. deque instead.

Use Cases of Stack 

​​A stack is a data structure that follows the Last In First Out (LIFO) principle. Some everyday use cases of stacks include

1. Undo and Redo operations in text editors and image editors
2. Back and Forward navigation in web browsers
3. Keeping track of function calls in a program (call stack)
4. Expression evaluation and syntax parsing
5. Implementing algorithms such as Depth First Search (DFS)
6. Balancing symbols in code, such as parentheses in expressions
7. The Tower of Hanoi is a classic problem where stacks are used to solve it.

Limitations of Stack 

There are several limitations of stacks as a data structure:

1. Limited accessibility: Only the top element of the stack can be accessed at any given time. All elements above must first be removed to access an element lower in the stack.
2. Fixed size: Stacks are fixed and can’t be resized dynamically. This means that if a stack is full and a new element is added, a stack overflow error will occur. On the other hand, if a stack is empty and an element is popped, a stack underflow error will occur.
3. Limited functionality: Stacks can only perform a limited set of operations, such as push, pop, and peek. It cannot be used for operations that require random access to elements, such as sorting or searching.
4. Hard to implement the extra feature: Stack works on the LIFO principle, so It’s hard to Implement extra features like sorting, searching, Reverse, etc.
5. Not suitable for extensive data set: When the data set is large, the stack may quickly become filled, and this may cause the program to run out of memory or crash.
6. No random access: Since the stack follows LIFO, we can not access any random element like other data structures such as Array, List, etc.

However, the limitations of stacks can be overcome by using other data structures, such as queues or linked lists, in conjunction with stacks.