Search for a command to run...
I am Kelvin Amoaba, a software engineer with a passion for building dependable, scalable systems. I am obsessed with delving into technical nuances and discovering the magic hidden beneath the code.
No comments yet. Be the first to comment.
When extensions aren't enough
One thing about the current world is that people can decide to be everywhere. With technology, we can all be engaged in matters happening in other parts of the world so far from where we are and also be in touch with people from all over the world. O...
Monotonic and wall clock time are two ways we measure time. Wall clock time is the time we see on our clocks. It's the time we are all used to and respond with when someone asks "what time it is?". Monotonic time on the other hand, is one that simply...
Writing your own SMTP server basically means that you go by the SMTP RFCSs and make sure that your system responds appropriately to whatever commands that come in from other mail servers. Under the hood, smtp servers are doing the same things with sl...
An IP address is a unique 32-bit address that identifies any device connected to the internet. It is of the form X.X.X.X. Each networked device has a unique IP address attached to it. The definition for the IP address above is that of the IPV4 IP add...
A stack is a very important data structure that is used to work on data temporarily. Unlike other data structures that are built into a language, a stack is rather a layer added to an existing data structure, such as an array or linked list. In this tutorial, however, we will focus on the array-based implementation of a stack.
So just like arrays, the data added to a stack is stored in contiguous memory. The main difference between a stack and an array is how operations on data are performed. A stack behaves differently from an array due to a set of rules that are added to the behavior of the array.
Data structures that are built on top of rules from other data structures are called abstract data types. Another type of abstract data type is the queue, which we will discuss in another post.
The stack data structure is a very important data structure used in various areas of computer science, like recursion. A stack helps to implement various things. The undo and redo functionalities of your IDE are based on a stack; your browser navigation, forward and back, is also based on a stack.
The following rules differentiate how a stack operates from how an array operates.
You can only add to the end of the stack.
You can only read from the end of the stack.
You can only delete from the end of the stack.
In a typical array, one can insert data into any index they want, but in a stack, that is prohibited. If this rule is broken, then it is no longer a stack but something else. (#1)
Reading from a typical array does not restrict where in the array you read from. You can read from the beginning of the array, the middle, or the end, wherever you want to read from. But then, in a stack, it is mandatory to only read from the end of the stack.
The third rule states that you can only delete from the end of the stack. This is a very different behavior from a normal array because, in an array, one can delete at any index they want.
It should be noted that these rules are not pre-written in most languages but are implemented when the stack data structure is built. It is typically not a built-in structure but rather something that the programmer explicitly creates.
The end of the stack is referred to as the top. This is because we look at the stack not like a horizontal array but as a vertical array.
You can think of a stack data structure as stones placed on top of each other, like in the preview picture above. To add another stone, you place it on top of the already existing stones, not below or in the middle (Rule #1)
If the stones were colored and you want to see (read) the color of the most recent one, you will obviously look down at the stones. The latest one simply refers to the one you just added to the stack. (Rule #2)
Also, to remove a stone, you would have to remove the one from the top first, as this is the only logical way to go about it if you don't want your stone empire to come crumbling down (Rule #3)
This behaviour of the stack is referred to as the LIFO This is an acronym for Last In, First Out. This basically means that the first thing you add to the array is the last thing that comes out.
The operations performed on a stack are:
Reading, a.k.a. "Peeking,"
Adding: AKA "Pushing to the Stack".
Removing: AKA "Popping from the Stack".
class Stack:
def __init__(self):
self.data = []
def push(self, value):
self.data.append(value)
return len(self.data) - 1 # return the index of the item
def peek(self):
# Return the last value if the data array is not empty else
# return None
return self.data[-1] if len(self.data) > 0 else None
def remove(self):
# Here too when the user tries removing the last item, return
# it if there are elements in the array else return None
return self.data.pop() if len(self.data) > 0 else None
We define the Stack class; as previously stated, the stack is a data structure that you create and does not come pre-built in most programming languages.
In the__init__ method, we create an empty array and attach it to the object. As you can see here, the stack we are implementing is based on the array data structure.
Next, we define the push method, the push method is responsible for inserting a new value onto a stack. This is accomplished by invoking the append method and passing in the user-supplied value. The append method adds to the end of the list, which is referred to as the TOP in a stack. The index of the last item is then returned.
Next, we define the peek method, the peek method simply returns the last item in the array if there are items in it; otherwise, it returns None.
The remove method is next. Here, we return the last item in the array. This is done by calling the pop() method on a list. This will remove the last item in the list and return it.
Let's quickly go through an example of this implementation.
s1 = Stack()
s1.push(1) # This adds 1 to the stack
print(s1.peek()) # This prints out 1, since it's the item at the top
s1.push(2)
s1.push(3)
print(s1.peek()) # This prints out 3, since it's the latest item at the top
s1.remove()
print(s1.peek()) # this prints 2 since 3 has been removed from the stack
As you can see from above, the LIFO behavior is working in full effect. The first item added will be the last item to leave.
Browser Forward and Back Navigation
Web browsers implement forward and back navigation using two stacks: the undo stack and the redo stack. As the user navigates between pages, the current URL is pushed onto the undo stack. Pressing the back button pops the URL from the undo stack and pushes it onto the redo stack, allowing the user to move backward and forward through their browsing history. This dual-stack system ensures efficient navigation between visited pages. This is a very simple breakdown; a lot gets built on this, though :D
Function Call Management
In programming, a call stack is a stack data structure that controls a function call. When a function is called, its parameters, local variables, and return address are pushed onto the call stack. As functions complete execution, they are deleted from the stack, returning the program to the previous execution context. This is mostly used in recursive programming.
Solving Algorithmic Problems
Several problems you will encounter will require some comprehension of stacks in order to solve them efficiently. Some include:
First-depth search problem
Reversing items in a list or string