Implementing a stack using global variables

Stacks are a fundamental data structure in computer science, known for their Last-In-First-Out (LIFO) property. There are many ways to implement a stack. In this blog post, we will explore how to implement a stack using global variables in Python.

This approach is particularly useful for understanding the core principles of stack operations without relying on built-in libraries or classes, and it is especially helpful for beginners who are just starting to learn data structures.

Understanding Stacks

A stack is a linear data structure, which means that each element is adjacent to the next and previous elements. A stack follows the LIFO order, meaning that the last element added to the stack will be the first one to be removed.

The primary operations of a stack are:

• Push: Add an element to the top of the stack.

• Pop: Remove and return the top element of the stack.

• Peek: Return the top element of the stack without removing it.

• IsEmpty: Check if the stack is empty.
  

Let's talk about stacks in Python. A stack is basically a concept, which means that we use a list and only apply the above operations—push, pop, peek, and is_empty—on it.

Revising Key Python Concepts

Before we start implementing a stack, let's revise some essential Python concepts: lists, the None keyword, the global keyword, line breaks, and try and except statements.

Lists

A list is a versatile data structure in Python that allows you to store a collection of items in a single variable. Lists are ordered, changeable, and allow duplicate elements.

# Creating a list
my_list = [1, 2, 3, 4, 5]

# Accessing elements using index, remember index starts from 0
print(my_list[0])  # Output: 1

# Adding elements
my_list.append(6)

# Removing the last element
my_list.pop()

# Slicing
print(my_list[1:3])  # Output: [2, 4]

The None Keyword

The None keyword is used to define a null value or a variable with no value in Python. It is often used to represent the absence of a value or a null value.

# Using None, so we say x variable has no value
x = None

if x is None:
# We check if x has no value then this condition is true
    print("The variable has no value.")

There is a difference between 0 and None. 0 is a number value whereas None means absence of a value.

This is just a reminder to take breaks when learning something new!!

This is just a reminder to take breaks when learning something new!!

Local Scope

A variable declared inside a function is said to have a local scope. This means that the variable is only accessible within the function where it was declared.

Imagine your house has several rooms. Each room has its own items. The toys inside your bedroom are only accessible when you're in the bedroom. No one in the kitchen or living room can see or use your bedroom toys.

Example: Your action figures are in your bedroom. Only you can play with them when you're in the bedroom.

def my_function():
    local_var = "I'm local"
	# as we defined local_var inside the function
	# we can only use it inside the function
    print(local_var)

# Trying to access local_var outside its scope will result in an error
# print(local_var)  
# This line will cause a NameError because we are trying to play with the toy that is in the bedroom but we are in the living room.

In the example above, local_var is a local variable and can only be accessed within my_function.

Global Scope

A variable declared outside of any function is said to have a global scope. This means that the variable is accessible throughout the entire program, both inside and outside of functions.

Some items are placed in the common areas of the house, like the living room. These items are accessible to everyone, no matter which room they are in. Anyone can see and use them.

Example: The family photo album is in the living room. Anyone in the house can look at it, whether they're in the kitchen, bedroom, or living room.

global_var = "I'm everywhere"

def my_function():
    print(global_var) # Even in a function we can use global variable

my_function()
print(global_var)

In the example above, global_var is a global variable and can be accessed both inside my_function and outside of it.

The global Keyword

Sometimes, you may want to modify a global variable inside a function. To do this, you use the global keyword. The global keyword is used to modify a variable outside the current scope. It is used to create or modify a global variable inside a function.

Sometimes, you need to take an item from the living room into your bedroom and use it or change it. When you do this, you're borrowing the item from the common area and making it accessible in your private space.

Example: You take the family photo album from the living room to your bedroom to add new pictures. After you're done, you put it back in the living room. Now, even though you added pictures in your bedroom, everyone in the house can still see and use the updated photo album in the living room.

# Global variable
counter = 0

def increment():
    global counter
	# with only the global keyword we can change a global variable
    counter += 1

increment()
print(counter)  # Output: 1

Scope with a Code Block

# Global variable
message = "Hello, World!"

def greet():
    # Local variable
    local_message = "Hello from the local scope!"
    print(local_message)  # Accessing local variable
    print(message)  # Accessing global variable

def modify_global():
    global message
    message = "Hello, Universe!"

