Stacks
We've already seen how array's work in python. We will cover a few advanced forms of this, starting with a stack.
LIFO (Last-In-First-Out) stands for elements that are added to a data structure most recently, are the first.
A stack is a datastructure to hold elements. It follows a LIFO principle.
What might this mean? Imagine you have a pile of clothes neatly layed on top of each other. On the first day you take off the clothing item on the top and wear it; at the end of the day you put it back on the top of the pile. The next day you want to wear the clothing item second from the top. To get to it, you need to first take off the one you wore yesterday before it is available. A stack is much like this. Let us build a data structure that uses python's array as a base.
We create a class Stack that initializes an array. We
use an optional argument to allow us to initialize the stack if an
array is passed in. we use method overriding to pretty print the
stack as well as accessing elements in it. Since python allows
circle indexing with negative numbers, we protect against this as it
may be confusing. Finally we implement a push method
that simply appends an element to the top of the stack.
Our implementation maps an index and mirrors its position. For example index 0 becomes index n and index 1 becones index n-1. In this way, when we get an element at index 0, we are actually getting an element at the end of the stack.
Notice how this implementation causes the last element pushed to the stack to be the first one printed.
We're not quite done with building our stack yet. We still need to
implement a method to take elements off of it, termed
pop. We also implement a helper method to know if the
stack is empty. In the following code, the stack definition is
included prior to this code.
Because the last element should be popped first, we use negative indexing to get the last element in the stack to pop it.
Way to go! Stacks are relatively straight forward. Before we learn about a
very similar data structure of queue, let's test our knowledge
with a practice question.
Practice Question
Write a method peek that returns the element on the
top of the stack without removing it from the stack.