How to implement a stack in Python and what data structure to choose for it?

A stack is a data structure that operates on the LIFO (Last In, First Out) principle, meaning the last added element is the first to be removed.

In Python, a list (list) can be used to implement a stack, as it has methods append() for adding an element and pop() for removing the last added element.

Example of implementing a stack with a list:

stack = []

# Adding elements
stack.append(1)
stack.append(2)
stack.append(3)

# Removing an element
top = stack.pop()  # top == 3

print(stack)  # [1, 2]

If high performance is important with a large number of operations, you can use collections.deque, which is optimized for adding and removing elements from both ends:

from collections import deque

stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)

top = stack.pop()  # 3
print(stack)  # deque([1, 2])