greet()
print(message)  # Output: Hello, World!

modify_global()
print(message)  # Output: Hello, Universe!

In this example:

• message is a global variable, accessible inside and outside functions.

• local_message is a local variable, accessible only within the greet function.

• The global keyword in the modify_global function allows the function to modify the global variable message.

Line Breaks

Line breaks in Python can be created using the newline character (\n). They are used to improve the readability of strings by splitting them across multiple lines.

# Using line breaks
multi_line_string = "This is the first line.\nThis is the second line."
print(multi_line_string)

# Output
# This is the first line. (Because of \n we had a line break and went to a different line)
# This is the second line

try and except Statements

The try and except statements are used for exception handling in Python. They allow you to catch and handle errors gracefully, preventing your program from crashing unexpectedly.

# Using try and except
try:
    result = 10 / 0
	# First the program will try to do 10/0 but it will give an error as nothing should be divided by 0 

	# so the try block fails and because only try block fails except block runs and prints Cannot divide by zero
except ZeroDivisionError:
    print("Cannot divide by zero!")

# Similar thing will happen with the next try-except

try:
    my_list = [1, 2, 3]
    print(my_list[5])
except IndexError:
    print("Index out of range!")

Take a break!

File Handling

# Example file content:
# line1: Hello, world!
# line2: Python is great.
# line3: Let's learn more.

# Open a file for reading
with open('example.txt', 'r') as file:
    # Iterate through each line in the file
    for line in file:
        # Remove leading and trailing whitespace from the line
        stripped_line = line.strip()
        
        # Check if the line is not empty
        if not stripped_line:
            continue
        
        # Split the line into words
        words = stripped_line.split()
        
        # Print each word
        for word in words:
            print(word)

1. with open('example.txt', 'r') as file:

This line opens the file named 'example.txt' in read mode ('r').

The 'with' statement ensures that the file is properly closed after its suite finishes automatically.

2. for line in file:

This iterates through each line in the file.

3. stripped_line = line.strip():

The strip() method removes any leading and trailing whitespace (including newlines) from the line. For example the line is " My name is Batman ".

Then stripped_line becomes "My name is Batman"

4. if not stripped_line:

The not keyword is used to check if stripped_line is empty. If the line is empty after stripping (e.g., it is " "), then not stripped_line evaluates to True. When this condition is True, the continue keyword is executed to skip the current iteration and move to the next line.

Analogy: You can think of the not keyword as a NOT gate in logic, which inverts the boolean value: True becomes False and vice versa.

5. words = stripped_line.split():

The split() method splits the stripped line into a list of words, using whitespace as the default delimiter. Our stripped_line was "My name is Batman", with the help of split() function words will become

words = ["My", "name", "is", "Batman"]

Note : That stripped_line was a string, but when we used split() it gave back a list of words separated by spaces. What if we wanted to separated a sentence by comma instead of white spaces.

Let's say that the sentence is "My,name,is,Batman"

Then we do words = sentence.split(",")

words = ["My", "name", "is", "Batman"]

6. for word in words:

Now we just iterates through words as it contains the words and prints it.

This is just a reminder to take breaks when learning something new!!

A reminder for break

Implementing Stack Using Global Variables

Let's dive into the implementation of a stack using global variables in Python with the help of a particular problem. We will implement a stack which we read a file on your computer and print its content in reverse.

Step 1: Define the Global Variables

First, we need to define the global variables that will hold the stack and its attributes.

# Global variables for stack

STACK_SIZE = 100
stack = [None] * STACK_SIZE
line_breaks = [None] * STACK_SIZE
top_index = -1
line_index = -1

We define a stack size of 100 ( It is not mandatory ). Basically, we are saying that our stack can hold 100 items.

Next, we create the stack initialized with None values. Initially, the stack contains only one None element. To ensure the stack has 100 elements, we multiply the initial stack by STACK_SIZE.

We don't know how many line breaks are present in the file we will read, so we create a similar structure for line breaks.

To track our position in the stack and the number of line breaks, we use two variables, top_index and line_index, initialized to -1. This is a common convention indicating that the stack is currently empty.

Step 2: Implement the Push Operation

The push function will add a word to the top of the stack if there is space available in the stack.

