Stacks
In this tutorial, we'll learn about Stacks.
What are Stacks?
Stacks are a simple but useful Data Structure. They're used in Programming Competitions and Job Interviews, so it is a good idea to learn about them.
In Programming, Stacks are like actual stacks of items. Imagine that you have some pancakes stacked on top of each other:
With these pancakes, you can either put some more pancakes on top of the stack, or remove the pancake on top of the stack. You can't remove or add items to the bottom of the pancakes, or the whole pile would fall. It's the same with Stacks in Programming. We call this idea/rule "First In, Last Out" (FILO), meaning that the first elements you add to the Stack will get removed last.
Stack Implementation
In Python, we can use lists to represent Stacks. Lists already come pre-built with the needed functions to make a Stack. So as an example, we'll use a browser history system to demonstrate the behavior of a Stack.
history = [1, 2, 3]
In this example, we represent our browser history with numbers. But, of course, you'd put the URL of a site as a string when you are creating an actual browser.
Then, type the following code into your program:
history.append(4)
history.append(5)
print(history.pop())
print(history)
After running the code, you'll get
5
[1, 2, 3, 4]
printed out into the terinal.
On the first two lines, we call the append method on our history list. This will add the element we pass in to the end of our list. After running these two lines of code, our history list will be [1, 2, 3, 4, 5]. First, it will add 4 to the list and then it will add 5.
Then, we have
print(history.pop())
print(history)
pop method on our history list. The pop method will remove the last item from the list and return it. So, our program will print out the 5 from the end of the list. To make sure that our code has successfully run, we print out history and it displays [1, 2, 3, 4], so we know that pop did indeed delete the last element (5) from our list.
Stacks in Competition
We've already gone over how Stacks work and how to implement one. So, now, let's go over using Stacks in Programming Competitions and Job Interview problems.
When To Use Stacks
In Programming problems, it is often useful to use Stacks when:
- Stacks Are Involved (Stacks Of Books)
- There Is A "First In Last Out" Format
Implementing Stacks in Contests
When you are using Stacks, you have two main options when it comes to implementing Stacks: creating your own Stack class or using lists, which are already built-in. Well, it's better to use your own class if you want to implement a couple of more complex features. Of course, this would use up memory so try to limit to built-in functions if you can. So, it's a good idea to just use a list most of the time.