1. Working with stacks
Let's discover stacks.
2. Stacks
Stacks follows
the LIFO ordering principle, which stands for Last-In-First-Out. That means that the
last inserted item will be the first item to be removed. We can think of a
stack of books, where
3. Stacks
we can only add a new book at the top of the stack. This is called
pushing onto the stack.
4. Stacks
We can only take a book from the top of the stack. This is called
popping from the stack.
5. Stacks
And finally, we can only read the cover of the last element of the stack. This is called
peeking from the stack.
6. Stacks - real uses
Stacks have a lot of uses, such as
the undo functionality in a word processor. We can
push onto the stack
7. Stacks - real uses
each keystroke
8. Stacks - real uses
the user
9. Stacks - real uses
types.
10. Stacks - real uses
When the user makes a mistake and wants to undo it,
11. Stacks - real uses
we pop the last inserted keystroke from the stack.
12. Stacks - real uses
Another use is a symbol checker that checks the correctness of the parentheses, square brackets, and curly braces in a program.
When we find an opening symbol,
13. Stacks - real uses
we push
14. Stacks - real uses
it into the stack, and when we find a closing symbol,
15. Stacks - real uses
we check if it matches with the opening symbol located on the top of the stack,
16. Stacks - real uses
popping it if it does.
17. Stacks - real uses
In a similar way, stacks can be used for function calls.
We can store the block of memory associated with the invocation of a function
and pop it after the execution of the function ends.
18. Stacks - implementation using singly linked lists
Stacks can be implemented
using singly linked lists. As we previously learned, linked lists have nodes.
Let's recall the Node class. It has two attributes:
19. Stacks - implementation using singly linked lists
data and next. data contains the value for the node, and next points to the next node. Now, we will implement a class
for the stack. The stack will have an attribute
20. Stacks - implementation using singly linked lists
called top that will store the last inserted node in the stack. Initially, the top node will be None.
21. Stacks - push
To push a new element onto the stack
we will implement the push method. First,
22. Stacks - push
we need to create a new_node with the data.
If the stack is not empty,
23. Stacks - push
the next node of the new_node will be the top node. Finally, whether the stack was empty or had elements,
24. Stacks - push
the top node will be the new_node.
25. Stacks - pop
To pop an element from the stack,
we can implement the following method, which will also return the value of the deleted item.
If the stack is empty,
we will return None, because there is no data.
If the stack has elements,
26. Stacks - pop
the popped_node will be the top node.
27. Stacks - pop
The new top node will be the next node of the top node,
28. Stacks - pop
and the popped_node will point to None.
29. Stacks - pop
Finally, we will return the data of the popped_node.
30. Stacks - peek
The last method
is peek, which returns the data of the last element of the stack, but does not alter the stack.
If the stack has elements,
we return the data,
and if it is empty,
we return None.
31. LifoQueue in Python
Instead of creating a stack from scratch each time, we can leverage
the LifoQueue class from
Python's queue module.
LifoQueue behaves like a stack. This is not to be confused with queues, a different type of data structure.
After importing queue,
we can create a new LifoQueue with a maxsize. If maxsize is zero, the stack will be infinite.
We can add elements using the put method,
get the size of the stack with the qsize method,
pop elements from the stack using get,
which also returns the popped element,
and check if the stack is empty, among other functionalities.
32. Let's practice!
Let's practice!