Stack Made Easy

In this notebook, we will understand what stack is, where we interact with stack it our daily lives and how can we build a stack in Python.

Before understanding what stack is, let’s see 2 most common examples of our daily life interaction with a stack which is now an integral part of modern day lives with computers, tablets and smartphones.

Internet browsing - Suppose we are browsing the pages of a news channel CNN. Initially we are at their homepage - cnn.com, then we went to read news in the Entertainment section - cnn.com/entertainment, on this page we want to read about celebrities - cnn.comentertainment/celebrities and now we want to go back to the homepage (cnn.com) and read the news in the business world - cnn.com/business. Stack is the underlying data structure which stores our browsing history and provides a convenient way for us to go back or forward from our existing page to a page that has been visited in the past.

Undo/Redo operations - If we are writing text in word document, we can conveiently press Ctrl + Z to undo or Ctrl+Y to redo becuase we are storing the user operations in a stack so that user experience is enhanced where it becomes extremly simple to either undo a change or redo it.

We can build stack in python by 2 ways: 1. List - okay but not ideal 2. Deque - better

1. Stack using List

browsing_history_stack = [] # initialize an empty list to store browsing history

browsing_history_stack.append('cnn.com')
browsing_history_stack.append('cnn.com/entertainment')
browsing_history_stack.append('cnn.com/entertainment/celebrities')

print('browsing history: ', browsing_history_stack)

# If we want to revisit the last browsing page: use pop
print('Last page visited was: ', browsing_history_stack.pop())

# pop removes the last page and updates the browsing_history_stack
print('new browsing history: ', browsing_history_stack)

browsing history:  ['cnn.com', 'cnn.com/entertainment', 'cnn.com/entertainment/celebrities']
Last page visited was:  cnn.com/entertainment/celebrities
new browsing history:  ['cnn.com', 'cnn.com/entertainment']

Q. Why a List is not ideal for storing the browser history i.e. a Stack?

Answer History is dynamic - There is no fixed size of history. In a session, a person can browse 5 websites or 50000. There is no limit. Hence, static arrays or list cannot be used thus, dynamic array is the only option. But with dynamic array there is memory overload problem.

“The issue with using a list as a stack is that list uses dymanic array internally and when it reaches its capacity it will reallocate a big chunk of memory somewhere else in memory area and copy all the elements. For example in below diagram if a list has a capacity of 10 and we try to insert 11th element, it will not allocate new memory in a different memory region, copy all 10 elements and then insert the 11th element. So overhead here is (1) allocate new memory plus (2) copy all existing elements in new memory area.”

2. Stack using deque

Read documentation about deque here.

from collections import deque # import deque

stack = deque() # initialize a stack

dir(stack)      # read what different methods are present with a deque class object

['__add__',
 '__class__',
 '__class_getitem__',
 '__contains__',
 '__copy__',
 '__delattr__',
 '__delitem__',
 '__dir__',
 '__doc__',
 '__eq__',
 '__format__',
 '__ge__',
 '__getattribute__',
 '__getitem__',
 '__getstate__',
 '__gt__',
 '__hash__',
 '__iadd__',
 '__imul__',
 '__init__',
 '__init_subclass__',
 '__iter__',
 '__le__',
 '__len__',
 '__lt__',
 '__module__',
 '__mul__',
 '__ne__',
 '__new__',
 '__reduce__',
 '__reduce_ex__',
 '__repr__',
 '__reversed__',
 '__rmul__',
 '__setattr__',
 '__setitem__',
 '__sizeof__',
 '__str__',
 '__subclasshook__',
 'append',
 'appendleft',
 'clear',
 'copy',
 'count',
 'extend',
 'extendleft',
 'index',
 'insert',
 'maxlen',
 'pop',
 'popleft',
 'remove',
 'reverse',
 'rotate']

Notice, deque has many similar attributes to that of list like append, insert, pop, remove, index. It means using deque stack is going to be exactly same as if we are handling a list object.

