A queue is a First-In-First-Out linear data structure, i.e., the element that is first inserted into the queue is the element that comes out first. The operation that involves inserting an element into the queue is called enqueue. The operation that involves removing an element from the queue is called dequeue. Normally, a queue is implemented using an array and two pointers; front and rear. This makes the time complexity of enqueue and dequeue operations O(1).
In this snippet, we will instead look at implementing a queue using a stack. This may increase the time complexity of the enqueue or dequeue operations, but the idea here is to see how such an implementation will look like. A stack is a Last-In-First-Out linear data structure. Here the last element inserted into the stack is the first element that comes out of the stack. It has push and pop operations where push inserts the element into the stack and pop removes the last inserted element from the stack.
Introduction According to Wikipedia, dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a tree. Once the the dynamic connectivity structure is built, it should adapt itself such that it can give quick answers to queries of the form “is there a path between x and y?”. The Union-Find algorithm is one approach build this connectivity structure. There are multiple approaches the Union-Find algorithm, the most optimal approach is the Weighted Quick Union algorithm.
Introduction In this article, we will write a simple implementation of the tail command from Linux. This program will take a file and an integer n as input and print the last n lines from the file. Also, the goal of the program is to not read the entire file into memory at once. This will make the program memory efficient when dealing with very large files.
Implementation Details In order to implement this program, we will use queue data structure.
Comparison Model In computer science, sorting a list of items is a very basic as well as an important problem, that is discussed in some great detail. We basically start by using some of the simplest and intuitive techinques to sort items, like Bubble sort or Insertion sort, which are not very efficient. By efficiency, I mean their runtime is very large for very large list of items. These basic algorithms have a time complexity of O(n^2).
About
Bharghava Varun Ayada is a Staff Software Engineer at Walmart Labs, living in Bangalore, India. This blog is about software engineering, system design, distributed systems and DevOps.