Data Structures - Stack

Data Structures - Stack

·

2 min read

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Think of it like a stack of cups in a cafeteria, where the last cup placed on top is the first to be taken off.

Let's see how we can implement a stack in Python.

from typing import Any, Optional

class Stack:
    def __init__(self) -> None:
        self.items: list = []

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

    def size(self) -> int:
        return len(self.items)

    def push(self, item: Any) -> None:
        self.items.insert(0, item)

    def pop(self) -> Optional[Any]:
        if not self.is_empty():
            return self.items.pop(0)
        else:
            return None

    def peek(self) -> Optional[Any]:
        if not self.is_empty():
            return self.items[0]
        else:
            return None

In a stack, elements are added and removed from the same end, known as the "top" of the stack. This makes it an efficient data structure for managing function calls in a program, and for tasks like undo functionality in text editors or browser history in web browsers.

Let’s just do it. Now we implement a notepad with an undo function.

from stack import Stack
from typing import NoReturn

class Notepad:
    def __init__(self) -> None:
        self.text_stack = Stack()

    def add_text(self, text: str) -> None:
        self.text_stack.push(text)

    def undo(self) -> None:
        undone_text = self.text_stack.pop()
        if undone_text is not None:
            print("Undo:", undone_text)
        else:
            print("Nothing to undo.")

    def display_texts(self) -> None:
        remaining_texts = self.text_stack.items[::-1]
        print("Text: ", "".join(remaining_texts))

def main() -> NoReturn:
    notepad = Notepad()

    while True:
        user_input = input("Enter your text (or 'undo' to revert): ")

        if user_input.lower() == 'undo':
            notepad.undo()
        else:
            notepad.add_text(user_input)

        notepad.display_texts()

if __name__ == "__main__":
    main()
'''
Output:
Enter your text (or 'undo' to revert): hello
Text:  hello
Enter your text (or 'undo' to revert): , world
Text:  hello, world
Enter your text (or 'undo' to revert): undo
Undo: , world
Text:  hello
Enter your text (or 'undo' to revert): undo
Undo: hello
Text:  
Enter your text (or 'undo' to revert): undo
Nothing to undo.
Text:  
Enter your text (or 'undo' to revert): 
...

'''