In the first part of this tutorial series on data structures in Python, queues were explained. Stacks follow in the second part. A stack is also a data structure that is similar to the list. But there is a significant difference: There are several rules that dictate how items must be added or removed. New elements may only be added on the top of a stack (this is the end of a list). Existing elements may only be removed from the top of a stack. So, the last element that is added is the first item to be removed again. This is called the LIFO principle (Last In, First Out). Finally, only the top element can be read. This is what a typical stack looks like:
The advantage of this data structure is the constant time for adding or removing the top element (Big-O notation: O(1)). But there is also a disadvantage: The top element can always be accessed immediately. But the other elements below cannot be accessed until all elements above them have been removed. And according to the Big-O notation, this means a O(n) value, where n stands for the number of elements in the stack.
Adding an element is called a push operation, removing an element is called a pop operation. A simple implementation of a stack can be done using a list:
# Create an empty Stack (list)
stack = []
# Add an item
stack.append(24)
stack.append(32)
stack.append(17)
stack.append(51)
stack.append(4)
# Print the items
print(stack) # -> [24, 32, 17, 51, 4]
# Remove an item
stack.pop()
print(stack) # -> [24, 32, 17, 51]The last element added with append() is the number 4, which is removed as the first element with the pop() method (Last In, First Out).
This example was taken in a slightly modified form from the official Python documentation. There you will find more information and examples of data structures in Python.
Finally, it should be noted that there are also other possibilities of implementation. For example, an implementation using a Linked List would be possible.