In the current world, new algorithms are constantly being developed to tackle complex challenges. However, the crucial role of simple algorithms in the realm of computing should not be underestimated. In this context, we will delve into two fundamental data structures. We will practically explore how to create and utilize these structures to solve real-world problems. This comprehensive guide will provide a complete understanding of the creation and implementation of these structures, bridging the gap from theory to practice.
Stack
Let's begin our journey into data structures and algorithms by studying the Stacks. This is a dynamic set that operates on the principle of Last In, First Out (LIFO). The stack data structure serves as the foundation for more complex structures such as Trees and Graphs. Its ability to orderly store data is highly useful for keeping track of paths in both previously mentioned structures, reversing text documents, browser tabs, and even processor tasks. The primary operations with the stack are Insert, Pop, Peek Top, and Empty, commonly used for inserting, deleting (which takes no arguments), checking the last element inserted in the stack and currently at the top, and verifying if the stack is empty.
The fundamental structure of a stack can be interpreted as S[1, N], where N is the maximum size of the set and represents the top of the stack, i.e., the last element inserted.
Let's start our implementation.
First we create our virtual environment and import the Numpy package to help us with implementation
mkdir DataStructure
cd DataStructure
python3 -m venv venv
source venv/bin/activate
pip install numpy
Now we will start building our Stack class by creating 3 variables.
- size -> the size of our stack
- top -> the beginning of the stack
- values -> the array that will store our elements
import numpy as np
class Stack:
def __init__(self, size):
self.__size = size
self.__top = -1
self.__values = np.empty(self.__size, dtype=int)
The first method has been designed to check whether the stack is already full. It is a straightforward approach that examines whether the index of the first element equals the stack size. This method is employed exclusively when adding new elements, and the double underscores signify that it is a private method, intended for use only within the class.
def __is_full(self):
return self.__top == self.__size - 1
Hint: The array positions starts with 0. An array with lenght equals to five has the following indices 0,1,2,3,4.
The second method has been implemented to check whether the stack is empty. This is indicated when the value of the index of the top element equals the initial value set during the creation of the class.
def __is_empty(self):
return self.__top == -1
The third method is responsible for inserting a new element into the stack. Initially, it checks if the stack is already full; if it is, it will return an exception. If the stack is not full, it increments the value of the index of the first element by 1 and adds the new element to the stack.
def push(self, value):
if self.__is_full():
raise Exception("The stack is full")
else:
self.__top += 1
self.__values[self.__top] = value
return f"the value: {value} has been entered!"
The fourth method removes the item from the top of the stack. With this method and the one before it, we implement the Last In, First Out (LIFO) principle. Initially, it checks if the stack is already empty. If it is not empty, it updates the index of the removed element. It's important to note that the stack does not erase the element itself but rather updates the index, allowing that position to be overwritten when a new element arrives.
def pop(self):
if self.__is_empty():
raise Exception("The stack is empty")
else:
self.__top -= 1
return f"the value: {self.__values[self.__top]} has been removed"
Finally, we have the method that returns the element at the top of the stack. The other elements in the stack are not visible to the user; thus, the user has visibility only of the input and output elements.
def peek_top(self):
if self.__top != -1:
return self.__values[self.__top]
else:
return -1
Now that our stack has been structured, let's explore an example of how to use this data structure.
Example usage of the Stack class
We will create an instance of the Stack class and set the size of its array to five. Subsequently, we will iterate five times in a for loop, pushing the value of each iteration onto our stack. Later, we can ascertain the last element in the stack by invoking the 'peek_top' method.
stack = Stack(5)
for x in range(5):
print(stack.push(x))
print("Top of stack is:", stack.peek_top())
The return of this test it's:
the value: 0 has been entered!
the value: 1 has been entered!
the value: 2 has been entered!
the value: 3 has been entered!
the value: 4 has been entered!
Top of stack is: 4
And if we exceed the stack size by increasing the iteration to six we will receive this Exception:
Traceback (most recent call last):
File "stack.py", line 63, in <module>
print(stack.push(x))
File "stack.py", line 31, in push
raise Exception("The stack is full")
Exception: The stack is full
We can also test removing items at the top of the list with the following code:
for _ in range(4):
print(stack.pop())
print("Top of stack is:", stack.peek_top())
Hint: We use the underscore in this iteration because we don't wanna save the value of each iteration.
The return of the pop method:
the value: 3 has been removed
the value: 2 has been removed
the value: 1 has been removed
the value: 0 has been removed
Top of stack is: 0
And in case we try to remove an element with an empty stack, we receive an exception:
Traceback (most recent call last):
File "stack.py", line 67, in <module>
print(stack.pop())
File "stack.py", line 43, in pop
raise Exception("The stack is empty")
Exception: The stack is empty
You're probably wondering "Woah, now where the hell is this used in the real world dude????"
Be patient, young padawan. The stack system is widely used in various areas of technology. You've likely encountered it in your IDE, though you might not have consciously realized it. Let's refresh your memory. Consider when you create a function in Java to add two numbers and print the result on the screen like this.
public class SumNumbers {
public static void addAndPrint(int num1, int num2) {
int result = num1 + num2;
System.out.println("Sum result: " + result);
}
public static void main(String[] args) {
int number1 = 5;
int number2 = 10;
addAndPrint(number1, number2);
}
}
If you eventually do not close a parenthesis or bracket, you will receive a compilation error similar to this.
/SumNumbers.java:11: error: ')' expected
addAndPrint(number1, number2;
^
1 error
This is possible because the compiler stores the values of the opening parentheses on a stack. When the stack is being disassembled, it expects its elements to be completely emptied. If the compiler does not find a corresponding pair for that open parenthesis, an exception will be displayed in the terminal.
We can create a stack that simulates the behavior with just a few adjustments to our original structure.
Let's change the type of array we use in this case to the Char type.
class Stack:
def __init__(self, size):
self.__size = size
self.__top = -1
self.__values = np.chararray(self.__size, unicode=True)
We will also change the peek top method just for better visualization.
def peek_top(self):
if not self.__is_empty():
return self.__values[self.__top]
else:
return None
And let's set the method is_empty as a public method.
def is_empty(self):
return self.__top == -1
Now we will create a function that receives input from the user of type string and creates an instance of the Stack class with the same size as the string entered by the user.
def validate_expression(expression):
stack = Stack(len(expression))
Next, we will iterate through the string, searching for the opening symbols of braces, brackets, and parentheses. If identified, we will add them to our stack.
for i in range(len(expression)):
ch = expression[i]
if ch in ['{', '[', '(']:
stack.push(ch)
In the same iteration, we will search, always checking if the stack is empty, for the closing symbols of braces, parentheses, and brackets. Within the first conditional, whenever we encounter one of these values, we will remove the last value inserted in the stack.
elif ch in ['}', ']', ')']:
if not stack.is_empty():
chx = str(stack.pop())
if (ch == '}' and chx != '{') or (ch == ']' and chx != '[') or (ch == ')' and chx != '('):
raise Exception(f"Error: {ch} in position {i}")
The function should look like this:
def validate_expression(expression):
stack = Stack(len(expression))
for i in range(len(expression)):
ch = expression[i]
if ch in ['{', '[', '(']:
stack.push(ch)
elif ch in ['}', ']', ')']:
if not stack.is_empty():
chx = str(stack.pop())
if (ch == '}' and chx != '{') or (ch == ']' and chx != '[') or (ch == ')' and chx != '('):
raise Exception(f"Error: {ch} in position {i}")
if not stack.is_empty():
raise Exception("Error: Unmatched opening bracket(s)")
To test our function we will receive input from the user and call the Stack class.
expression = input("Type your expression: ")
validate_expression(expression)
print("Expression is valid.")
Let's test with four inputs:
- (a)(b){c}
- a(a[b]{c(d)})
- a(b(c(d)}])
- a(b{c)
Respectively our returns are:
Expression is valid.
Expression is valid.
Traceback (most recent call last):
File "expression_validate.py", line 52, in <module>
validate_expression(expression)
File "expression_validate.py", line 47, in validate_expression
raise Exception(f"Error: {ch} in position {i}")
Exception: Error: } in position 8
Traceback (most recent call last):
File "expression_validate.py", line 52, in <module>
validate_expression(expression)
File "expression_validate.py", line 47, in validate_expression
raise Exception(f"Error: {ch} in position {i}")
Exception: Error: ) in position 5
Note that in the third and fourth entries, the last line of the Exception indicates that there is an error in positions eight and five respectively indicating that the braces were closed but not opened.
Queues
The queue, also known as a queue in English, is a dynamic set with a different principle called FIFO (First In, First Out). This approach is essential for solving complex application stress problems by organizing requests and processes based on the order in which they were created. This flow is fundamental for the orderly execution of asynchronous tasks, allowing, if the maximum capacity of the software or function is exceeded, surplus processes to be temporarily stored in data such as a cache. As executions occur, new processes in waiting are executed, ensuring the order of tasks. Various complex libraries, such as Celery, Kombu, Apache Kafka, and others, have been developed based on this data structure.
The queue shares some operations with the stack, such as Is empty and Is full. However, it also has other methods, such as Enqueue and Dequeue, which involve adding an item to the end of the queue and removing an item from the beginning of the queue, respectively.
There are two main types of queues, commonly referred to as linear queue and circular queue. In practice, the difference between them lies in the fact that a linear queue requires rearranging all positions when an element is added or removed. In the case of a circular queue, the indices indicating the first and last elements are repositioned. This approach has a direct impact on the algorithm's performance.In this section we will study about circular queues.
1) Let's start by visualizing how enqueue operations would work. We'll insert the first item into the queue, and this element will have the same indices referencing both the first and last positions.
2) The second enqueue operation will add an element to the queue structure, thereby shifting the index that references the last position to the right.
3) The third enqueue operation, again, will add an element to the queue structure, thereby shifting the index that references the last position to the right.
4) The fourth enqueue operation will add an element to the queue structure, causing the index referencing the last position to shift to the right. In this operation, our array will reach its maximum size, and the index referencing the position of the last element will be equal to the array size minus one.
Hint:Q[Last index] == Q[Size - 1]
5) The fifth operation will be dequeue. Conceptually, this operation will leave position 0 of our array empty but will maintain the original order of the first and last place indicators.
6) The sixth operation will again be enqueue, this operation will remove the next element to be dequeued, which has been to the left of the last element until now, shifting it to the right of the last element. This aspect of the operation requires a bit more attention when dealing with the code
7) Next, we will perform the dequeue operation followed by enqueue, which will maintain the current order of the next to be removed and last to be removed.
This way, we do not need to reallocate all elements in the list with each new operation. With this approach, we move away from using a linear queue with a performance of a Big O(n) algorithm and instead, utilize a circular queue that operates with a Big O(1) time complexity, maintaining constant performance regardless of the queue size.
Queue implementation
Hint:If you skipped to this part, go back a little to see the creation of our virtual environment.
First, let's create our Queue class and define five attributes.
- size -> The total size of the Queue.
- start -> The first index of the Queue.
- end -> The last index of the Queue.
- elements -> All elements in the Queue.
- values -> The array that the queue will be structured, with two parameters Size that will define the size of the array and dtype to indicate the type of data that will be inserted.
import numpy as np
class CircularQueue:
def __init__(self, size):
self.size = size
self.start = 0
self.end = -1
self.elements = 0
self.values = np.empty(self.size, dtype=int)
Next, we will create two simple methods that will return boolean values indicating whether the queue is empty or full. The queue will be considered full when the index value of the last added element is equal to the total size of the list indicated in its instance.
def __empty(self):
return self.elements == 0
def __is_full(self):
return self.elements == self.size
Here, we will create the enqueue method responsible for adding elements to the queue. Initially, we check if the queue is full. If it is, we print a message on the screen and conclude the method call. However, if it's not full, we initiate the addition process.
First, we examine the positions of the next element to be removed and the last element. In this example queue [x, 2, 3, 4, 5], the index of the current last element is 4. Therefore, we check if the value of the last index satisfies the condition size - 1 == 4. If true, since the queue isn't full, it means we have reached the last position but have empty spaces to the left.
This way, the index of the next element will be -1. In the next line, we perform the operation -1 + 1, which will return the value of index 0. This action causes the algorithm to overwrite the element at position zero, which has already been removed, with the next input element, thereby reversing the positions of the indicators.
Then we will simply add the new element to the queue and update the values.
def enqueue(self, value):
if self.__is_full():
print('The queue is full')
return
else:
if self.end == self.size - 1:
self.end = -1
self.end +=1
self.values[self.end] = value
self.elements +=1
The next method to be created is the dequeue, responsible for removing an element from the queue. Initially, we will check if the queue is already empty. If it is, a message indicating that the queue is already empty will be printed, and the method will be terminated. If the queue is not empty, we will store the value of the object to be removed in the tmp variable and move the start index to the next element to be removed in future calls.
Next, it checks if start has reached the end of the queue (the last possible index). If yes, it adjusts start to 0, indicating that the queue forms a loop, and the next element to be removed will be at the beginning of the queue.
Then, we update the queue values and return the removed value.
def dequeue(self):
if self.__empty():
print('The queue is already empty')
return
tmp = self.values[self.start]
self.start +=1
if self.start == self.size -1:
self.start = 0
self.elements -= 1
return tmp
The last method will be first, which simply returns the next object to be removed from the queue without performing any operation on it. Initially, we check if the queue is not empty. If it is, we print a message on the screen and terminate the method call. If it is not empty, we locate the element by the start index and return the element at that position.
def first(self):
if self.__empty():
return -1
return self.values[self.start]
To test our implementation, we will perform a simple sequence of enqueues and dequeues, creating a queue with a size of 5.
queue = CircularQueue(5)
print(queue.first()) # Empty queue
----------------------------------------
-1
After that, we will call our enqueue method to add five elements to the queue and print the result.
for i in range(5):
queue.enqueue(i)
print(f"The value of the first element is: {queue.first()}")
----------------------------------------
The value of the first element is: 0
Hint: The value printed in the result above corresponds to the value of the element and not the index.
Then, we will remove two elements and check what our first element in the list is after the removal.
for j in range(2):
print(f"The removed element has the value of {queue.dequeue()}")
print(f"The first element of the queue is: {queue.first()}")
----------------------------------------
The removed element has the value of 0
The removed element has the value of 1
Now we will insert two more elements in the queue, the first insertion will swap the positions of the indicators with each other.
for i in range(6,8):
queue.enqueue(i)
Then we will remove two elements again and check what our first element in the list is after the new removal.
for j in range(2):
print(f"The removed element has the value of {queue.dequeue()}")
print(f"The first element of the queue is: {queue.first()}")
----------------------------------------
The removed element has the value of 2
The removed element has the value of 3
The first element of the queue is: 6
In summary, circular queues and stacks are essential components in streamlining data management processes. Their efficiency lies in the seamless handling of elements, providing valuable insights for tech enthusiasts. As we navigate the intricacies of computer science, a solid grasp of circular queues and stacks becomes indispensable for elevating algorithmic expertise.
Feel free to send your questions and clone the repository to access the full code
Top comments (0)