stack = deque() 
# add browsing history
stack.append('cnn.com')
stack.append('cnn.com/entertainment')
stack.append('cnn.com/entertainment/celebrities')

# Use of deque is same as a list
print('browsing history: ', stack)
print('Last page visited was: ', stack.pop())
print('new browsing history: ', stack)

browsing history:  deque(['cnn.com', 'cnn.com/entertainment', 'cnn.com/entertainment/celebrities'])
Last page visited was:  cnn.com/entertainment/celebrities
new browsing history:  deque(['cnn.com', 'cnn.com/entertainment'])

Can we index in or slice a deque stack?

print(stack[1]) # indexing
print(stack[:2])# slicing

cnn.com/entertainment

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[35], line 2
      1 print(stack[1]) # indexing
----> 2 print(stack[:2])

TypeError: sequence index must be integer, not 'slice'

Wow!😮

So, with deque stacks, we can :

perform indexing ✅

but slicing ❌

Q. How to perform slicing?

Ans. Possible solutions:

1. convert stack to list. For eg: list(stack)[:2]
2. get one element at a time in the index range, aggregate and return the aggregated results

Writing a Stack class

While writing a Stack class, we first need to think what functionalities/methods we want our Stack class to support.

1. We want to add elements i.e. push
2. We want to get last element i.e. pop
3. We want to get the size of the stack (e.g. browsing history)
4. We want to see if the stack is_empty
5. We want to see the last element in the stack i.e. peek
6. get last_k_items
7. print the current stack i.e. printStack

class Stack:
    def __init__(self):
        self.container = deque()

    def push(self, item):
        self.container.append(item)
    
    def pop(self):
        return self.container.pop()
    
    def size(self):
        return len(self.container)
    
    def is_empty(self):
        return self.size()==0

    def peek(self):
        return self.container[-1]
    
    def last_k_items(self, k=5):
        return list(self.container)[-k:]
    
    def printStack(self):
        """print the stack from bottom to top """
        # make a copy because pop operation would remove elements in place
        temp = self.container.copy()
        stack_str = "\n" # initialize a string to print stack
        stack_str+="**--"
        # edge case: if stack is empty
        if len(temp)==0:
            stack_str+='\n⚠ Stack is empty'
        
        while len(temp)!=0: 
            stack_str+=f"\n{str(temp.pop())}"

        stack_str+="\n--**"
        return stack_str

browsing_stack = Stack() 
# add browsing history
browsing_stack.push('cnn.com')
browsing_stack.push('cnn.com/entertainment')
browsing_stack.push('cnn.com/entertainment/celebrities')

# Test methods
print('1. browsing history: ', browsing_stack.printStack())
print('2. Last page visited was: ', browsing_stack.pop())
print('3. new browsing history: ', browsing_stack.printStack())
print('4. Length of history: ', browsing_stack.size())
print('5. Is browsing history empty? : ', browsing_stack.is_empty())

1. browsing history:  
**--
cnn.com/entertainment/celebrities
cnn.com/entertainment
cnn.com
--**
2. Last page visited was:  cnn.com/entertainment/celebrities
3. new browsing history:  
**--
cnn.com/entertainment
cnn.com
--**
4. Length of history:  2
5. Is browsing history empty? :  False

From above we can convince easily that the time complexity of Stack is as follows:

In different languages, Stack can be implemented as follows:

Exercise-1: Write a function in python that can reverse a string using stack data structure (use the Stack class implemented above.)

reverse_string("We will conquere COVID-19") should return "91-DIVOC ereuqnoc lliw eW"

Hint: Treat each character as a browing history item. So our goal is to print browsing history in reverse order

def reverse_string(string):
    # initialize a stack
    mystack = Stack()       

    # push one character at a time
    for char in string:
        mystack.push(char)

    reversed_str = ""
    for i in range(mystack.size()):
        reversed_str+=mystack.pop()
    return reversed_str


reverse_string('We will conquere COVID-19')      

'91-DIVOC ereuqnoc lliw eW'

