What is a Stack?
Formal Definition
A Stack is a linear data structure that saves data in LIFO (Last In / First Out) order. A stack has two main operations — push and pop. It is the opposite of a queue.
What does this mean?
A stack is basically a list that only has two operations — adding an item to the top of the list (”pushing”) and removing the top item in the stack (”popping”). When you “push” an item to the stack, it goes to the top of the list. When you “pop” an item from the stack, you remove the item at the top of the list.
The “top” of the list can be either the front/first item or the back/last item of the list. It all depends on how you look at it. In most cases, you’ll want to use the last item of the list as the “top” of your stack because this works well with python lists’ append and pop methods
A great way to think of a stack is the undo function — your recent changes are added to the stack, and when you press undo, the most recent change is removed from the stack. You can also think of a stack a box — you put items into the box, and in order to remove the items on the bottom, you have to remove the items on the top first.
Simple Way to Make a Stack
Here we define a function called Stack and make a list inside called stack_list. Inside that list we add some values in this case 100, 200 and 300. After we print the value we start removing values from the end of the list which in this case we would remove 300 first, then 200, and lastly 100 until we return an empty list.
The biggest issue we face while implementing stacks is as the data grows so does its runtime. As the stack grows bigger, Python will have to do some memory work to make the data fit. This can lead to longer wait times for data to append.
Visualization:
def Stack(): # Make Stack List stack_list = [] # Appending Data To Stack List stack_list.append(100) stack_list.append(200) stack_list.append(300) print(stack_list) #Removes Last Item "Last In First Out" stack_list.pop() stack_list.pop() stack_list.pop() # Returns list return stack_list a = Stack() print(a)
Python Cleaner Implementation
Below is the same thing as above but it uses classes.
class Stack: def __init__(self): # Make List self.stack_list = [] def appending(self, item): # Checks to see if there are any duplicates in list if item in self.stack_list: #If so it returns error return "Value Already Exists" else: self.stack_list.append(item) def pops(self): # Checks to see if list is empty if len(self.stack_list) != 0: # if it isn’t empty it removes last value return self.stack_list.pop() else: return "List is Empty" Check_Stack = Stack() #Should add value to list Check_Stack.appending(100) Check_Stack.appending(200) Check_Stack.appending(300) #Should print 300 and then 200 print(Check_Stack.pops())
View code on GitHub.
Practice
Ever wanted to reverse a word a harder way? Well, look no further than this problem that puts your knowledge of Stacks to the test in order to solve a problem that is already solvable by python builtins!
Your job is to reverse a string by using a stack, adding every letter in the string (starting from the beginning of the string) into the stack, and then popping every letter from the stack.
If done correctly, this will result in a reversed version of the string.
Starter code is given.
Previous Section
2.3 Linked ListsCopyright © 2021 Code 4 Tomorrow. All rights reserved.
The code in this course is licensed under the MIT License.
If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.