def push(word):
    global top_index
    if top_index < STACK_SIZE - 1:
        top_index += 1
        stack[top_index] = word
    else:
        print("Stack overflow")

We define the push function, which takes an argument word. We use the global keyword because top_index is a global variable, and we need to modify it inside the function.

Next we have the condition if top_index < STACK_SIZE - 1. We need this to check if there is space inside our stack as we said we will only hold 100 items.

But why are we doing STACK_SIZE -1 and why not just STACK_SIZE? This is because indexing starts from 0. For example

list = [1, 7, 9]

The length is 3

Element 1 has index 0

Element 7 has index 1

Element 9 has index 2

Total length - 1 gives us the index of the last item, so we cannot go beyond this index.

For example, in the above case, the length is 3 and 3 - 1 = 2, which is the index of the last element.

Our stack can hold 100 items (STACK_SIZE = 100).

The maximum index we can have is 100 - 1 = 99 (i.e., STACK_SIZE - 1).

Currently, top_index is -1, indicating no items in the stack.

• If we add the 1st item, top_index becomes 0.

• If we add the 2nd item, top_index becomes 1.

• If we add a total of 100 items, top_index becomes 99, which is the maximum index.

So, when we say top_index < STACK_SIZE - 1, we mean that top_index should always be less than 99 to add more items. When top_index becomes 99, it means the stack is full.

If the condition is true, it means there is space in our stack, and we can add another element. Therefore, we increase top_index by 1 and replace the corresponding None value in our stack with the actual word.

Why don't we append? Because initially, our stack has 100 None elements, created by multiplying a list containing None by STACK_SIZE. Since the stack already contains 100 None elements (the maximum size), we cannot append more elements. Instead, we replace the None values with actual words.

If the condition fails then we run the else block and say that stack is full.

Step 3: Implement the push_line_break Operation

The push_line_break function will mark the position of a line break in the stack.

def push_line_break():
    global line_index
    if line_index < STACK_SIZE - 1:
        line_index += 1
        line_breaks[line_index] = top_index + 1
    else:
        print("Line break stack overflow")

Step 3 has similar explanation as Step 2 as everything is pretty much the same. There is one crucial difference

line_breaks[line_index] = top_index

This is complicated, so let's talk about it

• The line_breaks array or list stores the indices in the stack where each line ends. This helps to remember the positions of line breaks.
  

• Recording Line Breaks:

• Every time we finish reading a line and pushing its words onto the stack, we increment line_index.

• We then store the current top_index in line_breaks[line_index].

• This marks the end position of the current line in the stack.
  

• Example:

• After reading and pushing words from the first line, suppose top_index is 4.

• We set line_breaks[0] = 4, indicating that the first line ends at index 4 (after how many words) in the stack.

• When we read and push the second line, we do the same, storing the new top_index in the next position of line_breaks.

How to visualize the process

Step 4: Implement the pop Operation

The pop function will remove and return the top word of the stack if it is not empty.

def pop():
    global top_index
    if top_index >= 0:
        word = stack[top_index]
        top_index -= 1
        return word
    else:
        return None

The pop function is designed to remove and return the top word from the stack. It follows the Last-In-First-Out (LIFO) principle, where the most recently added element is the first to be removed.

global top_index is used to indicate that we are accessing and modifying the global variable top_index. This is necessary because top_index tracks the position of the top element in the stack, and we need to update it inside the function.

The condition if top_index >= 0 checks whether there are any elements in the stack. If top_index is -1, it means the stack is empty, and there are no elements to pop.

If the stack is not empty (top_index >= 0), we proceed to remove the top element.

word = stack[top_index] retrieves the element at the current top_index that is at the top of our stack.

top_index -= 1 decrements the top_index by 1, effectively removing the top element from the stack by moving the top index down. For example Lets say, we have 100 items which says max index is 99. Now, we removed an element then we have 99 items which says max index is 98.

The function returns the retrieved word, which was the top element of the stack.

If the stack was empty, the function returns None saying no value.

Step 5: Implement Additional Stack Operations

Implement the isEmpty, isLineBreak, and pop_line_break functions to manage stack operations.

def isEmpty():
    return top_index == -1
# this is basically if top_index == -1:
#                        return True
#                   else:
#                        return False


def isLineBreak():
    return line_index >= 0 and line_breaks[line_index] == top_index + 1