Exercise-2: Write a function in python that checks if paranthesis in the string are balanced or not. Possible parantheses are “{}’,”()” or “[]”.

is_balanced("({a+b})")     --> True
is_balanced("))((a+b}{")   --> False
is_balanced("((a+b))")     --> True
is_balanced("))")          --> False
is_balanced("[a+b]*(x+2y)*{gg+kk}") --> True

# This solution is probably the first solution one would think without using a Stack
def is_balanced(string):

    normal_bracket_start = '('
    curly_bracket_start = '{'
    square_bracket_start = '['

    normal_bracket_start_count = 0
    curly_bracket_start_count = 0
    square_bracket_start_count = 0

    normal_bracket_end = ')'
    curly_bracket_end = '}'
    square_bracket_end = ']'

    normal_bracket_end_count = 0
    curly_bracket_end_count = 0
    square_bracket_end_count = 0

    # if any of the 3 paranthesis is presnt - it has to start with '(', '{' or '['. If at any instant the count of 
    # any _end bracket > _start of that particular bracket, it means unbalanced.
    # Also at end, if count of _start != _end for any bracket type => unbalanced

    # let's iterate through the characters
    for char in string:
        # update the counts
        if char == normal_bracket_start:
            normal_bracket_start_count+=1
        elif char == normal_bracket_end:
            normal_bracket_end_count+=1
        elif char == curly_bracket_start:
            curly_bracket_start_count+=1
        elif char == curly_bracket_end:
            curly_bracket_end_count+=1
        elif char == square_bracket_start:
            square_bracket_start_count+=1
        elif char == square_bracket_end:
            square_bracket_end_count+=1
        
        # if at any instant count of _end bracket > _start of that particular bracket
        if normal_bracket_end_count>normal_bracket_start_count or curly_bracket_end_count>curly_bracket_start_count or square_bracket_end_count>square_bracket_start_count:
            return False

    # at end
    if normal_bracket_end_count!=normal_bracket_start_count or curly_bracket_end_count!=curly_bracket_start_count or square_bracket_end_count!=square_bracket_start_count:
        return False
    return True


# Test
print(is_balanced("({a+b})"))
print(is_balanced("))((a+b}{"))
print(is_balanced("((a+b))"))  
print(is_balanced("))"))   
print(is_balanced("[a+b]*(x+2y)*{gg+kk}"))

True
False
True
False
True

# For balanced brackets, the closing brackets would appear in a reverse order. FOr ex:
# if at start we have first normal and then curly like ( { then for closing we will first have a curly and then normal like }) ---(A)
# We can use stack, where we would store just the opening brackets and the whenever a closing bracket occurs, we pop the last element in the stack. 
# Because the last element of the stack has to be the counterpart of the closing bracket just encountered (as explained in ---(A))

def is_match(ch1, ch2):
    """ check whether the counterpart of ch1 and ch2 are same or not """
    # storing the counterparts for the closing brackets
    match_dict = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    return match_dict[ch1]==ch2

def is_balanced(string):
    stack = Stack()
    for char in string:
        # only add opening brackets to the stack
        if char=='(' or char=='{' or char=='[':
            stack.push(char)
        # if char is closing bracket
        if char==')' or char=='}' or char==']':
            # if there is no opening bracket in the stack and closing bracket starts
            if stack.size()==0:
                return False
            else:
                # pop the last element in the stack by checking if it is indeed the counter part else return False
                if not is_match(char, stack.pop()): # stack.pop() gives the last element
                    return False
    
    if stack.size()==0:
        return True
    return False
    

# Test
print(is_balanced("({a+b})"))
print(is_balanced("))((a+b}{"))
print(is_balanced("((a+b))"))  
print(is_balanced("))"))   
print(is_balanced("[a+b]*(x+2y)*{gg+kk}"))

True
False
True
False
True

######################
# code refactoring tip
######################

# Instead of writing 3 lines:
if stack.size()==0:
        return True
    return False

# simply write this 1 line:
return stack.size()==0

Resources:

Codebasics Lecture 7 on Stack