In [1]:
%load_ext watermark
In [2]:
%watermark -a 'Sebastian Raschka' -u -d -v
Stacks are one of the basic, linear datastructures that have the characteristical 2 end points (here: a top and a base).
Stacks are also often referred to as LIFO datastructures, which stands for "last in, first out," and we can picture them as "unwashed dishes" in our sink: the first plate to remove is the last one we put there and vice versa.
The idea behind stacks sounds trivial, yet, it is a data structure that is immensely useful in a variety of applications. One example would be the "back" button of our web browser, which goes one step back in our search history upon "clicking" -- back to the last item we added to the stack. Before we look at another common example, parenthesis matching, let's implement a basic Stack class using Python lists as an illustration.
In [3]:
class Stack(object):
def __init__(self):
self.stack = []
def add(self, item):
self.stack.append(item)
def pop(self):
self.stack.pop()
def peek(self):
return self.stack[-1]
def size(self):
return len(self.stack)
Note that the addition and removal of a single item is a O(1) algorithm: it takes linear time to remove or add an item to the top of the stack. In the simple implementation above, we added 2 more convenience methods: a peek methods, which lets us look at the top of the stack (i.e., the end of the Python list self.stack) and a size method, which returns the number of elements that are currently in the stack.
In [4]:
st = Stack()
st.add('a')
st.add(1)
print('size:', st.size())
print('top element', st.peek())
st.pop()
print('size:', st.size())
print('top element', st.peek())
st.pop()
print('size:', st.size())
Another common application of stacks -- next to the "back" button example mentioned earlier -- is syntax checking; matching openining and closing parantheses (e.g., in regex, math equations, etc.) to be specific.
In [5]:
def check_parens(eq, pair=['(', ')']):
st = Stack()
matches = True
for c in eq:
if c == pair[0]:
st.add(c)
elif c == pair[1]:
if st.size():
st.pop()
else:
matches = False
break
if not matches and st.size():
matches = False
return matches
In [6]:
eq1 = '(a + b) * (c + d)'
check_parens(eq=eq1)
Out[6]:
The code above is relatively simple, yet effective. We initialize a new Stack and set the matches variables to true -- we use the latter to keep track whether the paranthesis are matched or not. Next, we use a for loop to iterate through the string. If we encounter an opening paranthesis, we add it from the stack. If we encounter a closing parenthesis, we try to remove the last opening bracket from the stack. If we encounter a closing bracket but the stack is empty, we already know that the parentheses are not matching, and we can break out the for loop early.
After we finished iterating through the string, we check if our stack is empty. If it is not, parentheses are not matching.
Here, two more examples:
In [7]:
eq2 = '(a + b) * (c + d))'
check_parens(eq=eq2)
Out[7]:
In [8]:
eq3 = 'a + b) * (c + d)'
check_parens(eq=eq3)
Out[8]:
Now, let's look at another example, where we are using a stack to convert digits from the decimal into the binary system. For example, the decimal number 135 would be represented as the number 10000111 in the binary system, since
$$1 \times 2^7 + 0 \times 2^6 + 0 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 135.$$
In [9]:
def decimal_to_binary(number):
st = Stack()
while number > 0:
remainder = number % 2
st.add(remainder)
number = number // 2
binary = ''
while st.size():
binary += str(st.peek())
st.pop()
return binary
Our conversion function is simple, we iteratively divide the integer number by 2 until we arrive at 0, and for each division, we add the remainder (a 0 or 1) to the stack. Finally, we remove the items one by one from the stack to build a string notation of the binary number.
In [10]:
decimal_to_binary(135)
Out[10]:
Finally, let's walk through the solution step by step to make sure we understood it correctly:
1.
1. 135 % 2 = 1
2. add remainder 1 to stack -> [1]
3. 135 // 2 = 67
2.
1. 67 % 2 = 1
2. add remainder 1 to stack -> [1, 1]
3. 67 // 2 = 33
3.
1. 33 % 2 = 1
2. add remainder 1 to stack -> [1, 1, 1]
3. 33 // 2 = 16
4.
1. 16 % 2 = 0
2. add remainder 0 to stack -> [1, 1, 1, 0]
3. 16 // 2 = 8
5.
1. 8 % 2 = 0
2. add remainder 0 to stack -> [1, 1, 1, 0, 0]
3. 8 // 2 = 4
6.
1. 4 % 2 = 0
2. add remainder 0 to stack -> [1, 1, 1, 0, 0, 0]
3. 4 // 2 = 2
7.
1. 2 % 2 = 0
2. add remainder 0 to stack -> [1, 1, 1, 0, 0, 0, 0]
3. 2 // 2 = 1
8.
1. 1 % 2 = 1
2. add remainder 1 to stack -> [1, 1, 1, 0, 0, 0, 0, 1]
3. 1 // 2 = 0