Get startedGet started for free

Working with stacks

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!