A queue is a linear data structure that stores data (similar to Linked Lists and Stacks). In a queue, the order in which the data arrives is important. Definition: A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at other end (front). The first element that you insert, is the first one that is removed. This makes it a First In First Out (FIFO) or Last In Last Out (LILO) list. Basic Operations: The basic operations on this data structure…
nikoo28
nikoo28
a techsavvy guy and a design buff... I was born with the love for exploring and want to do my best to give back to the community. I also love taking photos with my phone and Canon Kiss X5 in order to capture moments in my life. It's my pleasure to have you here.


Question: Find spans in an array. Given an array arr[], the SPAN s[i] of arr[i] is the maximum number of consecutive elements arr[j] immediately before arr[i] such that arr[j] <= arr[i]. Let us try to understand the question once again. This is a very common problem in stock markets to find the peaks. Spans have applications to financial analysis(Example: You might have heard a saying “STOCKS AT 52 WEEK HIGH”). The span of a stocks price on certain day, i , is the maximum number of consecutive days (upto the…

This is one of the very basic pointer usage in C and to understand it let us start with a very simple example. Suppose we have a program like: In this case the first statement: declares p as a pointer to char. When we say “pointer to a char“, what does that mean? It means that the value of p is the address of a char; p tells us where in memory there is some space set aside to hold a char. The statement also initializes p to point to…

Question: How do we implement 2 stacks using only one array? Our stack routines should not indicate an exception unless every slot in the array is used? SOLUTION: Algorithm: Start with two indexes, one at the left end and other at the right end The left index simulates the first stack and the right index simulates the second stack. If we want to push an element into the first stack then put the element at left index. Similarly, if we want to push an element into the second stack then…

Question: You are given a stack and you have to reverse it, using only stack operations push and pop. The algorithm for the above problem can be given in this way: First POP all elements of the stack till it becomes empty Now for each upward step in the recursion, push the elements at the bottom of the stack.

ArraysStrings
Given an array of characters formed with a’s and b’s. The center is marked with ‘ X ‘. Check whether the string is palindrome or not?
by nikoo28Question: Given an array of characters formed by a’s and b’s. The string is marked with special character ‘X’ which represents the middle of the list (for example ababa…ababXbabab…baaa). Check whether the string is palindrome or not? Input: ababXbaba Output: PALINDROME Input: ababababababbbbbXbbbbabababababa Output: PALINDROME Input: abababbbabbXabbbabbabbb Output: NOT PALINDROME This is one of the simplest algorithms. What we do is, start two indexes – one at the beginning of the string and other at the ending of the string. Each time compare whether the values at both the indexes…

Suppose we want to find the minimum element available in a stack at any point of time. The most trivial and common method would be to traverse the entire stack and keep a record of the least element encountered. At the end, we can return this element. This method no doubt is easy, but it consists of traversing the entire stack again and again, which can lead to time complexities. Thus, we need to optimize it, and it can be done with a very neat little trick: ALGORITHM: Take an…

Postfix expressions have a very special place in computer science. Most of the computations are performed using stacks. Infact a very simple calculator works on the principle of postfix evaluation to get the answer. A postfix notation is also known as the reverse Polish notation. The steps involved in evaluating a postfix expression can be defined as follows. We use the concept of stacks to evaluate the same. ALGORITHM: Scan the postfix string from left to right. Initialize an empty stack. Repeat the below steps 4 and 5 till all…

In infix expressions, the operator precedence is implicit unless we use parentheses. Therefore, for the infix to postfix conversion algorithm, we have to define the operator precedence inside the algorithm. We did this in the post covering infix, postfix and prefix expressions. What are infix, prefix and postfix expressions? Important properties: Let us consider the infix expression 2 + 3 * 4 and its postfix will be 2 3 4 * +. Notice that between infix and postfix the order of the numbers(or operands) is unchanged. It is 2 3…

Stacks can be used to implement algorithms involving Infix, postfix and prefix expressions. So let us learn about them: INFIX: An infix expression is a single letter, or an operator, proceeded by one infix string and followed by another infix string. A A + B (A + B) + (C – D) PREFIX: A prefix expression is a single letter, or an operator, followed by two prefix strings. Every prefix string longer than a single variable contains an operator, first operand and second operand A + A B + +…