Creating Stacks With .append()

00:00 In this lesson, you’ll start a look at using lists with the .append() method and other list methods to implement common data structures. But let’s start with some definitions.

00:12 A data type is a type along with a collection of operations to manipulate the type. An abstract data type is a specification of a data type in a particular language, but not specifying exactly how the code should be written to implement its operations.

00:30 And a data structure is an implementation of an abstract data type. There are many data structures, but in these next two lessons, you’ll be looking at stacks and queues.

00:43 Let’s start with the stack. The goal here is to actually write the instructions to carry out the operations defined in the stack data type. We are going to implement the stack data structure.

00:57 So, what is a stack? Like the name suggests, a stack is a data structure where you can visualize it as items stored on top of other items. It’s often referred to as a Last-In/First-Out structure.

01:13 The first thing you put in becomes the bottom of the stack and it won’t be taken out until everything else is removed from on top of it. The two main operations of a stack are push to put a new item on the top of the stack and pop to remove the top item off of the stack.

01:32 In this lesson, you’ll use the .append() method to implement .push(), and list already comes with a .pop() method, which will perform that same action on the stack.

01:44 So, let’s take a closer look at list’s .pop() method. So create a list and now you will use the .pop() method on it. The list method .pop() can take an argument, which indicates which item from the list is to be removed.

02:02 The .pop() method also returns that item to the calling agent, assuming that it’s intended to be used as it comes off out of the list. So if you call .pop(1) on this list, the item in position 1 will be popped and returned.

02:21 We can see that the element 2 was returned. And if we look at the list, it now contains the numbers just 1 and 3.

02:31 If you use .pop() without an argument, it pops off the end of the list.

02:42 If you pop everything off

02:51 and then try again,

02:55 you’ll get an error message indicating that you tried to pop from an empty list, and there’s what that message looks like. You’re getting an IndexError.

03:07 So here is an implementation of the stack data structure, making use of .append() and .pop(). Let’s take a closer look. I’ve called this file list_stack because it’s the stack data type implemented using a list. It’s defined as a class, so it begins with the phrase class Stack:.

03:30 Its initializer doesn’t take any parameters other than the word self to refer to itself. It will just create an empty stack implemented with an empty list.

03:43 The empty list is created and saved to the attribute ._items. An underscore (_) is used to indicate that this attribute should not be accessed directly, but that the stack should only be accessed through the methods that are provided.

03:59 And here are the implementations of the stack operations. .append() is used to implement .push(). You want the top of the stack to be at the end of the list, so pushing an element to the stack means it needs to be added, or appended, to the end of the list.

04:21 .pop() is used to implement the operation .pop(). It doesn’t use a parameter since you want it to pop off the end of the list. You see a try/except block.

04:34 This is because popping off an empty stack will cause an error and you want the program to behave reasonably if that is attempted. The error you saw was an IndexError, so if this operation results in an IndexError, it will display "Empty stack".

04:55 You see two other methods implemented here. When defining a class, it’s common to implement several of what are referred to as dunder methods, whose name begin and end with double underscores (__).

05:08 Here, it’s implemented the dunder method .__len__() for length so that the len() function can be used on a stack object to see how many elements are in the stack. And the dunder method .__repr__() has been implemented to provide a way to represent this stack object in a print statement or in other contexts where its value can be displayed.

05:32 It’s often used for debugging purposes. Let’s see this in action. First, import it.

05:44 Now, create a stack,

05:49 push some things on it.

05:57 Let’s see what it looks like, get its representation, print it, and find its length.

06:10 Now, pop some things off the stack.

06:16 Again, see that the 2 was returned, and if we had saved this to a variable, we’d be able to use it.

06:25 Similarly, 1 is returned. Now the stack is empty. And if you try to call .pop() on it again, you get the empty stack message that you saw in the .pop() method.

06:41 So, there’s an implementation of a stack. Next, you’ll look at implementing another data structure, the queue.