Competitive Python

Tuple is a linear data structure which more or less behaves like a python list but with a really important difference, that a tuple is immutable . Immutable means that this structure can't be changed after it has been created, it can't be mutated if I may. Tuples being immutable are more memory efficient than list as they don't over allocate memory . Okay, so what this means is, when a list is created it takes up and reserves extra spaces of memory than needed for the original elements as new elements might be added to the list later and allocating memory on every addition would be quite inneficient but tuples, once created surelly won't change the numbers of elements in it later on, so it allocates exactly how much memory is needed. Almost all the list operations work for tuples except the ones which mutate it, for example, insert, append, remove etc. Declaring a tuple : Tuples can be initialise in a manner similar to list, But there's an important c...

In this post we will explore and implement an algorithm which helps us verify that if the brackets are balanced or validly used. This is a very important application of stacks as a lot of programming languages use brackets very extensively in their syntax and one of the job of a compiler is to check if the brackets are balanced or not. For simplicity's sake we will just use a list with the methods append() and pop(). This will help us emulate a stack without actually needing to implement it. If you want to, you can go and learn about stacks on this link . A set of brackets can be called balanced if all of the brackets in it are properly matched. Examples of balanced brackets : (([]{}{})) ({{}}[]) Examples of unbalanced brackets : (([)]) {{}]}]]) So now getting to the algorithm, what we simply do is that we go through a string of brackets and check that for every closing bracket there is a properly nested opening bracket. This is how we do it - Convert the input string into a...

We are going to look at Dijkstra's two-stack algorithm and see how it's implemented. This algorithm is used to evaluate infix expressions. It uses stacks at its core, so if you don't know about stacks or if you'd want to learn more about them, click this link There are three types of expressions, Infix : Infix expressions are the ones where the operators are used between values, like a + b - c . Postfix : These are the expressions where operators are written after the values, like a b c +- , this translates to a + b - c in infix. Prefix : In these expressions, the operators are written before the values, for example + - a b c . This expression will also be equal to a + b - c in infix. Okay, so what this algorithm does is evaluate expressions like ( ( 3 + 4 ) * 83 ) . It starts by breaking down this expression into a list of stings and create two empty stack, one for housing the values and other for the operators. Then we go through the list one by one. Whenev...

Today, we will talk about another linear data structure , a Queue. It is a data structure thay basically acts like a real life queue. It works on FIFO (First in First out) principle. It means that the element that gets added to the queue first gets removed the first, it's like first come first serve basis.In a queue, the operations take effect at rear and front end of the list. Enque adds the element to the back of the queue and Dequeue removes the element from the front of the queue. Queue is a very essential data structure and also form the basis for some advanced data structures. Applications of a queue- CPU procces scheduling Real life simulations The methods associated with a queue are - Enque(): Adds an element to the back of the queue Deque(): Removes an element from the front of the queue isEmpty(): Returns wether the queue is empty or not size(): Returns the size of the queue Here is the implementation of the Queue data structure, in this implementation we...

Stack So, now we're going to talk about stack , a linear data structure and also we will see its implementation. In another post which will be linked below later will discuss its uses. So what is a stack ? Visualise a pile of coins or a stack of trays put one over the other. The item that has been put at the last has to be removed first as it is over all the other items. Hence, it is a data structure that works on LIFO (Last in First out) principle. Which simply means that the element that has been added the last will be removed first. It is a very useful data structure and has several applications like expression evaluation and HTML validat or or a bracket matching verifier . In this data structure we only have operations that take their effect only at one end of the list. Both, the front or the end of a list can be used to implement it but using the tail(back-end) of the list is more efficient. The main operation or methods on a stack are - Push : Adds element at the...