def pop_line_break():
    global line_index
    if line_index >= 0:
        line_index -= 1

isEmpty()

• Checks if top_index is -1.

• Returns True if the stack is empty, otherwise False.

isLineBreak()

• The function first checks if line_index is greater than or equal to 0.

• This ensures that there is at least one line break recorded.
  

• Then, it checks if the value at line_breaks[line_index] is equal to top_index + 1.

• This checks if the current position in the stack is immediately after the last recorded line break.

pop_line_break()

• Global Variable:

• global line_index is used to indicate that we are accessing and modifying the global variable line_index.

• This is necessary because line_index tracks the position of the last recorded line break, and we need to update it inside the function.
  

• Condition Check:

• The function checks if line_index is greater than or equal to 0.
  

• This ensures that there is at least one line break recorded.
  

• Decrement Line Index:

• If the condition is met, line_index is decremented by 1.
  

• This effectively removes the last recorded line break by moving the index down.

You are doing great!!Just a little more

Putting It All Together

Now that we have implemented all the stack operations, let's test our stack.

def main():
    file_name = input("Enter the file name: ")
    try:
        with open(file_name, 'r') as file:
            for line in file:
                words = line.strip().split()  # Split line into words
                for word in words:
                    push(word)
                push_line_break()  # Mark the end of the line
    except FileNotFoundError:
        print("Error: File not found")
        return

    while not isEmpty():
        if isLineBreak():
            print()  # Print a newline
            pop_line_break()
        else:
            print(pop(), end=' ')
    print()  # Ensure the last line ends properly

if __name__ == "__main__":
    main()

1. Getting the File Name:

file_name = input("Enter the file name: ")

• This line prompts the user to enter the name of the text file to be processed. The entered file name is stored in the variable file_name.
  

2. Opening the File and Handling Errors:

try:
    with open(file_name, 'r') as file:

• This block attempts to open the file specified by file_name in read mode ('r').

• The with statement ensures that the file is properly closed after its suite finishes, even if an exception is raised.

• The try block is used to catch any potential FileNotFoundError if the file does not exist.
  

3. Reading Lines and Processing Words:

  for line in file:
            words = line.strip().split()  # First strip then split line into words
            for word in words:
                push(word)
            push_line_break()  # Mark the end of the line

• This loop reads the file line by line.
  

• line.strip().split():

• strip() removes any leading and trailing whitespace (including newline characters) from the line.

• split() splits the stripped line into a list of words based on whitespace.
  

• For each word in the line, the push(word) function is called to add the word to the stack.
  

• After processing all words in the that one line, push_line_break() is called to add a marker indicating the end of the line. This helps preserve the line structure during reverse printing.
  

4. Handling File Not Found Error:

except FileNotFoundError:
    print("Error: File not found")
    return

• If the file specified by file_name does not exist, a FileNotFoundError is caught.

• An error message is printed to inform the user.

• The function returns early, stopping further execution.

5. Printing Words in Reverse Order:

while not isEmpty():
    if isLineBreak():
        print()  # Print a newline
        pop_line_break()
    else:
        print(pop(), end=' ')

• This loop continues until the stack is empty.

• isEmpty() checks if the stack is empty. If not, the loop continues.
  

• isLineBreak() checks if the current position in the stack corresponds to a line break marker.

• If a line break marker is found, print() is called to print a newline character.

• pop_line_break() removes the marker from the line_breaks stack.
  

• If no line break marker is found, pop() is called to remove and return the top word from the stack, which is then printed followed by a space (end=' ').
  

6. Ensuring the Last Line Ends Properly:

print()  # Ensure the last line ends properly

• This print() statement ensures that after the loop ends, the last line of output ends properly with a newline character.
  

7. Running the Main Function:

if __name__ == "__main__":
    main()

• This is a standard boilerplate in Python scripts to ensure that the main() function runs in the python file it has been defined in.

Conclusion

In this blog post, we have demonstrated how to implement a stack using global variables in Python. This approach provides a clear and straightforward way to understand the basic operations of a stack.

While using global variables is not always recommended for larger projects due to potential side effects, it serves as a valuable learning tool for grasping the fundamentals of data structures.

Feel free to experiment with the code and modify it to suit your needs. Understanding how to implement basic data structures from scratch is a crucial step towards becoming a proficient programmer. Happy coding!