Today I want to talk about a famous, basic but pretty wonderful data structure we all read in our universities or colleges.

Stack

A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack is removed first.

You can think of the stack data structure as the pile of plates on top of another.

Here, you can:

• Put a new plate on top
• Remove the top plate
• And, if you want the plate at the bottom, you must first remove all the plates on top. This is exactly how the stack data structure works.

Applications

• To reverse a word - Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.
• In compilers - Compilers use the stack to calculate the value of expressions like 2 + 4 / 5 * (7 - 9).
• In browsers - The back button in a browser saves all the URLs you have visited previously in a stack.

Key functions of a Stack

• Push: Add new element
• Pop: Remove an element from last
• Peek: Get the last element without removing it

Cherry on Top

In the following implementation instead of using built-in functions to check empty or length of stack we will use an extra variable count to keep track of these things.

Code

from typing import Type

class Stack:

    elements = []

    count = -1

    def push(self, data):
        self.elements.append(data)
        self.count += 1

    def pop(self) -> int:
        if self.isEmpty() is True:
            raise Exception('Nothing to pop!')

        self.count -= 1
        self.elements.pop()

    def peek(self):
        if self.isEmpty() is True:
            raise Exception('Cannot peek an empty stack')

        return self.elements[self.count]

    def isEmpty(self):
        return self.count < 0