# Stack

### What is a stack? (LIFO)

A `Stack`

is a data structure with two key functions *push* and *pop*. The *push* function will insert an item onto the top of the stack and a *pop* function will remove an item at the top of the stack.

Stacks operate on a *Last In First Out* basis meaning that the most recently pushed item will be the next one to be returned when popped.

This can be visualized as putting chips back into a Pringles can. When you need to take one out the last one in goes out first.

Another example is the browser back and forward button. Hitting the back arrow *pops* the most recently visited website off your history and returns it to the main screen.

Operation | Stack State - Top of the Stack is on the right |
---|---|

Initialize Empty stack | [] |

stack.push(1) | [1] |

stack.push(2) | [1,2] |

stack.push(2) | [1,2] |

stack.push(3) | [1,2,3] |

stack.pop() | [1,2]: returns 3 |

stack.pop() | [1]: returns 2 |

stack.push(4) | [1,4] |

stack.push(5) | [1,4,5] |

stack.pop() | [1,4]: returns 5 |

### Python list

The built in `list`

data-type supports all stack operations. The only difference is that the `.push()`

is called `.append()`

```
my_stack = []
my_stack.append(1)
my_stack.append(2)
my_stack.append(3)
my_stack.pop() #3
my_stack.pop() #2
my_stack.append(4)
my_stack.append(5)
my_stack.pop() #5
```

### Implementing a stack in Python

Under the hood stacks are implemented using `linked-lists`

in Python.

Top of the stack | ||
---|---|---|

self.head | 5 | self.head points to the top of the stack |

self.head.next | 4 | When removing element from stack, set self.head = self.head.next |

3 | ||

2 | ||

1 |

Stack class implementation, this uses a Python list under the hood.

```
class Stack():
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def get_items(self):
return self.items
def is_empty(self):
return self.items == []
# Returns the top most element of the stack or last popped on item, this is
# the last element on a list.
def peek(self):
if not self.is_empty():
return self.items[-1]
if __name__ == "__main__":
s1 = Stack()
s1.push("a")
s1.push("b")
s1.push("c")
print("peeking", s1.peek())
s1.pop()
print(s1.get_items())
print(s1.is_empty())
```

### Time Complexity

Pop - O(1)

Push - O(1)

Top/peek - O(1)