Introduction

Stack data structure is one of the most common and most used data structure in computer science. It could be implemented using a python list or a linked list. However, we are going to use a python list in this tutorial.

Prerequisites

• Understanding of Python list
• A Programming language, preferably python
• Object Oriented Programming (OOP) concepts
• Logical Reasoning

What is a Stack Data Structure?

In a stack, elements are accessed in a LIFO manner — Last In First Out. A user may insert objects into a stack at any time, but may only access or remove the most recently inserted object that remains (at the so-called “top” of the stack). A good analogy is a stack of plates. In this case, the fundamental operations involve the “pushing” and “popping” of plates on the stack. When we need a new plate from the dispenser, we “pop” the top plate off the stack, and when we add a plate, we “push” it down on the stack to become the new top plate.

Real World Examples of A Stack Data Structure

• Web browsers stores the address of recently visited sites in a stack, when a new address is visited, the address is pushed on top of the stack of addresses. When the user clicks the back button, the browser pops the current site and the last visited site becomes the current site.
• A stack of plates in the cafeteria.
• In text editors, editing operations are kept in a stack so that when the user performs undo operation, the most current operation is removed and the previous operation becomes the most current operation.

Stack Operations

The primary operations performed on stacks are:

• is_empty: Check if the stack is empty
• Push : Add an element to the stack
• Pop: Remove and element from the top of the stack
• Length: Return the number of items in the stack
• Peek: Get the top element in the stack without removing it

• Print Item: Prints all the items in the stack

  Using python, we are now going to implement the stack methods.

Implementation of Stack Data Structure

In order for us to implement a stack data structure, we need to implement a stack data type using the code below

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

Then we implement other functionality(operations) of the stack class.

Check if the class is empty

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

Add items to the stack

    def push(self, item):
        return self.data.append(item)

Pop item from the stack

    def pop(self):
        if self.is_empty():
            raise Exception('The Stack is Empty!')
        return self.data.pop()

Check length of items in the stack

    def __len__(self):
        return len(self.data)

Peek at an item in the stack

    def peek(self):
        if self.is_empty():
            raise Exception('There is no item to peek at')
        return self.data[-1]

Print all the items in the stack

    def print_stack(self):
        return [x for x in self.data]

Final Implementation

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

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

    def push(self, item):
        return self.data.append(item)

    def pop(self):
        if self.is_empty():
            raise Exception('The Stack is Empty!')
        return self.data.pop()

    def __len__(self):
        return len(self.data)

    def peek(self):
        if self.is_empty():
            raise Exception('There is no item to peek at')
        return self.data[-1]

    def print_stack(self):
        return [x for x in self.data]

Time Complexity of Stack Operations

Conclusion

Conclusively, we have seen how to implement a stack data structure using a python list, the different operations and their time complexity. Thanks for reading!