Python - DS: Stacks

Question 1

What kind of data structure is a LIFO / FILO (last in first out / first in last out)? What is push, pop, and peek?

Answer 1

Stacks mimic a physical “stack” of objects. Consider a set of gym weights. Each plate has a weight (the data). The first plate you add, or push, onto the floor is both the bottom and top of the stack. Each weight added becomes the new top of the stack. At any point, the only weight you can remove, or pop, from the stack is the top one. You can peek and read the top weight without removing it from the stack.

Question 2

Attempting to push data onto an already full stack will result in a ______. Similarly, if you attempt to pop data from an empty stack, it will result in a ______.

Answer 2

Attempting to push data onto an already full stack will result in a stack overflow. Similarly, if you attempt to pop data from an empty stack, it will result in a stack underflow.

Question 3

How are stacks implemented?

Answer 3

Stacks can be implemented using a linked list, where the null pointer is the last / top of the stack.

Question 4

What do we do if someone tries to peek() or pop()when our stack is empty?

How do we keep someone from push()ing to a stack that has already reached its limit?

How do we even know how large our stack has gotten?

Answer 4

Inside the __init__ method we can have the attributes:

self. top_item # the node currently at the top of stack
self. size # the current length of stack
self. limit # the limit to the stack’s total size

Question 5

What’s a helper method?

Answer 5

Helper methods simplify the code we’ve written by abstracting and labeling chunks of code into a new function.

Question 6

Answer 6

peek()

Question 7

Complete Stack‘s is_empty() method so that you can use it to check if a stack is empty:

Answer 7

return self.size == 0

Question 8

Which values go where in a stack’s __init__() method?

Answer 8

#1: 0
#2: None
#3: l imit

Question 9

Fill in the method name:

Answer 9

push

Question 10

This stack class method could be useful because it allows us to:

Answer 10

Check if there’s enough space to add another node.

Question 11

Fill in the method name:

Answer 11

pop

Question 12

In __init__(), what purpose does the line self.limit = limit serve?

Answer 12

It sets a limit for the number of nodes that can be added to the stack at any one time.

Question 13

Which method would this line of code belong in?

self.size -= 1

Answer 13

pop()

Question 14

True or False: You can traverse a stack through its nodes.

Answer 14

False

You can traverse a linked list through its nodes, but stacks can only view and make changes to the top node in the stack.