Question: There is an array A[N] of N numbers. You have to compose an array Output[N] such that each element in Output[i] will tell the next greater element to the right in the original array. If there is no greater number to the right, then the output array should contain 1 in that position.Array 1: {4, 6, 5, 4, 3, 4, 9, 8, 1} Output: {6, 9, 9, 9, 4, 9, 1, 1, 1} Let us try to understand the problem statement. We are given an input array that has…
Stack
Algorithms involving stacks


We discussed about the basic tree traversals in this post – Binary Tree Traversals Lets take our own sample tree for understanding postorder traversal. In PostOrder traversal, the root is visited after both subtrees are completed. Postorder traversal is defined as follows: Traverse the left subtree in postorder. (Step 1) Traverse the right subtree in postorder. (Step 2) Visit the root The postorder traversal can then be defined in this way – The nodes of the tree will therefore be in order – 4, 5, 2, 6, 7, 3, 1…

We discussed about the tree traversal techniques in this post Binary Tree Traversals Please see preorder traversal to understand the basics of visiting nodes. We have our same sample tree Now let us try to understand the Inorder traversal. In inorder traversal, the root is traversed between the sub trees. Inorder traversal is defined as follows. Traverse the left subtree Visit the node Traverse the right subtree So when we apply the inorder traversal on our example tree this will be done as: We get the final inorder traversal as:…

We learned about the different type of traversals in this post Binary Tree Traversals In preorder traversal, each node is processed before (pre) either of its subtrees. This is the simplest traversal to understand. However, even though each node is processed before the subtrees, it still requires that some information must be maintained while moving down the tree. Let us consider an example In the example tree shown above, the node “1” is processed first, then the left subtree, followed by the right subtree. Therefore, processing must return to the…

Question: Give an algorithm to reverse a queue. You can only use generic functions of the Queue ADT. Input: 4, 8, 15, 16, 23, 42 Output: 42,23,16,15,8,4 To solve this question will take the help of an auxiliary stack. The steps involved will be: Create an auxiliary stack S. Until the queue Q is not empty, push the elements of the queue, in the stack S. Now we have a stack in which the last element of the Queue is at the TOP. Until the stack is empty POP(S) and…

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…

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.

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…
 1
 2