A queue is a linear data structure which maintains the order in which the elements appear. You need to implement a queue, using two stacks such that it behaves in the same way. If you are unfamiliar with the queue data structure and the stack data structure, it would be a good idea to learn them before approaching this problem. Problem Statement: The basic crux of the problem is that you are to implement a queue and its operations using stacks. It may seem unnecessary in the beginning, as a…
Stack
Algorithms involving stacks


Question: Given 3 arrays, where each element represent the height of a cylinder. Find the maximum possible height of equal stacks by removing one or more cylinders from the original stack. Example: Input: n1[] = {3, 2, 1, 1, 1}n2[] = {4, 3, 2}n3[] = {1, 1, 4, 1} Output: 5 Problem Statement Let us try to simplify the problem statement first. The problem states that you are provided with 3 sets of arrays. Each element in the array represents the height of a cylinder. Now, all these cylinders are…

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…

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