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):
...
'''